A256064 Number T(n,k) of rooted 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, 2, 3, 0, 4, 18, 16, 0, 9, 89, 201, 125, 0, 20, 418, 1830, 2720, 1296, 0, 48, 1962, 14845, 39720, 43580, 16807, 0, 115, 9268, 114624, 492276, 934455, 809760, 262144, 0, 286, 44375, 866148, 5613775, 16413510, 23991063, 17152163, 4782969

Offset: 1

Author

Alois P. Heinz, Mar 13 2015

Keywords

• nonn
• tabl

Examples

			T(3,2) = 3:
  o    o      o
  |    |     / \
  1    2    1   2
  |    |
  2    1
Triangle T(n,k) begins:
  1;
  0,   1;
  0,   2,    3;
  0,   4,   18,     16;
  0,   9,   89,    201,    125;
  0,  20,  418,   1830,   2720,   1296;
  0,  48, 1962,  14845,  39720,  43580,  16807;
  0, 115, 9268, 114624, 492276, 934455, 809760, 262144;
  ...
		

Links

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

Crossrefs

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

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

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

Cf. A242249, A256068.

Programs

Maple

with(numtheory):
A:= proc(n, k) option remember; `if`(n<2, n, (add(add(d*
      A(d, k), d=divisors(j))*A(n-j, k)*k, 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[Sum[d*A[d, k], {d, Divisors[j]}]* A[n - j, k]*k, {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, 1, 10}, {k, 0, n - 1}] // Flatten (* Jean-François Alcover, Jan 07 2020, from Maple *)

Formula

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