

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

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]
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]


FORMULA



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];


PROG

(PARI)
{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



KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



