cp's OEIS Frontend

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

%I A006082 M0798 #73 Mar 21 2024 21:09:57
%S A006082 1,1,1,2,3,6,12,27,65,175,490,1473,4588,14782,48678,163414,555885,
%T A006082 1913334,6646728,23278989,82100014,291361744,1039758962,3729276257,
%U A006082 13437206032,48620868106,176611864312,643834562075,2354902813742,8640039835974,31791594259244
%N A006082 Number of labeled projective plane trees (or "flat" trees) with n nodes.
%C A006082 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 A006082 R. W. Robinson, personal communication.
%D A006082 R. W. Robinson, Efficiency of power series operations for graph counting, AGRC Grant, Math. Dept., Univ. Newcastle, Australia, 1982.
%D A006082 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006082 Andrew Howroyd, <a href="/A006082/b006082.txt">Table of n, a(n) for n = 1..500</a>
%H A006082 David Feldman, <a href="/A002995/a002995_2.pdf">Counting plane trees</a>, Unpublished manuscript, 1992. (Annotated scanned copy)
%H A006082 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 A006082 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 A006082 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 A006082 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 A006082 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 A006082 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A006082 a(n) = A006080(n) - A006081(n) + A126120(n-2). [Stockmeyer] [Corrected by _Andrey Zabolotskiy_, Apr 06 2021]
%F A006082 a(n) = (2 * A002995(n) + A126120(n-2) + A001405(n-1)) / 4 for n > 1. - _Andrey Zabolotskiy_, May 24 2018
%F A006082 There is a compact formula from _David Broadhurst_ - see the Pari code - _N. J. A. Sloane_, Apr 06 2022.
%F A006082 a(n) ~ 2^(2*n-4) / (sqrt(Pi) * n^(5/2)). - _Vaclav Kotesovec_, Jun 01 2022
%t A006082 u[n_, k_, r_] := (r*Binomial[k*n + r, n]/(k*n + r));
%t A006082 e[n_, k_] := Sum[ u[j, k, 1 + (n - 2*j)*k/2], {j, 0, n/2}]
%t A006082 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 A006082 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 A006082 a[n_] := T[n, 2];
%t A006082 Table[a[n], {n, 0, 30}] (* _Jean-François Alcover_, Jun 14 2018, after _Andrew Howroyd_ and A303929 *)
%o A006082 (PARI)
%o A006082 \\ from _David Broadhurst_, Apr 06 2022, added by _N. J. A. Sloane_, Apr 06 2022
%o A006082 {A006082(n)=my(c(n)=binomial(2*n,n));
%o A006082 if(n<2,1,n--;(c(n)+if(n%2,2*n*(n+2),(n+1)^2)*c(n\2)
%o A006082 +(n+1)*sumdiv(n,d,if(d>2,eulerphi(d)*c(n/d))))/(4*n*(n+1)));}
%Y A006082 Column k=2 of A302828 and A303929.
%Y A006082 Cf. A006079, A006080, A006081.
%Y A006082 Cf. A002995 (noncrossing partitions into pairs up to rotations only), A126120, A001405, A185100.
%K A006082 nonn
%O A006082 1,4
%A A006082 _N. J. A. Sloane_
%E A006082 a(25) and a(26) from _Robert W. Robinson_, Oct 17 2006
%E A006082 a(27) and beyond from _Andrew Howroyd_, May 03 2018