The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. 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) The number of Dyck paths of semilength n-1 up to reversal; that is, the number of Dyck paths of semilength n-1, treating as identical a path and that path when traveled in reverse order. - Noah A Rosenberg, Jan 28 2019 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. Hansraj Gupta, Enumeration of incongruent cyclic k-gons, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999. Z. M. Himwich and N. A. Rosenberg, Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees, arXiv:1901.04465 [qbio.PE], 2019. (cf. Table 1) F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only] Vladimir Shevelev, Necklaces and convex k-gons, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638. Vladimir 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). FORMULA a(n+1) = (Catalan(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 D-finite with recurrence 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): <

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

Last modified June 20 10:03 EDT 2021. Contains 345162 sequences. (Running on oeis4.)