A005264 Number of labeled rooted Greg trees with n nodes.

1, 3, 22, 262, 4336, 91984, 2381408, 72800928, 2566606784, 102515201984, 4575271116032, 225649908491264, 12187240730230528, 715392567595403520, 45349581052869924352, 3087516727770990992896, 224691760916830871873536

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn
• nice
• easy

Comments

A rooted Greg tree can be described as a rooted tree with 2-colored nodes where only the black nodes are counted and labeled and the white nodes have at least 2 children. - Christian G. Bower, Nov 15 1999

Examples

			G.f. = x + 3*x^2 + 22*x^3 + 262*x^4 + 4336*x^5 + 91984*x^6 + 2381408*x^7 + ...
		

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 = 1..358
• D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2005.
• J. Felsenstein, The number of evolutionary trees, Systematic Zoology, 27 (1978), 27-33.
• J. Felsenstein, The number of evolutionary trees, Systematic Zoology, 27 (1978), 27-33. (Annotated scanned copy)
• 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 and R. W. Robinson, Determining the asymptotic number of phylogenetic trees, pp. 110-126 of Combinatorial Mathematics VII (Newcastle, August 1979), ed. R. W. Robinson, G. W. Southern and W. D. Wallis. Lect. Notes in Math., 829. Springer, 1980.
• L. R. Foulds & R. W. Robinson, Determining the asymptotic number of phylogenetic trees, Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)
• Armin Hoenen, Steffen Eger, and Ralf Gehrke, How Many Stemmata with Root Degree k?, Proceedings of the 15th Meeting on the Mathematics of Language, pp. 11-21, 2017.
• D. J. Jeffrey, G. A. Kalugin, and N. Murdoch, Lagrange inversion and Lambert W, Preprint, 2015 17th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC).
• M. Josuat-Vergès, Derivatives of the tree function, arXiv preprint arXiv:1310.7531 [math.CO], 2013.
• Vladimir Kruchinin, The method for obtaining expressions for coefficients of reverse generating functions, arXiv:1211.3244 [math.CO], 2012.
• Paul Laubie, Combinatorics of pre-Lie products sharing a Lie bracket, arXiv:2309.05552 [math.QA], 2023. See pp. 1, 5.
• N. J. A. Sloane, Transforms
• N. S. Wedd, Letter to N. J. A. Sloane, N.D.
• Index entries for reversions of series
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Crossrefs

Inverse Stirling transform of A005172 (hence corrected and extended). - John W. Layman

Cf. A005263, A048159, A048160, A052300, A052301, A052302, A052303, A157142.

Programs

Maple

T := proc(n,k) option remember; if k=0 and (n=0 or n=1) then return(1) fi; if k<0 or k>n then return(0) fi;
(n-1)*T(n-1,k-1)+(3*n-k-4)*T(n-1,k)-(k+1)*T(n-1,k+1) end:
A005264 := proc(n) add(T(n,k)*(-1)^k*2^(n-k-1), k=0..n-1) end;
seq(A005264(n),n=1..17); # Peter Luschny, Nov 10 2012

Mathematica

max = 17; f[x_] := -1/2 - ProductLog[-E^(-1/2)*(x + 1)/2]; Rest[ CoefficientList[ Series[ f[x], {x, 0, max}], x]*Range[0, max]!] (* Jean-François Alcover, May 23 2012, after Peter Bala *)
a[ n_] := If[ n < 1, 0, n! SeriesCoefficient[ InverseSeries[ Series[ Exp[-x] (1 + 2 x) - 1, {x, 0, n}]], n]]; (* Michael Somos, Jun 07 2012 *)

Maxima

a(n):=if n=1 then 1 else sum((n+k-1)!*sum(1/(k-j)!*sum(1/(l!*(j-l)!)*sum(((-1)^(i+l)*l^i*binomial(l,n+j-i-1)*2^(n+j-i-1))/i!,i,0,n+j-1),l,1,j),j,1,k),k,1,n-1); /* Vladimir Kruchinin, May 04 2012 */

PARI

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

PARI

{a(n) = if( n<1, 0, n! * polcoeff( serreverse( exp( -x + x * O(x^n) ) * (1 + 2*x) - 1), n))}; /* Michael Somos, Mar 26 2011 */

Sage

@CachedFunction
def T(n,k):
    if k==0 and (n==0 or n==1): return 1
    if k<0 or k>n: return 0
    return (n-1)*T(n-1,k-1)+(3*n-k-4)*T(n-1,k)-(k+1)*T(n-1,k+1)
A005264 = lambda n: add(T(n,k)*(-1)^k*2^(n-k-1) for k in (0..n-1))
[A005264(n) for n in (1..17)]  # Peter Luschny, Nov 10 2012

Formula

Exponential reversion of A157142 with offset 1. - Michael Somos, Mar 26 2011

The REVEGF transform of the odd numbers [1,3,5,7,9,11,...] is [1, -3, 22, -262, 4336, -91984, 2381408, ...] - N. J. A. Sloane, May 26 2017

E.g.f. A(x) = y satisfies y' = (1 + 2*y) / ((1 - 2*y) * (1 + x)). - Michael Somos, Mar 26 2011

E.g.f. A(x) satisfies (1 + x) * exp(A(x)) = 1 + 2 * A(x).

From Peter Bala, Sep 08 2011: (Start)

A(x) satisfies the separable differential equation A'(x) = exp(A(x))/(1-2*A(x)) with A(0) = 0. Thus the inverse function A^-1(x) = int {t = 0..x} (1-2*t)/exp(t) = exp(-x)*(2*x+1)-1 = x-3*x^2/2!+5*x^3/3!-7*x^4/4!+.... A(x) = -1/2-LambertW(-exp(-1/2)*(x+1)/2).

The expansion of A(x) can be found by inverting the above integral using the method of [Dominici, Theorem 4.1] to arrive at the result a(n) = D^(n-1)(1) evaluated at x = 0, where D denotes the operator g(x) -> d/dx(exp(x)/(1-2*x)*g(x)). Compare with [Dominici, Example 9].

(End)

a(n)=sum(k=1..n-1, (n+k-1)!*sum(j=1..k, 1/(k-j)!*sum(l=1..j, 1/(l!*(j-l)!)* sum(i=0..n+j-1, ((-1)^(i+l)*l^i*binomial(l,n+j-i-1)*2^(n+j-i-1))/i!)))), n>1, a(1)=1. - Vladimir Kruchinin, May 04 2012

Let T(n,k) = 1 if k=0 and (n=0 or n=1); T(n,k) = 0 if k<0 or k>n; and otherwise T(n,k) = (n-1)*T(n-1,k-1)+(3*n-k-4)*T(n-1,k)-(k+1)*T(n-1,k+1). Define polynomials p(n,w) = w^n*sum_{k=0..n-1}(T(n,k)*w^k)/(1+w)^(2*n-1), then a(n) = (-1)^n*p(n,-1/2). - Peter Luschny, Nov 10 2012

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

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