login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A007123 Number of connected unit interval graphs with n nodes; also number of bracelets (turnover necklaces) with n black beads and n-1 white beads.
(Formerly M1218)
12
1, 1, 2, 4, 10, 26, 76, 232, 750, 2494, 8524, 29624, 104468, 372308, 1338936, 4850640, 17685270, 64834550, 238843660, 883677784, 3282152588, 12233309868, 45741634536, 171530482864, 644953425740, 2430975800876 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

Also number of rooted planar general trees (of n vertices or n-1 edges) up to reflection. - Antti Karttunen, Aug 09 2002 (for the correspondence with bracelets, start by considering Raney's lemma as explained by Graham, Knuth & Patashnik).

Number of connected lattice path matroids on n elements up to isomorphism.

a(n) = number of noncrossing set partitions of [n] up to reflection (i<->n+1-i). Example: a(4) counts 123, 1-23, 13-2, 1-2-3 but not 12-3 because it is the reflection of 1-23. - David Callan, Oct 08 2005

From Vladimir Shevelev, Apr 23 2011: (Start)

Also number of non-equivalent necklaces of n beads, each of which is painted by one of 2*n-1 colors.

The sequence solves the so-called Reis problem about convex k-gons in case N=2*n-1, k=n. H. Gupta (1979) gave a full solution; I gave a short proof of Gupta's result and showed an equivalence of this problem and each of the following problems: the problem of enumerating the bracelets of n beads of 2 colors, k of them black, and the problem of enumerating the necklaces of k beads, each painted by one of n colors.

a(n) is an essentially unimprovable upper estimate for the number of distinct values of the permanent in (0,1)-circulants of order 2*n-1 with n 1's in every row.

(End)

REFERENCES

S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.

R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 345 & 346.

R. W. Robinson, personal communication.

R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

R. W. Robinson, Table of n, a(n) for n = 1..190

J. E. Bonin, A. de Mier and M. Noy, Lattice path matroids: enumerative aspects and Tutte polynomials, arXiv:math/0211188 [math.CO], 2002.

P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.

H. Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no.8, 964-999.

F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.

V. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.

V. Shevelev, Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma), arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).

Index entries for sequences related to bracelets

FORMULA

a(n+1) = (Cat(n)+binomial(n, floor(n/2)))/2 = (A000108(n)+A001405(n))/2. - Antti Karttunen, Aug 09 2002

G.f.: (1+2*x-sqrt(1-4*x)*sqrt(1-4*x^2))/(4*sqrt(1-4*x^2)).

G.f.: (sqrt((1 + 2*x) / (1 - 2*x)) - sqrt(1 - 4*x)) / 4. - Michael Somos, Apr 16 2012

a(n) = (A063886(n) - A002420(n)) / 4. - Michael Somos, Apr 16 2012

n*(n-1)*(n-4)*a(n) -4*(n-1)*(n^2-5*n+5)*a(n-1) -4*(n-2)*(n^2-7*n+11)*a(n-2) +8*(2*n-7)*(n-2)*(n-3)*a(n-3)=0. - R. J. Mathar, Aug 22 2018

EXAMPLE

x + x^2 + 2*x^3 + 4*x^4 + 10*x^5 + 26*x^6 + 76*x^7 + 232*x^8 + 750*x^9 + ...

MATHEMATICA

f[k_Integer, n_] := (Plus @@ (EulerPhi[ # ]Binomial[n/#, k/# ] & /@ Divisors[GCD[n, k]])/n + Binomial[(n - If[OddQ@n, 1, If[OddQ@k, 2, 0]])/2, (k - If[OddQ@k, 1, 0])/2])/2 - Robert A. Russell, Sep 27 2004

Table[ f[n, 2n - 1], {n, 10}]

(* Comment from Wouter Meeussen, Feb 02 2013, added by N. J. A. Sloane, Feb 02 2013: To get lists of the necklaces in Mathematica, use (if n=4, say):

<<Combinatorica`;

ListNecklaces[2*4- 1, {0, 1}, Dihedral] *)

PROG

(PARI) {a(n) = if( n<1, 0, (2 * binomial(n-1, (n-1)\2) + binomial(2*n, n) / (2*n - 1)) / 4)} /* Michael Somos, Apr 16 2012 */

(Python)

from sympy import catalan, binomial, floor

def a(n): return 1 if n==1 else (catalan(n - 1) + binomial(n - 1, floor((n - 1)/2)))/2 # Indranil Ghosh, Jun 03 2017

CROSSREFS

Cf. A002420, A007595, A063886, A073201.

Occurs as row 164 in A073201. Next-to-center columns of triangle A052307.

Sequence in context: A007579 A239078 A303930 * A220871 A007578 A239079

Adjacent sequences:  A007120 A007121 A007122 * A007124 A007125 A007126

KEYWORD

nonn,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

Extended by Christian G. Bower

Edited by Jon E. Schoenfield, Feb 14 2015

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 16 12:00 EDT 2018. Contains 316263 sequences. (Running on oeis4.)