|
%I M1222 #136 Jul 11 2023 12:21:26
%S 1,1,2,4,10,26,80,246,810,2704,9252,32066,112720,400024,1432860,
%T 5170604,18784170,68635478,252088496,930138522,3446167860,12815663844,
%U 47820447028,178987624514,671825133648,2528212128776,9536895064400,36054433810102,136583761444364,518401146543812
%N Number of rooted planar trees with n non-root nodes: circularly cycling the subtrees at the root gives equivalent trees.
%C Also number of necklaces with 2*n beads, n white and n black (to get the correspondence, start at root, walk around outside of tree, use white if move away from the root, black if towards root).
%C Also number of terms in polynomial expression for permanent of generic circulant matrix of order n.
%C a(n) is the number of equivalence classes of n-compositions of n under cyclic rotation. (Given a necklace, split it into runs of white followed by a black bead and record the lengths of the white runs. This gives an n-composition of n.) a(n) is the number of n-multisets in Z mod n whose sum is 0. - _David Callan_, Nov 05 2003
%D Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 305 (see R(x)).
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973; page 80, Problem 3.13.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 7.112(b).
%H Seiichi Manyama, <a href="/A003239/b003239.txt">Table of n, a(n) for n = 0..1669</a> (terms 0..200 from T. D. Noe)
%H Bruce M. Boman, Thien-Nam Dinh, Keith Decker, Brooks Emerick, Christopher Raymond, and Gilberto Schleinger, <a href="https://www.fq.math.ca/Papers1/55-5/Boman.pdf">Why do Fibonacci numbers appear in patterns of growth in nature?</a>, Fibonacci Quarterly, 55(5) (2017), 30-41.
%H R. Brualdi and M. Newman, <a href="http://nvlpubs.nist.gov/nistpubs/jres/74B/jresv74Bn1p37_A1b.pdf">An enumeration problem for a congruence equation</a>, J. Res. Nat. Bureau Standards, B74 (1970), 37-40.
%H CombOS - Combinatorial Object Server, <a href="http://combos.org/tree.html">Generate rooted plane trees</a>.
%H Paul Drube and Puttipong Pongtanapaisan, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Drube/drube3.html">Annular Non-Crossing Matchings</a>, Journal of Integer Sequences, Vol. 19 (2016), #16.2.4.
%H A. Elashvili and M. Jibladze, <a href="http://dx.doi.org/10.1016/S0019-3577(98)80021-9">Hermite reciprocity for the regular representations of cyclic groups</a>, Indag. Math. (N.S.) 9(2) (1998), 233--238. MR1691428 (2000c:13006).
%H A. Elashvili, M. Jibladze, and D. Pataraia, <a href="http://dx.doi.org/10.1023/A:1018727630642">Combinatorics of necklaces and "Hermite reciprocity"</a>, J. Algebraic Combin. 10(2) (1999), 173--188. MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014
%H M. L. Fredman, <a href="https://doi.org/10.1016/0097-3165(75)90008-4">A symmetry relationship for a class of partitions</a>, J. Combin. Theory Ser. A, 18 (1975), 199-202. See Eq. (4), a(n) = S(n,n,0).
%H F. Harary and R. W. Robinson, <a href="http://dx.doi.org/10.1515/crll.1975.278-279.322">The number of achiral trees</a>, J. Reine Angew. Math., 278 (1975), 322-335.
%H F. Harary and R. W. Robinson, <a href="/A002995/a002995_1.pdf">The number of achiral trees</a>, J. Reine Angew. Math., 278 (1975), 322-335. (Annotated scanned copy)
%H Thomas C. Hull and Tomohiro Tachi, <a href="https://arxiv.org/abs/1709.03210">Double-line rigid origami</a>, arXiv:1709.03210 [math.MG], 2017.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=761">Encyclopedia of Combinatorial Structures 761</a>.
%H Benjamin Ruoyu Kan, <a href="https://dash.harvard.edu/handle/1/37376406">Polynomial Approximations for Quantum Hamiltonian Complexity</a>, Bachelor's thesis, Harvard Univ., 2023.
%H G. Labelle and P. Leroux, <a href="https://doi.org/10.1016/S0012-365X(96)83017-2">Enumeration of (uni- or bicolored) plane trees according to their degree distribution</a>, Disc. Math. 157 (1996), 227-240, Eq. (1.18).
%H J. Malenfant, <a href="http://arxiv.org/abs/1502.06012">On the Matrix-Element Expansion of a Circulant Determinant</a>, arXiv preprint arXiv:1502.06012 [math.NT], 2015.
%H Paul Melotti, Sanjay Ramassamy, and Paul Thévenin, <a href="https://arxiv.org/abs/2003.11006">Points and lines configurations for perpendicular bisectors of convex cyclic polygons</a>, arXiv:2003.11006 [math.CO], 2020.
%H J. Sawada, <a href="http://dx.doi.org/10.1145/1125994.1125995">Generating rooted and free plane trees</a>, ACM Transactions on Algorithms, 2(1) (2006), 1-13.
%H Hugh Thomas, <a href="http://arxiv.org/abs/math/0301048">The number of terms in the permanent and the determinant of a generic circulant matrix</a>, arXiv:math/0301048 [math.CO], 2003.
%H D. W. Walkup, <a href="http://dx.doi.org/10.1112/S0025579300005659">The number of plane trees</a>, Mathematika, 19(2) (1972), 200-204. - From _N. J. A. Sloane_, Jun 08 2012
%H <a href="/index/Ne#necklaces">Index entries for sequences related to necklaces</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F a(n) = Sum_{d|n} (phi(n/d)*binomial(2*d, d))/(2*n) for n > 0.
%F a(n) = (1/n)*Sum_{d|n} (phi(n/d)*binomial(2*d-1, d)) for n > 0.
%F a(n) = A047996(2*n, n). - _Philippe Deléham_, Jul 25 2006
%F a(n) ~ 2^(2*n-1) / (sqrt(Pi) * n^(3/2)). - _Vaclav Kotesovec_, Aug 22 2015
%p with(numtheory): A003239 := proc(n) local t1,t2,d; t2 := divisors(n); t1 := 0; for d in t2 do t1 := t1+phi(n/d)*binomial(2*d,d)/(2*n); od; t1; end;
%p spec := [ C, {B=Union(Z,Prod(B,B)), C=Cycle(B)}, unlabeled ]; [seq(combstruct[count](spec, size=n), n=0..40)];
%t a[n_] := Sum[ EulerPhi[n/k]*Binomial[2k, k]/(2n), {k, Divisors[n]}]; a[0] = 1; Table[a[n], {n, 0, 25}] (* _Jean-François Alcover_, Apr 11 2012 *)
%o (PARI)
%o C(n, k)=binomial(n,k);
%o a(n) = if(n<=0, n==0, sumdiv(n, d, eulerphi(n/d) * C(2*d, d)) / (2*n) );
%o /* or, second formula: */
%o /* a(n) = if(n<=0, n==0, sumdiv(n, d, eulerphi(n/d) * C(2*d-1,d)) / n ); */
%o /* _Joerg Arndt_, Oct 21 2012 */
%o (SageMath)
%o def A003239(n):
%o if n == 0: return 1
%o return sum(euler_phi(n/d)*binomial(2*d, d)/(2*n) for d in divisors(n))
%o print([A003239(n) for n in (0..29)]) # _Peter Luschny_, Dec 10 2020
%Y Cf. A002995, A057510, A000108, A022553, A082936, A084575, A037306.
%Y Column k=2 of A208183.
%Y Column k=1 of A261494.
%K nonn,nice,easy
%O 0,3
%A _N. J. A. Sloane_
%E Sequence corrected and extended by Roderick J. Fletcher (yylee(AT)mail.ncku.edu.tw), Aug 1997
%E Additional comments from _Michael Somos_
|
