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

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,4

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

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

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 *)

Prog

(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))); }

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.

Sequence in context: A061343 A057649 A104872 * A122889 A014280 A073431

Adjacent sequences: A006079 A006080 A006081 * A006083 A006084 A006085

Keyword

nonn

Author

N. J. A. Sloane

Extensions

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

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

Status

approved