login
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.
7
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
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.
Sequence in context: A302670 A302472 A303254 * A302381 A303102 A302953
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Mar 13 2015
STATUS
approved