|
| |
|
|
A032188
|
|
Number of labeled series-reduced mobiles (circular rooted trees) with n leaves (root has degree 0 or >=2).
|
|
11
| |
|
|
1, 1, 5, 41, 469, 6889, 123605, 2620169, 64074901, 1775623081, 54989743445, 1882140936521, 70552399533589, 2874543652787689, 126484802362553045, 5977683917752887689, 301983995802099667861, 16239818347465293071401
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,3
|
|
|
COMMENTS
| With offset 0, a(n) = number of partitions of the multiset {1,1,2,2,...,n,n} into lists of strictly decreasing lists, called blocks, such that the concatenation of all blocks in a list has the Stirling property: all entries between the two occurrences of i exceed i, 1<=i<=n. For example, with slashes separating blocks, a(2) = 5 counts 1/1/2/2; 1/2/2/1; 2/2/1/1; 1/2/2 1; 2/2 1/1, but not, for instance, 2 1/2/1 because it fails the Stirling test for i=2.
- David Callan Nov 21 2011
|
|
|
LINKS
| 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]
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 89
Index entries for sequences related to mobiles
|
|
|
FORMULA
| Doubles (index 2+) under "CIJ" (necklace, indistinct, labeled) transform.
E.g.f. A(x) satisfies ln(1-A(x))+2*A(x)-x = 0. - Vladeta Jovovic (vladeta(AT)eunet.rs), Dec 06 2002
With offset 0, second Eulerian transform of the powers of 2 [A000079]. See A001147 for definition of SET. - Ross La Haye (rlahaye(AT)new.rr.com), Feb 14 2005
From Peter Bala, Sep 05 2011: (Start)
The generating function A(x) satisfies the autonomous differential equation A'(x) = (1-A)/(1-2*A) with A(0) = 0. Hence the inverse function A^-1(x) = int {t = 0..x} (1-2*t)/(1-t) = 2*x+ln(1-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-x)/(1-2*x)*g(x)). Compare with A006351.
Applying [Bergeron et al, Theorem 1] to the result x = int {t = 0..A(x)} 1/phi(t), where phi(t) = (1-t)/(1-2*t) = 1+t+2*t^2+4*t^3+8*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. (End)
The integral from 0 to infinity w.r.t. w of exp(-2w)(1-z*w)^(-1/z) gives an o.g.f. for the series with offset 0. Consequently, a(n)= sum(j=1 to infinity): St1d(n,j)/(2^(n+j-1)) where St1d(n,j) is the j-th element of the n-th diagonal of A132393 with offset=1; e.g. a(3)= 5 = 0/2^3 + 2/2^4 + 11/2^5 + 35/2^6 + 85/2^7 + .... - Tom Copeland, Sep 15 2011
A signed o.g.f., with Γ(v,x) the incomplete gamma function (see A111999 with u=1), is g(z) = (2/z)^(-(1/z)-1) exp(2/z) Γ((1/z)+1,2/z)/z . - Tom Copeland, Sep 16 2011
With offset 0, a(n) = Sum[T(n+k,k), k=1..n] where T(n,k) are the associated Stirling numbers of the first kind (A008306). For example, a(3) = 41 = 6 + 20 + 15. - David Callan Nov 21 2011
a(n)=sum(k=0..n-1, (n+k-1)!*sum(j=0..k, 1/(k-j)!*sum(l=0..j, (2^l*(-1)^(n+l+1)*stirling1(n-l+j-1,j-l))/(l!*(n-l+j-1)!)))), n>0. [From Vladimir Kruchinin, Feb 06 2012]
|
|
|
EXAMPLE
| D^3(1) = (24*x^2-64*x+41)/(2*x-1)^6. Evaluated at x = 0 this gives a(4) = 41.
a(3) = 5: Denote the colors of the vertices by the letters a,b,c, .... The 5 possible increasing plane trees on 3 vertices with vertices of outdegree k coming in 2^(k-1) colors are ............................................... ...1a.......1a.......1b........1a........1b.... ...|......./.\....../..\....../..\....../..\... ...2a.....2...3....2....3....3....2....3....2.. ...|........................................... ...3...........................................
|
|
|
MAPLE
| Order := 20; t1 := solve(series((ln(1-A)+2*A), A)=x, A); A000311 := n->n!*coeff(t1, x, n);
|
|
|
MATHEMATICA
| For[y=x+O[x]^21; oldy=0, y=!=oldy, oldy=y; y=((1-y)Log[1-y]+x*y+y-x)/(2y-1), Null]; Table[n!Coefficient[y, x, n], {n, 1, 20}]
|
|
|
PROG
| (Maxima) a(n):=sum((n+k-1)!*sum(1/(k-j)!*sum((2^l*(-1)^(n+l+1)*stirling1(n-l+j-1, j-l))/(l!*(n-l+j-1)!), l, 0, j), j, 0, k), k, 0, n-1); [From Vladimir Kruchinin, Feb 06 2012]
|
|
|
CROSSREFS
| Cf. A006351.
Sequence in context: A047735 A096364 A049119 * A143415 A056545 A009755
Adjacent sequences: A032185 A032186 A032187 * A032189 A032190 A032191
|
|
|
KEYWORD
| nonn,eigen,changed
|
|
|
AUTHOR
| Christian G. Bower (bowerc(AT)usa.net)
|
| |
|
|
