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.
John W. Layman observes that this is the Stirling transform of A005264.
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.
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
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.
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)
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 *)
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))
[A005172(n) for n in (1..16)] # Peter Luschny, Nov 10 2012
(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
CROSSREFS
KEYWORD
nonn,nice,easy
AUTHOR
STATUS
approved