A256068 Number T(n,k) of rooted identity trees with n nodes and colored non-root nodes using exactly k colors; triangle T(n,k), n>=1, 0<=k<=n-1, read by rows.

1, 0, 1, 0, 1, 3, 0, 2, 14, 16, 0, 3, 60, 174, 125, 0, 6, 254, 1434, 2464, 1296, 0, 12, 1087, 10746, 33362, 40455, 16807, 0, 25, 4742, 77556, 388312, 816535, 763104, 262144, 0, 52, 21020, 551460, 4191916, 13617210, 21501684, 16328620, 4782969

Offset: 1

Author

Alois P. Heinz, Mar 13 2015

Keywords

• nonn
• tabl

Examples

			T(4,2) = 14:
:   0   0   0   0   0   0     0       0
:   |   |   |   |   |   |     |       |
:   1   1   2   2   2   1     1       2
:   |   |   |   |   |   |    / \     / \
:   1   2   1   2   1   2   1   2   1   2
:   |   |   |   |   |   |
:   2   1   1   1   2   1
:
:     0      0      0      0      0      0
:    / \    / \    / \    / \    / \    / \
:   1   1  2   1  1   2  2   2  1   2  2   1
:   |      |      |      |      |      |
:   2      1      1      1      2      2
Triangle T(n,k) begins:
  1;
  0,  1;
  0,  1,    3;
  0,  2,   14,    16;
  0,  3,   60,   174,    125;
  0,  6,  254,  1434,   2464,   1296;
  0, 12, 1087, 10746,  33362,  40455,  16807;
  0, 25, 4742, 77556, 388312, 816535, 763104, 262144;
  ...
		

Links

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

Crossrefs

Columns k=0-1 give: A063524 (for n>0), A004111 (for n>1):

Main diagonal gives: A000272 (for n>0).

Row sums give A319220(n-1).

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

Cf. A255517, A256064.

Programs

Maple

with(numtheory):
A:= proc(n, k) option remember; `if`(n<2, n, add(A(n-j, k)*add(
      k*A(d, k)*d*(-1)^(j/d+1), d=divisors(j)), j=1..n-1)/(n-1))
    end:
T:= (n, k)-> add(A(n, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n-1), n=1..10);

Mathematica

A[n_, k_] := A[n, k] = If[n < 2, n, Sum[A[n - j, k] Sum[k A[d, k] d * (-1)^(j/d + 1), {d, Divisors[j]}], {j, 1, n - 1}]/(n - 1)];
T[n_, k_] := Sum[A[n, k - i] (-1)^i Binomial[k, i], {i, 0, k}];
Table[T[n, k], {n, 10}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, May 29 2020, after Maple *)

Formula

T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A255517(n).