login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A005264 Number of labeled rooted Greg trees with n nodes.
(Formerly M3096)
11
1, 3, 22, 262, 4336, 91984, 2381408, 72800928, 2566606784, 102515201984, 4575271116032, 225649908491264, 12187240730230528, 715392567595403520, 45349581052869924352, 3087516727770990992896, 224691760916830871873536 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

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

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, 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, 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.

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

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

EXAMPLE

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

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 *)

PROG

(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 */

(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 */

(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

CROSSREFS

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

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

Sequence in context: A054595 A054594 A242794 * A195512 A052892 A155806

Adjacent sequences:  A005261 A005262 A005263 * A005265 A005266 A005267

KEYWORD

nonn,nice,easy

AUTHOR

N. J. A. Sloane

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 22 18:53 EST 2019. Contains 319365 sequences. (Running on oeis4.)