A055356 Triangle of increasing mobiles (circular rooted trees) with n nodes and k leaves.

1, 1, 0, 1, 1, 0, 1, 4, 2, 0, 1, 11, 18, 6, 0, 1, 26, 98, 96, 24, 0, 1, 57, 424, 874, 600, 120, 0, 1, 120, 1614, 6040, 8244, 4320, 720, 0, 1, 247, 5682, 35458, 83500, 83628, 35280, 5040, 0, 1, 502, 19022, 187288, 701164, 1169768, 915984, 322560, 40320, 0, 1

Offset: 1

Author

Christian G. Bower, May 15 2000

Keywords

• nonn
• tabl

Comments

In an increasing rooted tree, nodes are numbered and numbers increase as you move away from root.

Also related to the solution of the equation df/dt=f e^f (see the Maple code). - F. Chapoton, Jul 16 2004

Examples

			Triangle begins
  1;
  1,  0;
  1,  1,   0;
  1,  4,   2,   0;
  1, 11,  18,   6,   0;
  1, 26,  98,  96,  24,   0;
  1, 57, 424, 874, 600, 120, 0;
  ...
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..1275 (first 50 rows)
• Shi-Mei Ma, Some combinatorial sequences associated with context-free grammars, arXiv:1208.3104v2 [math.CO], 2012. - _N. J. A. Sloane_, Aug 21 2012
• Index entries for sequences related to mobiles

Crossrefs

Row sums give A029768 (p(n,1)).

Alternating row sums give A089963 (p(n+1,-1)).

Columns 2..8 are A000295, A055357, A055358, A055359, A055360, A055361, A055362.

Cf. A055340, A055349, A055363.

Programs

Maple

P[1]:=1;for n from 1 to 8 do P[n+1]:=simplify((1+n*x)*P[n]+x*diff(P[n],x)) end; # F. Chapoton, Jul 16 2004

Mathematica

P[1][_] = 1;
P[n_][x_] := P[n][x] = (1 + (n-1) x) P[n-1][x] + x P[n-1]'[x] // Expand;
row[1] = {1};
row[n_] := Append[CoefficientList[P[n-1][x], x], 0];
Array[row, 10] // Flatten (* Jean-François Alcover, Nov 17 2018, after F. Chapoton *)

PARI

A(n)={my(v=vector(n)); v[1]=y; for(n=2, #v, v[n]=v[n-1] + sum(k=1, n-2, binomial(n-2, k)*v[k]*v[n-k])); vector(#v, i, Vecrev(v[i]/y, i))}
{ my(T=A(10)); for(i=1, #T, print(T[i])) } \\ Andrew Howroyd, Sep 23 2018

Formula

Let p(n,x) be the polynomial with coefficients equal to the n-th row of the triangle in ascending powers of x, e.g., p(4,x) = 1+4*x+2*x^2; then p(n+1,x) = (1+(n-1)*x)*p(n,x) + x*p'(n,x). - Ben Whitmore, May 12 2021

Recurrence: T(n,k) = (n-2) * T(n-1,k-1) + k * T(n-1,k) for n >= 1, 1 <= k <= n with T(1,1) = 1 and T(n,k) = 0 for n < 1, k < 1 or k > n. - Georg Fischer, Oct 27 2021

Conjecture: row polynomials are R(n-2,0) for n > 1 where R(n,k) = R(n-1,k+1) + x*Sum_{i=0..n-1} Sum_{j=0..k} binomial(n-1, i)*R(n-i-1,j)*R(i,k-j) for n > 0, k >= 0 with R(0,k) = 1 for k >= 0. - Mikhail Kurkov, Apr 11 2025