A244925 Number T(n,k) of n-node unlabeled rooted trees with every leaf at height k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 0, 1, 2, 2, 1, 1, 0, 1, 4, 3, 2, 1, 1, 0, 1, 4, 5, 3, 2, 1, 1, 0, 1, 7, 7, 6, 3, 2, 1, 1, 0, 1, 8, 12, 8, 6, 3, 2, 1, 1, 0, 1, 12, 18, 15, 9, 6, 3, 2, 1, 1, 0, 1, 14, 27, 23, 16, 9, 6, 3, 2, 1, 1, 0, 1, 21, 42, 39, 26, 17, 9, 6, 3, 2, 1, 1

Offset

1,13

Links

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

Example

The A048816(5) = 5 rooted trees with 5 nodes with every leaf at the same height sorted by height 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  :
  :         :             :       :     :
  : ---1--- : -----2----- : --3-- : -4- :
Thus row 5 = [0, 1, 2, 1, 1].
Triangle T(n,k) begins:
  1;
  0, 1;
  0, 1,  1;
  0, 1,  1,  1;
  0, 1,  2,  1,  1;
  0, 1,  2,  2,  1,  1;
  0, 1,  4,  3,  2,  1, 1;
  0, 1,  4,  5,  3,  2, 1, 1;
  0, 1,  7,  7,  6,  3, 2, 1, 1;
  0, 1,  8, 12,  8,  6, 3, 2, 1, 1;
  0, 1, 12, 18, 15,  9, 6, 3, 2, 1, 1;
  0, 1, 14, 27, 23, 16, 9, 6, 3, 2, 1, 1;
  ...

Maple

with(numtheory):
T:= proc(n, k) option remember; `if`(n=1, 1, `if`(k=0, 0,
      add(add(`if`(d<k, 0, T(d, k-1)*d), d=divisors(j))*
      T(n-j, k), j=1..n-1)/(n-1)))
    end:
seq(seq(T(n, k), k=0..n-1), n=1..14);

Mathematica

T[n_, k_] := T[n, k] = If[n == 1, 1, If[k == 0, 0, Sum[ Sum[ If[d<k, 0, T[d, k-1]*d], {d, Divisors[j]}] * T[n-j, k], {j, 1, n-1}]/(n-1)]]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Jan 28 2015, after Alois P. Heinz *)

Crossrefs

Columns k=0-10 give: A000007(n-1), A000012 (for n>0), A002865(n-1) (for n>2), A048808, A048809, A048810, A048811, A048812, A048813, A048814, A048815.

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

Row sums give A048816.

Sequence in context: A072233 A264391 A116598 * A068914 A090824 A264620

Adjacent sequences: A244922 A244923 A244924 * A244926 A244927 A244928

Keyword

nonn,tabl

Author

Alois P. Heinz, Jul 08 2014

Status

approved