The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 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. 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 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
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified May 14 13:20 EDT 2021. Contains 343884 sequences. (Running on oeis4.)