A005263 Number of labeled Greg trees.

1, 1, 1, 4, 32, 396, 6692, 143816, 3756104, 115553024, 4093236352, 164098040448, 7345463787136, 363154251536896, 19653476190481408, 1155636468524067328, 73364615077878838784, 5001199614295920565248, 364363128390631094137856

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

A Greg tree can be described as a tree with 2-colored nodes where only the black nodes are counted and labeled and the white nodes are of degree at least 3.

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Robert Israel, Table of n, a(n) for n = 0..359
• C. Flight, How many stemmata?, Manuscripta, 34 (1990), 122-128.
• C. Flight, How many stemmata?, Manuscripta, 34 (1990), 122-128. (Annotated scanned copy)
• C. Flight, Letter to N. J. A. Sloane, Nov 1990
• L. R. Foulds & R. W. Robinson, Determining the asymptotic number of phylogenetic trees, Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)
• V. Kurauskas, On graphs containing few disjoint excluded minors. Asymptotic number and structure of graphs containing few disjoint minors K_4, arXiv preprint arXiv:1504.08107 [math.CO], V1, Apr 30, 2015; V2, Jul 14 2019.
• Dimitris Papamichail, Angela Huang, Edward Kennedy, Jan-Lucas Ott, Andrew Miller, Georgios Papamichail, Most Compact Parsimonious Trees, arXiv preprint arXiv:1603.03315 [cs.DS], 2016.
• Index entries for sequences related to trees

Crossrefs

Cf. A005264, A005640, A048159, A048160, A052300-A052303.

Programs

Maple

E:= 1/4 -LambertW(-(1+x)*exp(-1/2)/2)^2 - 2*LambertW(-(1+x)*exp(-1/2)/2):
S:= series(E,x,21):
seq(coeff(S,x,j)*j!, j=0..20); # Robert Israel, Mar 28 2017

Mathematica

max = 18; b[x] := -1/2 - ProductLog[-Exp[-1/2]*(x+1)/2]; f[x_] := Sum[c[k]*x^k, {k, 0, max}]; sol = SolveAlways[ Normal[ Series[f[x] - (1 + b[x] - b[x]^2), {x, 0, max}]] == 0, x]; First[Table[c[k], {k, 0, max}] /. sol]*Range[0, max]! (* Jean-François Alcover, May 21 2012, from e.g.f. *)
a[ n_] := If[ n < 1, Boole[n == 0], n! SeriesCoefficient[ With[ {B =      InverseSeries[ Series[ Exp[-x] (1 + 2 x) - 1, {x, 0, n}]]}, B - B^2], n]] (* Michael Somos, Jun 07 2012 *)

PARI

{a(n) = local(A); if( n<1, n==0, for( k=1, n, A += x * O(x^k); A = truncate( (1 + x) * exp(A) - 1 - A) ); A += x * O(x^n); A -= A^2; n! * polcoeff( A, n))} /* Michael Somos, Apr 02 2007 */

Formula

E.g.f.: 1 + B(x) - B(x)^2 where B(x) is e.g.f. of A005264.

a(n) ~ n^(n-2) / (sqrt(2) * exp(n/2) * (2-exp(1/2))^(n-3/2)). - Vaclav Kotesovec, Jul 09 2013

E.g.f.: 1/4 - W(-(1+x)*exp(-1/2)/2)^2 - 2*W(-(1+x)*exp(-1/2)/2) where W is the Lambert W function. - Robert Israel, Mar 28 2017

Extensions

More terms, formula and comment from Christian G. Bower, Nov 15 1999