|
| |
|
|
A029768
|
|
Number of increasing mobiles with n elements.
|
|
14
|
|
|
|
0, 1, 1, 2, 7, 36, 245, 2076, 21059, 248836, 3356609, 50896380, 856958911, 15864014388, 320245960333, 7001257954796, 164792092647355, 4154906594518116, 111719929072986521, 3191216673497748444
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,4
|
|
|
COMMENTS
|
A labeled tree of size n is a rooted tree on n nodes that are labeled by distinct integers from the set {1,...,n}. An increasing tree is a labeled tree such that the sequence of labels along any branch starting at the root is increasing.
a(n) counts increasing trees with cyclically ordered branches.
a(n+1) counts the non-plane (where the subtrees stemming from a node are not ordered between themselves) increasing trees on n nodes where the nodes of outdegree k come in k+1 colors. An example is given below. The number of plane increasing trees on n nodes where the nodes of outdegree k come in k+1 colors is given by the triple factorial numbers A008544. - Peter Bala, Aug 30 2011
|
|
|
REFERENCES
|
F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 392.
|
|
|
LINKS
|
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.
|
|
|
FORMULA
|
Bergeron et al. give several formulas. Shifts left under "CIJ" (necklace, indistinct, labeled) transform.
E.g.f.: A(x) =
x + (1/2)*x^2 + (1/3)*x^3 + (7/24)*x^4 + (3/10)*x^5 + (49/144)*x^6 + (173/420)*x^7 + (21059/40320)*x^8 + (8887/12960)*x^9 + ...
and satisfies the differential equation A'(x)=log(1/(1-A(x)))+1. - Vladimir Kruchinin, Jan 22 2011
E.g.f. A(x) satisfies: A''(x) = A'(x) * exp(A'(x)-1). - Paul D. Hanna, Apr 17 2015
E.g.f. A(x) satisfies e*(Ei(1,A'(x)) - Ei(1,1)) = integral(s = 1 .. A'(x), exp(1-s)/s ds) = -x.
a(n) = e^(1-n)*limit(w -> 1, (d^(n-2)/dw^(n-2))(((w-1)/(Ei(1,1)-Ei(1,w)))^(n-1))) for n >= 2. (End)
a(n) = sum(i=1..n-2,binomial(n-2,i)*a(i)*a(n-i))+a(n-1), a(0)=0, a(1)=1. - Vladimir Kruchinin, Jan 24 2011
The following remarks refer to the interpretation of this sequence as counting increasing trees where the nodes of outdegree k come in k+1 colors. Thus we work with the generating function B(x) = A'(x)-1 = x + 2*x^2/2!+7*x^3/3!+36*x^4/4!+.... The degree function phi(x) (see [Bergeron et al.] for definition) for this variety of trees is phi(x) = 1+2*x+3*x^2/2!+4*x^3/3!+5*x^4/4!+... = (1+x)*exp(x). The generating function B(x) satisfies the autonomous differential equation B' = phi(B(x)) with initial condition B(0) = 0. It follows that the inverse function B(x)^(-1) may be expressed as an integral B(x)^(-1) = int {t = 0..x} 1/phi(t) dt = int {t = 0..x} exp(-t)/(1+t) dt. Applying [Dominici, Theorem 4.1] to invert the integral produces the result B(x) = sum {n>=1} D^(n-1)[(1+x)*exp(x)](0)*x^n/n!, where the nested derivative D^n[f](x) of a function f(x) is defined recursively as D^0[f](x) = 1 and D^(n+1)[f](x) = d/dx(f(x)*D^n[f](x)) for n >= 0. Thus a(n+1) = D^(n-1)[(1+x)*exp(x)](0). - Peter Bala, Aug 30 2011
|
|
|
EXAMPLE
|
a(4) = 7: D^2[(1+x)*exp(x)] = exp(2*x)*(2*x^2+8*x+7). Evaluated at x = 0 this gives a(4) = 7. Denote the colors of the nodes by the letters a,b,c,.... The 7 possible trees on 3 nodes with nodes of outdegree k coming in k+1 colors are:
........................................................
...1a....1b....1a....1b........1a.......1b........1c....
...|.....|.....|.....|......../.\....../..\....../..\...
...2a....2b....2b....2a......2...3....2....3....2....3..
...|.....|.....|.....|..................................
...3.....3.....3.....3..................................
G.f. = x + x^2 + 2*x^3 + 7*x^4 + 36*x^5 + 245*x^6 + 2076*x^7 + 21059*x^8 + ...
|
|
|
MAPLE
|
S:= rhs(dsolve({diff(a(x), x) = log(1/(1-a(x)))+1, a(0)=0}, a(x), series, order=101)):
|
|
|
MATHEMATICA
|
Multinomial1[list_] := Apply[Plus, list]!/Apply[Times, (#1! & ) /@ list]; a[1]=1; a[n_]/; n>=2 := a[n] = Sum[Map[Multinomial1[ # ]Product[Map[a, # ]]/Length[ # ]&, Compositions[n-1]]]; Table[a[n], {n, 8}] (* David Callan, Nov 29 2007 *)
nmax=20; b = ConstantArray[0, nmax]; b[[1]]=0; b[[2]]=1; Do[b[[n+1]] = b[[n]] + Sum[Binomial[n-2, i]*b[[i+1]]*b[[n-i+1]], {i, 1, n-2}], {n, 2, nmax-1}]; b (* Vaclav Kotesovec after Vladimir Kruchinin, Mar 11 2014 *)
terms = 20; A[x_] := x; Do[A[x_] = Integrate[(1 + A[x])*Exp[A[x] + O[x]^j], x] + O[x]^j // Normal // Simplify, {j, 1, terms - 1}]; Join[{0, 1}, CoefficientList[A[x], x]*Range[0, terms - 2]! // Rest] (* Jean-François Alcover, May 22 2014, updated Jan 12 2018 (after PARI script by Michael Somos) *)
|
|
|
PROG
|
(PARI) {a(n) = my(A = x + O(x^2)); if( n<2, n==1, n--; for(k=1, n-1, A = intformal( (1 + A) * exp(A))); n! * polcoeff(A, n))}; /* Michael Somos, Apr 17 2015 */
for(n=1, 30, print1(a(n), ", "))
(PARI)
seq(N) = {
my(a = vector(N)); a[1] = 1;
for (n = 2, N, a[n] = a[n-1] + sum(k=1, n-2, binomial(n-2, k)*a[k]*a[n-k]));
concat(0, a);
};
seq(19)
\\ test: N=200; y=serconvol(Ser(seq(N), 'x), exp('x+O('x^N))); y' == y''*(1-y)
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,easy,eigen,nice
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
