A005264 - OEIS

%I M3096 #106 Oct 11 2023 11:45:10

%S 1,3,22,262,4336,91984,2381408,72800928,2566606784,102515201984,

%T 4575271116032,225649908491264,12187240730230528,715392567595403520,

%U 45349581052869924352,3087516727770990992896,224691760916830871873536

%N Number of labeled rooted Greg trees with n nodes.

%C 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

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

%H Robert Israel, <a href="/A005264/b005264.txt">Table of n, a(n) for n = 1..358</a>

%H D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions.</a> arXiv:math/0501052v2 [math.CA], 2005.

%H J. Felsenstein, <a href="http://www.jstor.org/stable/2412810">The number of evolutionary trees</a>, Systematic Zoology, 27 (1978), 27-33.

%H J. Felsenstein, <a href="/A005373/a005373.pdf">The number of evolutionary trees</a>, Systematic Zoology, 27 (1978), 27-33. (Annotated scanned copy)

%H C. Flight, <a href="http://dx.doi.org/10.1484/J.MSS.3.1335">How many stemmata?</a>, Manuscripta, 34 (1990), 122-128.

%H C. Flight, <a href="/A048159/a048159.pdf">How many stemmata?</a>, Manuscripta, 34 (1990), 122-128. (Annotated scanned copy)

%H C. Flight, <a href="/A005263/a005263.pdf">Letter to N. J. A. Sloane, Nov 1990</a>

%H L. R. Foulds and R. W. Robinson, <a href="https://doi.org/10.1007/BFb0088905">Determining the asymptotic number of phylogenetic trees</a>, 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.

%H L. R. Foulds & R. W. Robinson, <a href="/A005172/a005172_1.pdf">Determining the asymptotic number of phylogenetic trees</a>, Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)

%H Armin Hoenen, Steffen Eger, and Ralf Gehrke, <a href="http://aclweb.org/anthology/W17-3402.pdf">How Many Stemmata with Root Degree k?</a>, Proceedings of the 15th Meeting on the Mathematics of Language, pp. 11-21, 2017.

%H D. J. Jeffrey, G. A. Kalugin, and N. Murdoch, <a href="https://www.uwo.ca/apmaths/faculty/jeffrey/pdfs/JeffreySYNASC2015paper17.pdf">Lagrange inversion and Lambert W</a>, Preprint, 2015 17th International Symposium on Symbolic and Numeric Algorithms for Scientific Computing (SYNASC).

%H M. Josuat-Vergès, <a href="http://arxiv.org/abs/1310.7531">Derivatives of the tree function</a>, arXiv preprint arXiv:1310.7531 [math.CO], 2013.

%H Vladimir Kruchinin, <a href="http://arxiv.org/abs/1211.3244">The method for obtaining expressions for coefficients of reverse generating functions</a>, arXiv:1211.3244 [math.CO], 2012.

%H Paul Laubie, <a href="https://arxiv.org/abs/2309.05552">Combinatorics of pre-Lie products sharing a Lie bracket</a>, arXiv:2309.05552 [math.QA], 2023. See pp. 1, 5.

%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>

%H N. S. Wedd, <a href="/A005264/a005264.pdf">Letter to N. J. A. Sloane, N.D.</a>

%H <a href="/index/Res#revert">Index entries for reversions of series</a>

%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F Exponential reversion of A157142 with offset 1. - _Michael Somos_, Mar 26 2011

%F 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

%F E.g.f. A(x) = y satisfies y' = (1 + 2*y) / ((1 - 2*y) * (1 + x)). - _Michael Somos_, Mar 26 2011

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

%F From _Peter Bala_, Sep 08 2011: (Start)

%F 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).

%F 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].

%F (End)

%F 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

%F 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

%F a(n) ~ n^(n-1) / (sqrt(2) * exp(n/2) * (2-exp(1/2))^(n-1/2)). - _Vaclav Kotesovec_, Jul 09 2013

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

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

%p 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;

%p (n-1)*T(n-1,k-1)+(3*n-k-4)*T(n-1,k)-(k+1)*T(n-1,k+1) end:

%p A005264 := proc(n) add(T(n,k)*(-1)^k*2^(n-k-1), k=0..n-1) end;

%p seq(A005264(n),n=1..17); # _Peter Luschny_, Nov 10 2012

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

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

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

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

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

%o (Sage)

%o @CachedFunction

%o def T(n,k):

%o     if k==0 and (n==0 or n==1): return 1

%o     if k<0 or k>n: return 0

%o     return (n-1)*T(n-1,k-1)+(3*n-k-4)*T(n-1,k)-(k+1)*T(n-1,k+1)

%o A005264 = lambda n: add(T(n,k)*(-1)^k*2^(n-k-1) for k in (0..n-1))

%o [A005264(n) for n in (1..17)]  # _Peter Luschny_, Nov 10 2012

%Y Inverse Stirling transform of A005172 (hence corrected and extended). - _John W. Layman_

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

%K nonn,nice,easy

%O 1,2

%A _N. J. A. Sloane_