A005172 Number of labeled rooted trees of subsets of an n-set.
1, 4, 32, 416, 7552, 176128, 5018624, 168968192, 6563282944, 288909131776, 14212910809088, 772776684683264, 46017323176296448, 2978458881388183552, 208198894960190160896, 15631251601179130462208, 1254492810303112820555776, 107174403941451434687463424, 9711022458989438255300083712
Offset: 1
Examples
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.
From _Peter Bala_, Sep 06 2011: (Start)
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)
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
- T. D. Noe and Vaclav Kotesovec, Table of n, a(n) for n = 1..240 (terms 1..30 from T. D. Noe)
- 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.
- F. Chapoton, F. Hivert, and J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.
- D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions, arXiv:math/0501052 [math.CA], 2005.
- 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 and R. W. Robinson, Determining the asymptotic number of phylogenetic trees, Lecture Notes in Math., 829 (1980), 110-126. (Annotated scanned copy)
- J. P. Hayes, Enumeration of fanout-free Boolean functions, J. ACM, 23 (1976), 700-709.
- F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10.
- F. R. McMorris and T. Zaslavsky, The number of cladistic characters, Math. Biosciences, 54 (1981), 3-10. [Annotated scanned copy]
- István Mezo, Victor H. Moll, José L. Ramírez, and Diego Villamizar, On the r-Derangements of type B, arXiv:2103.04151 [math.CO], 2021.
- Index entries for sequences related to trees
- Index entries for sequences related to rooted trees
Programs
-
Maple
with(combinat); A005172 := n -> add(eulerian2(n-1,k)*2^(2*n-k-2),k=0..n-1): seq(A005172(n), n=1..16); # Peter Luschny, Nov 10 2012 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: convert(A,list) end: A005172_list(19); # Peter Luschny, May 24 2017
-
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}]); Array[a, 20] (* Jean-François Alcover, Jun 24 2018, after Vladimir Kruchinin *) 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 *) -
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 */
-
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 -
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)); gf=1/Q(0); Vec(gf) \\ Joerg Arndt, May 01 2013 -
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)) [A005172(n) for n in (1..16)] # Peter Luschny, Nov 10 2012
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
From Peter Bala, Sep 06 2011: (Start)
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
a(n) ~ (2/(2*log(2)-1))^(n-1/2)*n^(n-1)/exp(n). - Vaclav Kotesovec, Jan 05 2013
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
Comments