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

1, 1, 1, 2, 3, 6, 12, 27, 65, 175, 490, 1473, 4588, 14782, 48678, 163414, 555885, 1913334, 6646728, 23278989, 82100014, 291361744, 1039758962, 3729276257, 13437206032, 48620868106, 176611864312, 643834562075, 2354902813742, 8640039835974, 31791594259244

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Also, the number of noncrossing partitions up to rotation and reflection composed of n-1 blocks of size 2. - Andrew Howroyd, May 03 2018

References

• R. W. Robinson, personal communication.
• R. W. Robinson, Efficiency of power series operations for graph counting, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..500
• David Feldman, Counting plane trees, Unpublished manuscript, 1992. (Annotated scanned copy)
• Richard Kapolnai, Gabor Domokos, and Timea Szabo, Generating spherical multiquadrangulations by restricted vertex splittings and the reducibility of equilibrium classes, Periodica Polytechnica Electrical Engineering, 56(1):11-10, 2012. Also arXiv:1206.1698 [cs.DM], 2012. See row 2 of Table 1.
• T. S. Motzkin, Relations between hypersurface cross ratios and a combinatorial formula for partitions of a polygon, for permanent preponderance and for non-associative products, 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]
• Feng Rong, A note on the topological classification of complex polynomial differential equations with only centre singularities, Journal of Difference Equations and Applications, Volume 18, Issue 11, 2012. - From _N. J. A. Sloane_, Dec 27 2012
• P. K. Stockmeyer, The charm bracelet problem and its applications, 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.
• P. J. Stockmeyer, The charm bracelet problem and its applications, 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]
• Index entries for sequences related to trees

Crossrefs

Column k=2 of A302828 and A303929.

Cf. A006079, A006080, A006081.

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

Programs

Mathematica

u[n_, k_, r_] := (r*Binomial[k*n + r, n]/(k*n + r));
e[n_, k_] := Sum[ u[j, k, 1 + (n - 2*j)*k/2], {j, 0, n/2}]
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[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;
a[n_] := T[n, 2];
Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Jun 14 2018, after Andrew Howroyd and A303929 *)

PARI

\\ from David Broadhurst, Apr 06 2022, added by N. J. A. Sloane, Apr 06 2022
{A006082(n)=my(c(n)=binomial(2*n,n));
if(n<2,1,n--;(c(n)+if(n%2,2*n*(n+2),(n+1)^2)*c(n\2)
+(n+1)*sumdiv(n,d,if(d>2,eulerphi(d)*c(n/d))))/(4*n*(n+1)));}

Formula

a(n) = A006080(n) - A006081(n) + A126120(n-2). [Stockmeyer] [Corrected by Andrey Zabolotskiy, Apr 06 2021]

a(n) = (2 * A002995(n) + A126120(n-2) + A001405(n-1)) / 4 for n > 1. - Andrey Zabolotskiy, May 24 2018

There is a compact formula from David Broadhurst - see the Pari code - N. J. A. Sloane, Apr 06 2022.

a(n) ~ 2^(2*n-4) / (sqrt(Pi) * n^(5/2)). - Vaclav Kotesovec, Jun 01 2022

Extensions

a(25) and a(26) from Robert W. Robinson, Oct 17 2006

a(27) and beyond from Andrew Howroyd, May 03 2018