|
| |
|
|
A007123
|
|
Number of connected unit interval graphs with n nodes; also bracelets (turn over necklaces) with n black beads and n-1 white beads.
(Formerly M1218)
|
|
11
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| Also number of rooted planar general trees (of n vertices or n-1 edges) up to reflection, - AK, 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 (callan(AT)stat.wisc.edu), Oct 08 2005
Contribution by Vladimir Shevelev, Apr 23 2011: (Start)
Also number of non-equivalent necklaces of n beads each of them 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. Full solution gave H.Gupta (1979); I gave a short proof of Gupta's result and showed an equivalence of this problem and every of the following problems: problem of enumerating the bracelets of n beads of 2 colors, k of them black, and problem of enumerating the necklaces of k beads each of them 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).
H. Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no.8, 964-999.
V. Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
|
|
|
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.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
Index entries for sequences related to bracelets
V. Shevelev,Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma)(Cf. Section 5)
|
|
|
FORMULA
| a(n) = (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)).
|
|
|
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 (russell(AT)post.harvard.edu), Sep 27 2004
Table[ f[n, 2n - 1], {n, 10}]
|
|
|
CROSSREFS
| Cf. A007595, A073201.
Occurs as row 164 in A073201. Next-to-center columns of triangle A052307.
Sequence in context: A049401 A148099 A007579 * A007578 A007580 A000085
Adjacent sequences: A007120 A007121 A007122 * A007124 A007125 A007126
|
|
|
KEYWORD
| nonn,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Extended by Christian G. Bower (bowerc(AT)usa.net)
|
| |
|
|
