cp's OEIS Frontend

A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.

%I A002995 M0805 #121 May 02 2025 14:29:10
%S A002995 1,1,1,1,2,3,6,14,34,95,280,854,2694,8714,28640,95640,323396,1105335,
%T A002995 3813798,13269146,46509358,164107650,582538732,2079165208,7457847082,
%U A002995 26873059986,97239032056,353218528324,1287658723550,4709785569184
%N A002995 Number of unlabeled planar trees (also called plane trees) with n nodes.
%C A002995 Noncrossing handshakes of 2(n-1) people (each using only one hand) on round table, up to rotations - _Antti Karttunen_, Sep 03 2000
%C A002995 Equivalently, the number of noncrossing partitions up to rotation composed of n-1 blocks of size 2. - _Andrew Howroyd_, May 04 2018
%C A002995 a(n), n>2, is also the number of oriented cacti on n-1 unlabeled nodes with all cutpoints of separation degree 2, i.e. ones shared only by two (cyclic) blocks. These are digraphs (without loops) that have a unique Eulerian tour. Such digraphs with labeled nodes are enumerated by A102693. - _Valery A. Liskovets_, Oct 19 2005
%C A002995 Labeled plane trees are counted by A006963. - _David Callan_, Aug 19 2014
%C A002995 This sequence is similar to A000055 but those trees are not embedded in a plane. - _Michael Somos_, Aug 19 2014
%D A002995 Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, page 304.
%D A002995 A. Errera, De quelques problèmes d'analysis situs, Comptes Rend. Congr. Nat. Sci. Bruxelles, (1930), 106-110.
%D A002995 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 67, (3.3.26).
%D A002995 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A002995 T. D. Noe, <a href="/A002995/b002995.txt">Table of n, a(n) for n=0..200</a>
%H A002995 F. Bergeron, G. Labelle and P. Leroux, <a href="https://books.google.de/books?id=83odtWY4eogC">Combinatorial Species and Tree-Like Structures</a>, Cambridge, 1998, pp. 285 (4.1.26), 291 (4.1.48)
%H A002995 CombOS - Combinatorial Object Server, <a href="http://combos.org/tree.html">Generate free plane trees</a>
%H A002995 R. Cori and M. Marcus, <a href="https://doi.org/10.1016/S0304-3975(98)00031-0">Counting non-isomorphic chord diagrams</a>, Theor. Comp. Sci. 204 (1998) 55-75, Corollary 5.2.
%H A002995 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 A002995 A. Errera, <a href="/A002995/a002995.pdf">Reviews of two articles on Analysis Situs</a>, from Fortschritte [Annotated scanned copy]
%H A002995 D. Feldman, <a href="/A002995/a002995_2.pdf">Counting plane trees</a>, Unpublished manuscript, 1992. (Annotated scanned copy)
%H A002995 Bernold Fiedler, <a href="https://arxiv.org/abs/2410.05043">Scalar polynomial vector fields in real and complex time</a>, arXiv:2410.05043 [math.DS], 2024. See pp. 21, 50.
%H A002995 Bernold Fiedler, <a href="https://arxiv.org/abs/2504.20503">Real-time blow-up and connection graphs of rational vector fields on the Riemann sphere</a>, arXiv:2504.20503 [math.DS], 2025. See p. 23.
%H A002995 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 A002995 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 A002995 G. Labelle, <a href="http://dx.doi.org/10.1016/0304-3975(93)90300-I">Sur la symétrie et l'asymétrie des structures combinatoires</a>, Theor. Comput. Sci. 117, No. 1-2, 3-22 (1993).
%H A002995 P. Leroux and B. Miloudi, <a href="/A000081/a000081_2.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
%H A002995 Torsten Mütze, <a href="http://arxiv.org/abs/1404.4442">Proof of the middle levels conjecture</a>, arXiv preprint arXiv:1404.4442 [math.CO], 2014.
%H A002995 Torsten Mütze, <a href="https://arxiv.org/abs/2306.13019">A book proof of the middle levels theorem</a>, arXiv:2306.13019 [math.CO], 2023.
%H A002995 Torsten Mütze and Franziska Weber, <a href="http://arxiv.org/abs/1111.2413">Construction of 2-factors in the middle layer of the discrete cube</a>, arXiv preprint arXiv:1111.2413 [math.CO], 2011.
%H A002995 Torsten Mütze and F. Weber, <a href="http://dx.doi.org/10.1016/j.jcta.2012.06.005">Construction of 2-factors in the middle layer of the discrete cube</a>, Journal of Combinatorial Theory, Series A, 119(8) (2012), 1832-1855.
%H A002995 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 A002995 Seunghyun Seo and Heesung Shin, <a href="http://igm.univ-mlv.fr/~fpsac/FPSAC02/ARTICLES/Seo.pdf">Two involutions on vertices of ordered trees</a>, FPSAC'02 (2002). (see p_n).
%H A002995 Alexander Stoimenow, <a href="https://doi.org/10.1016/S0012-365X(99)00347-7">On the number of chord diagrams</a>, Discr. Math. 218 (2000), 209-233. See Table 1.
%H A002995 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.
%H A002995 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A002995 G.f.: 1+B(x)+(C(x^2)-C(x)^2)/2 where B is g.f. of A003239 and C is g.f. of A000108(n-1).
%F A002995 a(n) = 1/(2*(n-1))*sum{d|(n-1)}(phi((n-1)/d)*binomial(2d, d)) - A000108(n-1)/2 + (if n is even) A000108(n/2-1)/2.
%e A002995 G.f. = 1 + x + x^2 + x^3 + 2*x^4 + 3*x^5 + 6*x^6 + 14*x^7 + 34*x^8 + 95*x^9 + ...
%e A002995 a(7) = 14 = 11 + 3 because there are 11 trees with 7 nodes but three of them can be embedded in a plane in two ways. These three trees have degree sequences 4221111, 3321111, 3222111, where there are two trees with each degree sequence but in the first, the two nodes of degree two are adjacent, in the second, the two nodes of degree three are adjacent, and in the third, the node of degree three is adjacent to two nodes of degree two. - _Michael Somos_, Aug 19 2014
%p A002995 with (powseries): with (combstruct): n := 27: Order := n+2: sys := {C = Cycle(B), B = Union(Z,Prod(B,B))}: G003239 := (convert(gfseries(sys,unlabeled,x) [C(x)], polynom)) / x: G000108 := convert(taylor((1-sqrt(1-4*x)) / (2*x),x),polynom): G002995 := 1 + G003239 + (eval(G000108,x=x^2) - G000108^2)/2: A002995 := 1,1,1,seq(coeff(G002995,x^i),i=1..n); # Ulrich Schimke, Apr 05 2002
%p A002995 with(combinat): with(numtheory): m := 2: for p from 2 to 28 do s1 := 0: s2 := 0: for d from 1 to p do if p mod d = 0 then s1 := s1+phi(p/d)*binomial(m*d, d) fi: od: for d from 1 to p-1 do if gcd(m, p-1) mod d = 0 then s2 := s2+phi(d)*binomial((p*m)/d, (p-1)/d) fi: od: printf(`%d, `, (s1+s2)/(m*p)-binomial(m*p, p)/(p*(m-1)+1)) od : # _Zerinvary Lajos_, Dec 01 2006
%t A002995 a[0] = a[1] = 1; a[n_] := (1/(2*(n-1)))*Sum[ EulerPhi[(n-1)/d]*Binomial[2*d, d], {d, Divisors[n-1]}] - CatalanNumber[n-1]/2 + If[ EvenQ[n], CatalanNumber[n/2-1]/2, 0]; Table[ a[n], {n, 0, 29}] (* _Jean-François Alcover_, Mar 07 2012, from formula *)
%o A002995 (PARI) catalan(n) = binomial(2*n, n)/(n+1);
%o A002995 a(n) = if (n<2, 1, n--; sumdiv(n, d, eulerphi(n/d)*binomial(2*d, d))/(2*n) - catalan(n)/2 + if ((n-1) % 2, 0, catalan((n-1)/2)/2)); \\ _Michel Marcus_, Jan 23 2016
%Y A002995 Column k=2 of A303694 and A303864.
%Y A002995 Cf. A000055, A000108, A002996, A003239, A005354, A057502, A061417, A064640.
%K A002995 nonn,easy,nice
%O A002995 0,5
%A A002995 _N. J. A. Sloane_
%E A002995 More terms, formula from _Christian G. Bower_, Dec 15 1999
%E A002995 Name corrected ("labeled" --> "unlabeled") by _David Callan_, Aug 19 2014