|
| |
|
|
A029768
|
|
Number of increasing mobiles with n elements.
|
|
10
| |
|
|
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; internal format)
|
|
|
|
OFFSET
| 0,4
|
|
|
COMMENTS
| A labelled tree of size n is a rooted tree on n nodes that are labelled by distinct integers from the set {1,...,n}. An increasing tree is a labelled 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.
Sergey Fomin and Grigory Mikhalkin, Labeled floor diagrams for plane curves, arXiv:0906.3828. See Section 7.4. [From N. J. A. Sloane, Sep 27 2010]
|
|
|
LINKS
| C. G. Bower, Transforms
C. G. Bower, Transforms (2)
Index entries for sequences related to mobiles
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]
|
|
|
FORMULA
| Bergeron et al. give several formulae. Shifts left under "CIJ" (necklace, indistinct, labeled) transform.
E.g.f.: A(x) satisfies the differential equation A'(x)=ln(1/(1-A(x)))+1. [From Vladimir Kruchinin, Jan 22 2011]
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. [From 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(x) = int {t = 0..x} exp(-x)/(1+x). 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..................................
|
|
|
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 (callan(AT)stat.wisc.edu), Nov 29 2007
|
|
|
CROSSREFS
| Cf. A032220, A038037, A055356. A008544, A145271.
Sequence in context: A185754 A191493 A095793 * A180271 A167199 A007889
Adjacent sequences: A029765 A029766 A029767 * A029769 A029770 A029771
|
|
|
KEYWORD
| nonn,easy,eigen,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms from Christian G. Bower (bowerc(AT)usa.net)
|
| |
|
|
