A055356 -id:A055356 - cp's OEIS frontend

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

N. J. A. Sloane, Dec 11 1999

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

			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 + ...

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

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

Cf. A032220, A038037, A055356, A008544, A145271.

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

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

{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),", "))

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

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

More terms from Christian G. Bower

A055340 Triangle read by rows: number of mobiles (circular rooted trees) with n nodes and k leaves.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 4, 3, 1, 0, 1, 6, 8, 4, 1, 0, 1, 9, 19, 16, 5, 1, 0, 1, 12, 37, 46, 25, 6, 1, 0, 1, 16, 66, 118, 96, 40, 7, 1, 0, 1, 20, 110, 260, 300, 184, 56, 8, 1, 0, 1, 25, 172, 527, 811, 688, 318, 80, 9, 1, 0, 1, 30, 257, 985, 1951, 2178, 1408, 524, 105, 10, 1, 0

Offset: 1

Christian G. Bower, May 14 2000

			G.f. = x^(y + x*y + x^2*(y + y^2) + x^3*(y + 2*y^2 + y^3) + x^4*(y + 4*y^2 + 3*y^3 + y^4) + ...).
n\k 1  2  3  4  5  6  7  8
--:-- -- -- -- -- -- -- --
1:  1
2:  1  0
3:  1  1  0
4:  1  2  1  0
5:  1  4  3  1  0
6:  1  6  8  4  1  0
7:  1  9 19 16  5  1  0
8:  1 12 37 46 25  6  1  0

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)
C. G. Bower, Transforms (2)
Index entries for sequences related to mobiles

Row sums give A032200.
Columns 2..8 are A002620(n-1), A055341, A055342, A055343, A055344, A055345, A055346.
Cf. A055347, A055348, A055349, A055356, A055363.

m = 13; A[, ] = 0;
Do[A[x_, y_] = x (y - Sum[EulerPhi[i]/i Log[1 - A[x^i, y^i]], {i, 1, m}]) + O[x]^m + O[y]^m // Normal, {m}];
Join[{1}, Append[CoefficientList[#/y, y], 0]& /@ Rest @ CoefficientList[ A[x, y]/x, x]] // Flatten (* Jean-François Alcover, Oct 02 2019 *)

{T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*y - x*sum(i=1, j, eulerphi(i)/i * log(1 - subst( subst( A + x * O(x^min(j, n\i)), x, x^i), y, y^i) ) )); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */

G.f. satisfies A(x, y)=xy+x*CIK(A(x, y))-x. Shifts up under CIK transform.
G.f. satisfies A(x, y) = x*(y - Sum_{i>0} phi(i)/i * log(1 - A(x^i, y^i))). - Michael Somos, Aug 24 2015
Sum_k T(n, k) = A032200(n). - Michael Somos, Aug 24 2015

A055363 Triangle of asymmetric mobiles (circular rooted trees) with n nodes and k leaves.

Original entry on oeis.org

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 2, 1, 0, 0, 1, 4, 4, 1, 0, 0, 1, 6, 10, 5, 1, 0, 0, 1, 9, 22, 19, 7, 1, 0, 0, 1, 12, 42, 53, 31, 8, 1, 0, 0, 1, 16, 73, 130, 109, 45, 10, 1, 0, 0, 1, 20, 119, 280, 321, 190, 63, 11, 1, 0, 0, 1, 25, 184, 556, 833, 672, 310, 83, 13, 1, 0, 0, 1, 30, 272

Offset: 1

Christian G. Bower, May 15 2000

			G.f. = x*(y + x*y + x^2*y + x^3*(y + y^2) + x^4*(y + 2*y^2 + y^3) + x^5*(y + 4*y^2 + 4*y^3 + y^4) + ...).
n\k 1  2  3  4  5  6  7  8
--:-- -- -- -- -- -- -- --
1:  1
2:  1  0
3:  1  0  0
4:  1  1  0  0
5:  1  2  1  0  0
6:  1  4  4  1  0  0
7:  1  6 10  5  1  0  0
8:  1  9 22 19  7  1  0  0

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)
Index entries for sequences related to mobiles

Row sums give A032171.
Columns 2..8: A002620(n-2), A055364, A055365, A055366, A055367, A055368, A055369.
Cf. A055340, A055349, A055356, A055370, A055371.

T[n_, k_] := Module[{A}, A[, ] = 0; If[k<1 || k>n, 0, For[j=1, j <= n, j++, A[x_, y_] = x*y-x*Sum[MoebiusMu[i]/i * Log[1 - A[x^i, y^i]] + O[x]^j // Normal, {i, 1, j}]]; Coefficient[Coefficient[A[x, y], x, n], y, k]]];
Table[T[n, k], {n, 1, 13}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jun 30 2017, after Michael Somos *)

{T(n, k) = my(A = O(x)); if(k<1 || k>n, 0, for(j=1, n, A = x*y - x*sum(i=1, j, moebius(i)/i * log(1 - subst( subst( A + x * O(x^min(j, n\i)), x, x^i), y, y^i) ) )); polcoeff( polcoeff(A, n), k))}; /* Michael Somos, Aug 24 2015 */

G.f. satisfies A(x, y) = x*(y - Sum_{i>0} moebius(i)/i * log(1 - A(x^i, y^i))). - Michael Somos, Aug 19 2015

Sum_k T(n, k) = A032171(n). - Michael Somos, Aug 24 2015

A055349 Triangle of labeled mobiles (circular rooted trees) with n nodes and k leaves.

Original entry on oeis.org

1, 2, 0, 6, 3, 0, 24, 36, 8, 0, 120, 360, 220, 30, 0, 720, 3600, 4200, 1500, 144, 0, 5040, 37800, 71400, 47250, 11508, 840, 0, 40320, 423360, 1176000, 1234800, 545664, 98784, 5760, 0, 362880, 5080320, 19474560, 29635200, 20469456, 6618528, 940896, 45360, 0

Offset: 1

Christian G. Bower, May 15 2000

			Triangle begins:
     1;
     2,     0;
     6,     3,     0;
    24,    36,     8,     0;
   120,   360,   220,    30,     0;
   720,  3600,  4200,  1500,   144,   0;
  5040, 37800, 71400, 47250, 11508, 840, 0;
  ...

Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)
Index entries for sequences related to mobiles

Row sums give A038037.
Columns 1..8 are A000142, A055303, A055350, A055351, A055352, A055353, A055354, A055355.
Cf. A055340, A055356, A055363.

T[rows_] := {{1}}~Join~((cc = CoefficientList[#, y]; Append[Rest[cc], 0] * Length[cc]!)& /@ (CoefficientList[InverseSeries[x/(y-Log[1-x + O[x]^rows] ), x], x][[3;;]]));
T[9] // Flatten (* Jean-François Alcover, Oct 31 2019 *)

A(n)={my(v=Vec(serlaplace(serreverse(x/(y - log(1-x + O(x^n))))))); vector(#v, i, Vecrev(v[i]/y, i))}
{ my(T=A(10)); for(i=1, #T, print(T[i])) } \\ Andrew Howroyd, Sep 23 2018

E.g.f. satisfies A(x, y) = x*y - x*log(1-A(x, y)). [Corrected by Sean A. Irvine, Mar 19 2022]

A055357 Number of increasing mobiles (circular rooted trees) with n nodes and 3 leaves.

Original entry on oeis.org

2, 18, 98, 424, 1614, 5682, 19022, 61584, 194882, 607042, 1870122, 5716680, 17379206, 52628898, 158934998, 479032912, 1441816986, 4335412050, 13027207250, 39125661480, 117469258622, 352600713298, 1058204792478

Offset: 4

Christian G. Bower, May 15 2000

nonn

Georg Fischer, Table of n, a(n) for n = 4..250
Index entries for sequences related to mobiles
Index entries for linear recurrences with constant coefficients, signature (10,-40,82,-91,52,-12).

Column 3 of A055356.

Drop[CoefficientList[Series[x^4*(-2*x^2 - 2*x + 2)/((1 - 3*x)*(1 - 2*x)^2*(1 - x)^3), {x, 0, 30}], x], 4] (* Vaclav Kotesovec, Mar 15 2022 *)

G.f.: x^4*(-2*x^2-2*x+2)/((1-3*x)*(1-2*x)^2*(1-x)^3).

For n>0, a(n) = 5*3^(n-1)/4 - 2^n*(n+1)/2 + n^2/2 + 1/4. - Vaclav Kotesovec, Mar 15 2022

A055358 Number of increasing mobiles (circular rooted trees) with n nodes and 4 leaves.

Original entry on oeis.org

6, 96, 874, 6040, 35458, 187288, 920350, 4297240, 19332662, 84615152, 362772194, 1531122296, 6385177274, 26382771464, 108232980822, 441554515704, 1793612585550, 7261158583200, 29318205685050

Offset: 5

Christian G. Bower, May 15 2000

nonn

Georg Fischer, Table of n, a(n) for n = 5..250
Index entries for sequences related to mobiles

Column 4 of A055356.

For n>0, a(n) = 31*2^(2*n - 3)/9 - 5*(n+2)*3^n/12 + (n^2 + 2*n + 2)*2^(n-2) - n^3/6 - n/4 - 1/18. - Vaclav Kotesovec, Mar 15 2022

A055359 Number of increasing mobiles (circular rooted trees) with n nodes and 5 leaves.

Original entry on oeis.org

24, 600, 8244, 83500, 701164, 5191412, 35160560, 223072440, 1347354144, 7836767696, 44262649196, 244280080420, 1323563238484, 7066323307308, 37279810191336, 194788586755056, 1009815185486280, 5201560257678600

Offset: 6

Christian G. Bower, May 15 2000

nonn

Georg Fischer, Table of n, a(n) for n = 6..250
Index entries for sequences related to mobiles

Column 5 of A055356.

A055360 Number of increasing mobiles (circular rooted trees) with n nodes and 6 leaves.

Original entry on oeis.org

120, 4320, 83628, 1169768, 13329084, 131888624, 1178097904, 9745456704, 75988344096, 565644812320, 4057808611860, 28255332957880, 192032572801508, 1279389256340592, 8384651931678936, 54203683325174736

Offset: 7

Christian G. Bower, May 15 2000

nonn

Georg Fischer, Table of n, a(n) for n = 7..250
Index entries for sequences related to mobiles

Column 6 of A055356.

A055361 Number of increasing mobiles (circular rooted trees) with n nodes and 7 leaves.

Original entry on oeis.org

720, 35280, 915984, 16939800, 251869440, 3213860944, 36634201456, 383130347344, 3745749248752, 34704916926064, 307859356272208, 2635356154189416, 21904079389753056, 177636951598742640

Offset: 8

Christian G. Bower, May 15 2000

nonn

Georg Fischer, Table of n, a(n) for n = 8..250
Index entries for sequences related to mobiles

Column 7 of A055356.

A055362 Number of increasing mobiles (circular rooted trees) with n nodes and 8 leaves.

Original entry on oeis.org

5040, 322560, 10824336, 255992688, 4818505344, 77114374080, 1093159611568, 14109101755360, 169059052774160, 1907751093010304, 20495617800709968, 211401353181089232, 2107388333854021920, 20411845702807028160

Offset: 9

Christian G. Bower, May 15 2000

nonn

Georg Fischer, Table of n, a(n) for n = 9..250
Index entries for sequences related to mobiles

Column 8 of A055356.

cp's OEIS Frontend

A029768 Number of increasing mobiles with n elements.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A055340 Triangle read by rows: number of mobiles (circular rooted trees) with n nodes and k leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A055363 Triangle of asymmetric mobiles (circular rooted trees) with n nodes and k leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A055349 Triangle of labeled mobiles (circular rooted trees) with n nodes and k leaves.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A055357 Number of increasing mobiles (circular rooted trees) with n nodes and 3 leaves.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

Formula

A055358 Number of increasing mobiles (circular rooted trees) with n nodes and 4 leaves.

Views

Author

Keywords

Links

Crossrefs

Formula

A055359 Number of increasing mobiles (circular rooted trees) with n nodes and 5 leaves.

Views

Author

Keywords

Links

Crossrefs

A055360 Number of increasing mobiles (circular rooted trees) with n nodes and 6 leaves.

Views

Author

Keywords

Links

Crossrefs

A055361 Number of increasing mobiles (circular rooted trees) with n nodes and 7 leaves.

Views