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

 

Logo


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

a(n+1)/a(n)/n tends to 1/A073003 = 1.676875... . - Vaclav Kotesovec, Mar 11 2014

REFERENCES

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 392.

LINKS

Vaclav Kotesovec, Table of n, a(n) for n = 0..400

C. G. Bower, Transforms

C. G. Bower, Transforms (2)

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.

D. Dominici, Nested derivatives: A simple method for computing series expansions of inverse functions. arXiv:math/0501052v2 [math.CA], 2015.

Sergey Fomin and Grigory Mikhalkin, Labeled floor diagrams for plane curves, arXiv:0906.3828 [math.AG], 2009-2010.

Index entries for sequences related to mobiles

FORMULA

Bergeron et al. give several formulas. Shifts left under "CIJ" (necklace, indistinct, labeled) transform.

E.g.f.: A(x) 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

From Robert Israel, Apr 17 2015 (Start):

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)):

seq(coeff(S, x, j)*j!, j=0..100); # Robert Israel, Apr 17 2015

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)

\\ Gheorghe Coserea, Jun 26 2018

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, Dec 11 1999

EXTENSIONS

More terms from Christian G. Bower

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 20 10:05 EDT 2018. Contains 316378 sequences. (Running on oeis4.)