|
| |
|
|
A005172
|
|
Number of labeled rooted trees of subsets of an n-set.
(Formerly M3648)
|
|
10
|
|
|
|
1, 4, 32, 416, 7552, 176128, 5018624, 168968192, 6563282944, 288909131776, 14212910809088, 772776684683264, 46017323176296448, 2978458881388183552, 208198894960190160896, 15631251601179130462208, 1254492810303112820555776, 107174403941451434687463424, 9711022458989438255300083712
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,2
|
|
|
COMMENTS
|
Each node is a subset of the labeled set {1,...,n}. If the subset node is empty, it must have at least two children.
|
|
|
REFERENCES
|
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
R. P. Stanley, Enumerative Combinatorics, Cambridge, Vol. 2, 1999; see Problem 5.26.
|
|
|
LINKS
|
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
|
|
|
FORMULA
|
E.g.f.: -1/2 - LambertW ( - exp( -1/2 + x) / 2 ).
E.g.f.: A(x) = 1 + Integral A(x)*(1 + A(x))^2 dx. - Paul D. Hanna, Sep 06 2008
The generating function A(x) = x+4*x^2/2!+32*x^3/3!+... satisfies the autonomous differential equation A'(x) = (1+2*A)/(1-2*A) with A(0) = 0. Hence the inverse function A^-1(x) = Integral_{t = 0..x} (1-2*t)/(1+2*t) dt = log(1+2*x)-x.
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((1+2*x)/(1-2*x)*g(x)). Compare with A032188.
Applying [Bergeron et al., Theorem 1] to the result x = Integral_{t = 0..A(x)} 1/phi(t) dt, where phi(t) = (1+2*t)/(1-2*t) = 1+4*t+8*t^2+16*t^3+32*t^4+... leads to the following combinatorial interpretation for this sequence: a(n) gives the number of plane increasing trees on n vertices where each vertex of outdegree k >= 1 can be colored in 2^(k+1) ways. An example is given below. (End)
a(n) = Sum_{k=1..n-1} (n+k-1)!*Sum_{j=1..k} (-1)^j/(k-j)!*Sum_{i=0..j} (-1)^i* 2^(n-i+j-1)*Stirling1(n-i+j-1,j-i)/((n-i+j-1)!*i!), n>1, a(1)=1. - Vladimir Kruchinin, Jan 30 2012
Let p(n,w) = w*Sum_{k=0..n-1}((-1)^k*E2(n-1,k)*w^k)/(1+w)^(2*n-1), E2 the second-order Eulerian numbers as defined by Knuth, then a(n) = -p(n,-1/2). - Peter Luschny, Nov 10 2012
G.f.: 1/Q(0), where Q(k)= 1 - 2*(k+1)*x - 2*x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 01 2013
a(n) = 2*a(n-1) + Sum_{j=1..n-1} binomial(n,j)*a(j)*a(n-j) for n>1, a(1) = 1. - Peter Luschny, May 24 2017
a(1) = 1; a(n) = n! * [x^n] exp(x + Sum_{k=1..n-1} a(k)*x^k/k!). - Ilya Gutkovskiy, Oct 18 2017
|
|
|
EXAMPLE
|
x + 4*x^2 + 32*x^3 + 416*x^4 + 7552*x^5 + 176128*x^6 + 5018624*x^7 + ...
D^3(1) = 32*(12*x^2+28*x+13)/(2*x-1)^6. Evaluated at x = 0 this gives a(4) = 416.
a(3) = 32: The 32 increasing plane trees on 3 vertices with vertices of outdegree k coming in 2^(k+1) colors are
.
1(x4 colors) 1(x8 colors) 1(x8 colors)
| / \ / \
2(x4 colors) 2 3 3 2
|
3
.
Totals: 16 + 8 + 8 = 32. (End)
|
|
|
MAPLE
|
A005172_list := proc(len) local A, n; A[1] := 1; for n from 2 to len do
A[n] := 2*A[n-1] + add(binomial(n, j)*A[j]*A[n-j], j=1..n-1) od:
|
|
|
MATHEMATICA
|
max = 16; g[x_] := -1/2 - ProductLog[-E^(-1/2 + x)/2]; Drop[ CoefficientList[ Series[ g[x], {x, 0, max}], x]*Range[0, max]!, 1](* Jean-François Alcover, Nov 17 2011, after 1st e.g.f. *)
a[ n_] := If[ n < 0, 0, n! SeriesCoefficient[ -1/2 - ProductLog[ -Exp[ -1/2 + z] / 2], {z, 0, n}]] (* Michael Somos, Jun 07 2012 *)
a[1] = 1; a[n_] := (Sum[(n + k - 1)!*Sum[(-1)^j/(k - j)!*Sum[(-1)^i*2^(n - i + j - 1)*StirlingS1[n - i + j - 1, j - i]/((n - i + j - 1)!*i!), {i, 0, j}], {j, 1, k}], {k, 1, n - 1}]);
Eulerian2[n_, k_] := Eulerian2[n, k] = If[k == 0, 1, If[k == n, 0, Eulerian2[n-1, k] (k + 1) + Eulerian2[n - 1, k - 1] (2n - k - 1)]]; A005172[n_] := Sum[Eulerian2[n - 1, k] 2^(2 n - k - 2), {k, 0, n - 1}]; Table[A005172[n], {n, 19}] (* Peter Luschny, Jun 24 2018 *)
|
|
|
PROG
|
(PARI) {a(n)=local(A=1+x); for(i=0, n, A=1+intformal(A*(1+A+x*O(x^n))^2)); n!*polcoeff(A, n)} \\ Paul D. Hanna, Sep 06 2008
(Maxima) a(n):=if n=1 then 1 else (sum((n+k-1)!*sum((-1)^j/(k-j)!*sum((-1)^i*2^(n-i+j-1)*stirling1(n-i+j-1, j-i)/((n-i+j-1)!*i!), i, 0, j), j, 1, k), k, 1, n-1)); /* Vladimir Kruchinin, Jan 30 2012 */
(Sage)
@CachedFunction
def eulerian2(n, k):
if k==0: return 1
elif k==n: return 0
return eulerian2(n-1, k)*(k+1)+eulerian2(n-1, k-1)*(2*n-k-1)
A005172 = lambda n: add(eulerian2(n-1, k)*2^(2*n-k-2) for k in (0..n-1))
(PARI) N=66; x='x+O('x^N);
Q(k)=if(k>N, 1, 1-2*(k+1)*x-2*x*(k+1)/Q(k+1));
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,nice,easy
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
