|
Search: id:A007123
|
|
|
| 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)
|
|
+0
10
|
|
| 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; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
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
|
|
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.
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
|
|
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 this_sequence A007578 A007580 A000085
Adjacent sequences: A007120 A007121 A007122 this_sequence 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)
|
|
|
Search completed in 0.003 seconds
|
