|
%I M1218 #106 Oct 16 2022 18:52:33
%S 1,1,2,4,10,26,76,232,750,2494,8524,29624,104468,372308,1338936,
%T 4850640,17685270,64834550,238843660,883677784,3282152588,12233309868,
%U 45741634536,171530482864,644953425740,2430975800876,9183681736376,34766785487152,131873995933480
%N Number of connected unit interval graphs with n nodes; also number of bracelets (turnover necklaces) with n black beads and n-1 white beads.
%C 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.)
%C Number of connected lattice path matroids on n elements up to isomorphism.
%C 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
%C From _Vladimir Shevelev_, Apr 23 2011: (Start)
%C Also number of non-equivalent necklaces of n beads, each of which is painted by one of 2*n-1 colors.
%C 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.
%C 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)
%C 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
%D S. R. Finch, Mathematical Constants, Cambridge, 2003, Section 5.6.7.
%D R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics. Addison-Wesley, Reading, MA, 1990, p. 345 & 346.
%D R. W. Robinson, personal communication.
%D R. W. Robinson, Numerical implementation of graph counting algorithms, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1980.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H Alois P. Heinz, <a href="/A007123/b007123.txt">Table of n, a(n) for n = 1..1670</a> (first 190 terms from R. W. Robinson)
%H J. E. Bonin, A. de Mier, and M. Noy, <a href="https://arxiv.org/abs/math/0211188">Lattice path matroids: enumerative aspects and Tutte polynomials</a>, arXiv:math/0211188 [math.CO], 2002.
%H P. J. Cameron, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL3/groups.html">Sequences realized by oligomorphic permutation groups</a>, J. Integ. Seqs., Vol. 3 (2000), #00.1.5.
%H Hansraj Gupta, <a href="https://web.archive.org/web/20200806162943/https://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/20005a66_964.pdf">Enumeration of incongruent cyclic k-gons</a>, Indian J. Pure and Appl. Math., 10 (1979), no. 8, 964-999.
%H Z. M. Himwich and N. A. Rosenberg, <a href="https://arxiv.org/abs/1901.04465">Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees</a>, arXiv:1901.04465 [qbio.PE], 2019; Adv. Appl. Math. 113 (2020), 101939. (cf. Table 1)
%H F. Ruskey, <a href="http://combos.org/necklace">Necklaces, Lyndon words, De Bruijn sequences, etc.</a>
%H F. Ruskey, <a href="/A000011/a000011.pdf">Necklaces, Lyndon words, De Bruijn sequences, etc.</a> [Cached copy, with permission, pdf format only]
%H Vladimir Shevelev, <a href="https://web.archive.org/web/20200722171019/http://www.insa.nic.in/writereaddata/UpLoadedFiles/IJPAM/2000c4e8_629.pdf">Necklaces and convex k-gons</a>, Indian J. Pure and Appl. Math., 35 (2004), no. 5, 629-638.
%H Vladimir Shevelev, <a href="http://arxiv.org/abs/1104.4051">Spectrum of permanent's values and its extremal magnitudes in Lambda_n^3 and Lambda_n(alpha,beta,gamma)</a>, arXiv:1104.4051 [math.CO], 2011. (Cf. Section 5).
%H <a href="/index/Br#bracelets">Index entries for sequences related to bracelets</a>
%F a(n+1) = (Catalan(n) + binomial(n, floor(n/2)))/2 = (A000108(n) + A001405(n))/2. - _Antti Karttunen_, Aug 09 2002
%F G.f.: (1 + 2*x - sqrt(1 - 4*x)*sqrt(1 - 4*x^2))/(4*sqrt(1 - 4*x^2)).
%F G.f.: (sqrt((1 + 2*x) / (1 - 2*x)) - sqrt(1 - 4*x)) / 4. - _Michael Somos_, Apr 16 2012
%F a(n) = (A063886(n) - A002420(n)) / 4. - _Michael Somos_, Apr 16 2012
%F 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
%e x + x^2 + 2*x^3 + 4*x^4 + 10*x^5 + 26*x^6 + 76*x^7 + 232*x^8 + 750*x^9 + ...
%t 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 *)
%t Table[ f[n, 2n - 1], {n, 10}]
%t (* 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):
%t <<Combinatorica`;
%t ListNecklaces[2*4- 1, {0, 1}, Dihedral] *)
%o (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 */
%o (Python)
%o from sympy import catalan, binomial, floor
%o 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
%Y Cf. A000108, A002420, A007595, A063886, A073201.
%Y Occurs as row 164 in A073201.
%Y Next-to-center columns of triangle A052307.
%Y Equal to A001405 plus A006079.
%K nonn,nice
%O 1,3
%A _N. J. A. Sloane_
%E Extended by _Christian G. Bower_
%E Edited by _Jon E. Schoenfield_, Feb 14 2015
|
