A029768 Number of increasing mobiles with n elements.
0, 1, 1, 2, 7, 36, 245, 2076, 21059, 248836, 3356609, 50896380, 856958911, 15864014388, 320245960333, 7001257954796, 164792092647355, 4154906594518116, 111719929072986521, 3191216673497748444
Offset: 0
Examples
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 + ...
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
Programs
-
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) *) -
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
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
Extensions
More terms from Christian G. Bower
Comments