

A006082


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


8



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

Also, the number of noncrossing partitions up to rotation and reflection composed of n1 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):1110, 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 nonassociative products, Bull. Amer. Math. Soc., 54 (1948), 352360. [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. 339349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. SpringerVerlag, 1974.
P. J. Stockmeyer, The charm bracelet problem and its applications, pp. 339349 of Graphs and Combinatorics (Washington, Jun 1973), Ed. by R. A. Bari and F. Harary. Lect. Notes Math., Vol. 406. SpringerVerlag, 1974. [Scanned annotated and corrected copy]
Index entries for sequences related to trees


FORMULA

a(n) = A006080(n)  A006081(n) + A126120(n2). [Stockmeyer] [Corrected by Andrey Zabolotskiy, Apr 06 2021]
a(n) = (2 * A002995(n) + A126120(n2) + A001405(n1)) / 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*n4) / (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[n1, k], EulerPhi[#]*Binomial[n*k/#, (n1)/#]&])/(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}] (* JeanFranç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



