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

Links

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

Formula

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

Example

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

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

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.

Sequence in context: A140326 A261781 A211402 * A126436 A102394 A145091

Adjacent sequences: A256061 A256062 A256063 * A256065 A256066 A256067

Keyword

nonn,tabl

Author

Alois P. Heinz, Mar 13 2015

Status

approved