This site is supported by donations to The OEIS Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A003239 Number of rooted planar trees with n non-root nodes: circularly cycling the subtrees at the root gives equivalent trees. (Formerly M1222) 32

%I M1222

%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 2n 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)=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 G. Labelle, P. Leroux, Enumeration of (uni- or bicolored) plane trees according to their degree distribution, Disc. Math. 157 (1996) 227-240, Eq. (1.18)

%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, 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>, in Fibonacci Quarterly, 55(5): pp 30-41, (2017).

%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, 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 (1998), no. 2, 233--238. MR1691428 (2000c:13006).

%H A. Elashvili, M. Jibladze, D. Pataraia, <a href="http://dx.doi.org/10.1023/A:1018727630642">Combinatorics of necklaces and "Hermite reciprocity"</a>, J. Algebraic Combin. 10 (1999), no. 2, 173--188. MR1719140 (2000j:05009). See p. 174. - _N. J. A. Sloane_, Aug 06 2014

%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, 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 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 J. Sawada, <a href="http://dx.doi.org/10.1145/1125994.1125995">Generating rooted and free plane trees</a>, ACM Transactions on Algorithms, Vol. 2 No. 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, vol. 19, No. 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(2d, d))/(2n), n>0.

%F a(n) = (1/n) Sum_{d|n} (phi(n/d)*binomial(2d-1, d)), 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 = 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 */

%Y Cf. A002995, A057510, A000108, A022553, A084575, A037306.

%Y Cf. A082936.

%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