|
%I #90 Dec 29 2020 08:58:24
%S 0,1,1,2,7,36,245,2076,21059,248836,3356609,50896380,856958911,
%T 15864014388,320245960333,7001257954796,164792092647355,
%U 4154906594518116,111719929072986521,3191216673497748444
%N Number of increasing mobiles with n elements.
%C 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.
%C a(n) counts increasing trees with cyclically ordered branches.
%C 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
%C a(n+1)/a(n)/n tends to 1/A073003 = 1.676875... . - _Vaclav Kotesovec_, Mar 11 2014
%D F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 392.
%H Vaclav Kotesovec, <a href="/A029768/b029768.txt">Table of n, a(n) for n = 0..400</a>
%H C. G. Bower, <a href="/transforms2.html">Transforms</a>
%H C. G. Bower, <a href="/transforms2.html">Transforms (2)</a>
%H F. Bergeron, Ph. Flajolet and B. Salvy, <a href="http://algo.inria.fr/flajolet/Publications/BeFlSa92.pdf">Varieties of Increasing Trees</a>, Lecture Notes in Computer Science vol. 581, ed. J.-C. Raoult, Springer 1992, pp. 24-48.
%H D. Dominici, <a href="http://arxiv.org/abs/math/0501052">Nested derivatives: A simple method for computing series expansions of inverse functions.</a> arXiv:math/0501052v2 [math.CA], 2015.
%H Sergey Fomin and Grigory Mikhalkin, <a href="http://arxiv.org/abs/0906.3828">Labeled floor diagrams for plane curves</a>, arXiv:0906.3828 [math.AG], 2009-2010.
%H <a href="/index/Mo#mobiles">Index entries for sequences related to mobiles</a>
%F Bergeron et al. give several formulas. Shifts left under "CIJ" (necklace, indistinct, labeled) transform.
%F E.g.f.: A(x) =
%F 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 + ...
%F and satisfies the differential equation A'(x)=log(1/(1-A(x)))+1. - _Vladimir Kruchinin_, Jan 22 2011
%F E.g.f. A(x) satisfies: A''(x) = A'(x) * exp(A'(x)-1). - _Paul D. Hanna_, Apr 17 2015
%F From _Robert Israel_, Apr 17 2015 (Start):
%F 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.
%F 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)
%F 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
%F 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
%e 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:
%e ........................................................
%e ...1a....1b....1a....1b........1a.......1b........1c....
%e ...|.....|.....|.....|......../.\....../..\....../..\...
%e ...2a....2b....2b....2a......2...3....2....3....2....3..
%e ...|.....|.....|.....|..................................
%e ...3.....3.....3.....3..................................
%e G.f. = x + x^2 + 2*x^3 + 7*x^4 + 36*x^5 + 245*x^6 + 2076*x^7 + 21059*x^8 + ...
%p S:= rhs(dsolve({diff(a(x),x) = log(1/(1-a(x)))+1,a(0)=0},a(x),series,order=101)):
%p seq(coeff(S,x,j)*j!,j=0..100); # _Robert Israel_, Apr 17 2015
%t 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 *)
%t 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 *)
%t 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_) *)
%o (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 */
%o for(n=1,30,print1(a(n),", "))
%o (PARI)
%o seq(N) = {
%o my(a = vector(N)); a[1] = 1;
%o for (n = 2, N, a[n] = a[n-1] + sum(k=1, n-2, binomial(n-2, k)*a[k]*a[n-k]));
%o concat(0, a);
%o };
%o seq(19)
%o \\ test: N=200; y=serconvol(Ser(seq(N),'x), exp('x+O('x^N))); y' == y''*(1-y)
%o \\ _Gheorghe Coserea_, Jun 26 2018
%Y Cf. A032220, A038037, A055356, A008544, A145271.
%K nonn,easy,eigen,nice
%O 0,4
%A _N. J. A. Sloane_, Dec 11 1999
%E More terms from _Christian G. Bower_
| 