A244530 Number T(n,k) of ordered unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals k; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

1, 0, 1, 0, 1, 1, 0, 4, 0, 1, 0, 11, 2, 0, 1, 0, 36, 5, 0, 0, 1, 0, 117, 11, 3, 0, 0, 1, 0, 393, 28, 7, 0, 0, 0, 1, 0, 1339, 78, 8, 4, 0, 0, 0, 1, 0, 4630, 201, 21, 9, 0, 0, 0, 0, 1, 0, 16193, 532, 55, 10, 5, 0, 0, 0, 0, 1, 0, 57201, 1441, 121, 11, 11, 0, 0, 0, 0, 0, 1

Offset: 1

Author

Joerg Arndt and Alois P. Heinz, Jun 29 2014

Keywords

• nonn
• tabl

Comments

T(1,0) = 1 by convention.

Examples

			T(5,1) = 11:
  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       o       o
  |  / \  |         | |         |
  o o   o o         o o         o
  |
  o
Triangle T(n,k) begins:
  1;
  0,     1;
  0,     1,   1;
  0,     4,   0,  1;
  0,    11,   2,  0,  1;
  0,    36,   5,  0,  0, 1;
  0,   117,  11,  3,  0, 0, 1;
  0,   393,  28,  7,  0, 0, 0, 1;
  0,  1339,  78,  8,  4, 0, 0, 0, 1;
  0,  4630, 201, 21,  9, 0, 0, 0, 0, 1;
  0, 16193, 532, 55, 10, 5, 0, 0, 0, 0, 1;
		

Links

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

Crossrefs

Columns k=0-10 give: A063524, A106640(n-2), A244531, A244532, A244533, A244534, A244535, A244536, A244537, A244538, A244539.

Row sums give A000108(n-1).

Cf. A244454 (unordered unlabeled rooted trees).

Programs

Maple

b:= proc(n, t, k) option remember; `if`(n=0,
      `if`(t in [0, k], 1, 0), `if`(t>n, 0, add(b(j-1, k$2)*
       b(n-j, max(0, t-1), k), j=1..n)))
    end:
T:= (n, k)-> b(n-1, k$2) -`if`(n=1 and k=0, 0, b(n-1, k+1$2)):
seq(seq(T(n, k), k=0..n-1), n=1..14);

Mathematica

b[n_, t_, k_] := b[n, t, k] = If[n == 0, If[t == 0 || t == k, 1, 0], If[t>n, 0, Sum[b[j-1, k, k]*b[n-j, Max[0, t-1], k], {j, 1, n}]]]; T[n_, k_] := b[n-1, k, k] - If[n == 1 && k == 0, 0, b[n-1, k+1, k+1]]; Table[Table[T[n, k], {k, 0, n-1}], {n, 1, 14}] // Flatten (* Jean-François Alcover, Jan 13 2015, translated from Maple *)