login
Number of labeled projective plane trees (or "flat" trees) with n nodes.
(Formerly M0798)
8

%I M0798 #73 Mar 21 2024 21:09:57

%S 1,1,1,2,3,6,12,27,65,175,490,1473,4588,14782,48678,163414,555885,

%T 1913334,6646728,23278989,82100014,291361744,1039758962,3729276257,

%U 13437206032,48620868106,176611864312,643834562075,2354902813742,8640039835974,31791594259244

%N Number of labeled projective plane trees (or "flat" trees) with n nodes.

%C Also, the number of noncrossing partitions up to rotation and reflection composed of n-1 blocks of size 2. - _Andrew Howroyd_, May 03 2018

%D R. W. Robinson, personal communication.

%D R. W. Robinson, Efficiency of power series operations for graph counting, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Andrew Howroyd, <a href="/A006082/b006082.txt">Table of n, a(n) for n = 1..500</a>

%H David Feldman, <a href="/A002995/a002995_2.pdf">Counting plane trees</a>, Unpublished manuscript, 1992. (Annotated scanned copy)

%H Richard Kapolnai, Gabor Domokos, and Timea Szabo, <a href="http://arxiv.org/abs/1206.1698">Generating spherical multiquadrangulations by restricted vertex splittings and the reducibility of equilibrium classes</a>, Periodica Polytechnica Electrical Engineering, 56(1):11-10, 2012. Also arXiv:1206.1698 [cs.DM], 2012. See row 2 of Table 1.

%H T. S. Motzkin, <a href="http://dx.doi.org/10.1090/S0002-9904-1948-09002-4 ">Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products</a>, Bull. Amer. Math. Soc., 54 (1948), 352-360. [The sequence is mentioned on page 355, but because of a miscalculation it is given, incorrectly, as 1, 1, 1, 2, 3, 6, 12, 25. Thanks to _David Broadhurst_ for this information. - _N. J. A. Sloane_, Apr 06 2022]

%H Feng Rong, <a href="https://doi.org/10.1080/10236198.2012.721782">A note on the topological classification of complex polynomial differential equations with only centre singularities</a>, Journal of Difference Equations and Applications, Volume 18, Issue 11, 2012. - From _N. J. A. Sloane_, Dec 27 2012

%H P. K. Stockmeyer, <a href="https://doi.org/10.1007/BFb0066456">The charm bracelet problem and its applications</a>, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974.

%H P. J. Stockmeyer, <a href="/A006078/a006078.pdf">The charm bracelet problem and its applications</a>, pp. 339-349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. Springer-Verlag, 1974. [Scanned annotated and corrected copy]

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F a(n) = A006080(n) - A006081(n) + A126120(n-2). [Stockmeyer] [Corrected by _Andrey Zabolotskiy_, Apr 06 2021]

%F a(n) = (2 * A002995(n) + A126120(n-2) + A001405(n-1)) / 4 for n > 1. - _Andrey Zabolotskiy_, May 24 2018

%F There is a compact formula from _David Broadhurst_ - see the Pari code - _N. J. A. Sloane_, Apr 06 2022.

%F a(n) ~ 2^(2*n-4) / (sqrt(Pi) * n^(5/2)). - _Vaclav Kotesovec_, Jun 01 2022

%t u[n_, k_, r_] := (r*Binomial[k*n + r, n]/(k*n + r));

%t e[n_, k_] := Sum[ u[j, k, 1 + (n - 2*j)*k/2], {j, 0, n/2}]

%t c[n_, k_] := If[n == 0, 1, (DivisorSum[n, EulerPhi[n/#]*Binomial[k*#, #]&] + DivisorSum[GCD[n-1, k], EulerPhi[#]*Binomial[n*k/#, (n-1)/#]&])/(k*n) - Binomial[k*n, n]/(n*(k - 1) + 1)];

%t T[n_, k_] := (1/2)*(c[n, k] + If[n == 0, 1, If[OddQ[k], If[OddQ[n], 2*u[ Quotient[n, 2], k, (k + 1)/2], u[n/2, k, 1] + u[n/2 - 1, k, k]], e[n, k] + If[OddQ[n], u[Quotient[n, 2], k, k/2]]]/2]) /. Null -> 0;

%t a[n_] := T[n, 2];

%t Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jun 14 2018, after _Andrew Howroyd_ and A303929 *)

%o (PARI)

%o \\ from _David Broadhurst_, Apr 06 2022, added by _N. J. A. Sloane_, Apr 06 2022

%o {A006082(n)=my(c(n)=binomial(2*n,n));

%o if(n<2,1,n--;(c(n)+if(n%2,2*n*(n+2),(n+1)^2)*c(n\2)

%o +(n+1)*sumdiv(n,d,if(d>2,eulerphi(d)*c(n/d))))/(4*n*(n+1)));}

%Y Column k=2 of A302828 and A303929.

%Y Cf. A006079, A006080, A006081.

%Y Cf. A002995 (noncrossing partitions into pairs up to rotations only), A126120, A001405, A185100.

%K nonn

%O 1,4

%A _N. J. A. Sloane_

%E a(25) and a(26) from _Robert W. Robinson_, Oct 17 2006

%E a(27) and beyond from _Andrew Howroyd_, May 03 2018