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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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.

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, 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 & 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]

Index entries for sequences related to trees

Index entries for sequences related to rooted trees

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) = int {t = 0..x} (1-2*t)/(1+2*t) = 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 = int {t = 0..A(x)} 1/phi(t), 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. - Peter Bala, Sep 06 2011

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.

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

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

Cf. A005640, A032188.

See A225170 for another version.

Sequence in context: A191459 A184359 A229548 * A298694 A222685 A140178

Adjacent sequences:  A005169 A005170 A005171 * A005173 A005174 A005175

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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 18 22:37 EDT 2018. Contains 316327 sequences. (Running on oeis4.)