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,8

Comments

T(1,0) = 1 by convention.

Links

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

Example

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;

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

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

Sequence in context: A325873 A363973 A046781 * A372722 A271424 A117435

Adjacent sequences: A244527 A244528 A244529 * A244531 A244532 A244533

Keyword

nonn,tabl

Author

Joerg Arndt and Alois P. Heinz, Jun 29 2014

Status

approved