|
| |
|
|
A005172
|
|
Number of labeled rooted trees of subsets of an n-set.
(Formerly M3648)
|
|
3
| |
|
|
1, 4, 32, 416, 7552, 176128, 5018624, 168968192, 6563282944, 288909131776, 14212910809088, 772776684683264, 46017323176296448, 2978458881388183552, 208198894960190160896, 15631251601179130462208
(list; graph; refs; listen; history; 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
| 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.
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.
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, Table of n, a(n) for n=1..30
F. Bergeron, Ph. Flajolet and B. Salvy, Varieties of Increasing Trees, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1922, pp. 24-48. D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA]
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. [From Paul D. Hanna (pauldhanna(AT)juno.com), 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) = ln(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) counts 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, Sept 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. [From Vladimir Kruchinin, Jan 30 2012]
|
|
|
EXAMPLE
| 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.............
|
|
|
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](* From Jean-François Alcover, Nov 17 2011, after 1st e.g.f. *)
|
|
|
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)} [From Paul D. Hanna (pauldhanna(AT)juno.com), 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)); [From Vladimir Kruchinin, Jan 30 2012]
|
|
|
CROSSREFS
| Cf. A005640.
John Layman (layman(AT)calvin.math.vt.edu) observes that this is the Stirling transform of A005264. A032188.
Sequence in context: A127670 A191459 A184359 * A140178 A088991 A009668
Adjacent sequences: A005169 A005170 A005171 * A005173 A005174 A005175
|
|
|
KEYWORD
| nonn,nice,easy
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
| |
|
|
