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

Links

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

Formula

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

Example

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

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

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.

Sequence in context: A302670 A302472 A303254 * A302381 A303102 A302953

Adjacent sequences: A256065 A256066 A256067 * A256069 A256070 A256071

Keyword

nonn,tabl

Author

Alois P. Heinz, Mar 13 2015

Status

approved