A244372 Number T(n,k) of unlabeled rooted trees with n nodes and maximal outdegree (branching factor) k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 2, 1, 0, 1, 5, 2, 1, 0, 1, 10, 6, 2, 1, 0, 1, 22, 16, 6, 2, 1, 0, 1, 45, 43, 17, 6, 2, 1, 0, 1, 97, 113, 49, 17, 6, 2, 1, 0, 1, 206, 300, 136, 50, 17, 6, 2, 1, 0, 1, 450, 787, 386, 142, 50, 17, 6, 2, 1, 0, 1, 982, 2074, 1081, 409, 143, 50, 17, 6, 2, 1

Offset: 1

Author

Joerg Arndt and Alois P. Heinz, Jun 26 2014

Keywords

• nonn
• tabl

Examples

			The A000081(5) = 9 rooted trees with 5 nodes sorted by maximal outdegree are:
:  o  :   o     o     o       o     o   :   o     o   :    o    :
:  |  :   |     |    / \     / \   / \  :   |    /|\  :  /( )\  :
:  o  :   o     o   o   o   o   o o   o :   o   o o o : o o o o :
:  |  :   |    / \  |      / \    |   | :  /|\  |     :         :
:  o  :   o   o   o o     o   o   o   o : o o o o     :         :
:  |  :  / \  |     |                   :             :         :
:  o  : o   o o     o                   :             :         :
:  |  :                                 :             :         :
:  o  :                                 :             :         :
:     :                                 :             :         :
: -1- : ---------------2--------------- : -----3----- : ---4--- :
Thus row 5 = [0, 1, 5, 2, 1].
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,   1;
  0,  1,   2,    1;
  0,  1,   5,    2,    1;
  0,  1,  10,    6,    2,   1;
  0,  1,  22,   16,    6,   2,   1;
  0,  1,  45,   43,   17,   6,   2,  1;
  0,  1,  97,  113,   49,  17,   6,  2,  1;
  0,  1, 206,  300,  136,  50,  17,  6,  2,  1;
  0,  1, 450,  787,  386, 142,  50, 17,  6,  2,  1;
  0,  1, 982, 2074, 1081, 409, 143, 50, 17,  6,  2,  1;
		

Links

• Alois P. Heinz, Rows n = 1..141, flattened

Crossrefs

Columns k=2-10 give: A244398, A244399, A244400, A244401, A244402, A244403, A244404, A244405, A244406.

T(2n,n) gives A244407(n).

T(2n+1,n) gives A244410(n).

Row sum give A000081.

Cf. A244454.

Programs

Maple

b:= proc(n, i, t, k) option remember; `if`(n=0, 1,
      `if`(i<1, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
       b(n-i*j, i-1, t-j, k), j=0..min(t, n/i))))
    end:
T:= (n, k)-> b(n-1$2, k$2) -`if`(k=0, 0, b(n-1$2, k-1$2)):
seq(seq(T(n, k), k=0..n-1), n=1..14);

Mathematica

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, 1, If[i < 1, 0, Sum[Binomial[b[i-1, i-1, k, k]+j-1, j]*b[n-i*j, i-1, t-j, k], {j, 0, Min[t, n/i]}]]]; T[n_, k_] := b[n-1, n-1, k, k] - If[k == 0, 0, b[n-1, n-1, k-1, k-1]]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Jul 01 2014, translated from Maple *)