|
|
A261836
|
|
Number T(n,k) of compositions of n into distinct parts where each part i is marked with a word of length i over a k-ary alphabet whose letters appear in alphabetical order and all k letters occur at least once in the composition; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
|
|
15
|
|
|
1, 0, 1, 0, 1, 1, 0, 3, 10, 7, 0, 3, 15, 21, 9, 0, 5, 40, 96, 92, 31, 0, 11, 183, 832, 1562, 1305, 403, 0, 13, 266, 1539, 3908, 4955, 3090, 757, 0, 19, 549, 4281, 14791, 26765, 26523, 13671, 2873, 0, 27, 1056, 10902, 50208, 124450, 178456, 148638, 66904, 12607
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,8
|
|
COMMENTS
|
Also number of matrices with k rows of nonnegative integer entries and without zero rows or columns such that the sum of all entries is equal to n and the column sums are distinct.
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A261835(n,k-i).
|
|
EXAMPLE
|
T(3,2) = 10: (matrices and corresponding marked compositions are given)
[2] [1] [2 0] [0 2] [1 0] [0 1] [1 1] [1 1] [1 0] [0 1]
[1] [2] [0 1] [1 0] [0 2] [2 0] [1 0] [0 1] [1 1] [1 1]
3aab, 3abb, 2aa1b, 1b2aa, 1a2bb, 2bb1a, 2ab1a, 1a2ab, 2ab1b, 1b2ab.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 1;
0, 3, 10, 7;
0, 3, 15, 21, 9;
0, 5, 40, 96, 92, 31;
0, 11, 183, 832, 1562, 1305, 403;
0, 13, 266, 1539, 3908, 4955, 3090, 757;
0, 19, 549, 4281, 14791, 26765, 26523, 13671, 2873;
|
|
MAPLE
|
b:= proc(n, i, p, k) option remember;
`if`(i*(i+1)/2<n, 0, `if`(n=0, p!, b(n, i-1, p, k)+
`if`(i>n, 0, b(n-i, i-1, p+1, k)*binomial(i+k-1, k-1))))
end:
T:= (n, k)-> add(b(n$2, 0, k-i)*(-1)^i*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..12);
|
|
MATHEMATICA
|
b[n_, i_, p_, k_] := b[n, i, p, k] = If[i*(i+1)/2<n, 0, If[n==0, p!, b[n, i -1, p, k] + If[i>n, 0, b[n-i, i-1, p+1, k]*Binomial[i+k-1, k-1]]]]; T[n_, k_] := Sum[b[n, n, 0, k-i]*(-1)^i*Binomial[k, i], {i, 0, k}]; Table[ Table[T[n, k], {k, 0, n}], {n, 0, 12}] // Flatten (* Jean-François Alcover, Feb 21 2016, after Alois P. Heinz *)
|
|
CROSSREFS
|
Columns k=0-10 give: A000007, A032020 (for n>0), A261853, A261854, A261855, A261856, A261857, A261858, A261859, A261860, A261861.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|