|
|
A319501
|
|
Number T(n,k) of sets of nonempty words with a total of n letters over k-ary alphabet such that all k letters occur at least once in the set; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
|
|
16
|
|
|
1, 0, 1, 0, 1, 3, 0, 2, 12, 13, 0, 2, 38, 105, 73, 0, 3, 110, 588, 976, 501, 0, 4, 302, 2811, 8416, 9945, 4051, 0, 5, 806, 12354, 59488, 121710, 111396, 37633, 0, 6, 2109, 51543, 375698, 1185360, 1830822, 1366057, 394353, 0, 8, 5450, 207846, 2209276, 10096795, 23420022, 28969248, 18235680, 4596553
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,6
|
|
LINKS
|
|
|
FORMULA
|
T(n,k) = Sum_{i=0..k} (-1)^i * C(k,i) * A292804(n,k-i).
|
|
EXAMPLE
|
T(2,2) = 3: {ab}, {ba}, {a,b}.
T(3,2) = 12: {aab}, {aba}, {abb}, {baa}, {bab}, {bba}, {a,ab}, {a,ba}, {a,bb}, {aa,b}, {ab,b}, {b,ba}.
T(4,2) = 38: {aaab}, {aaba}, {aabb}, {abaa}, {abab}, {abba}, {abbb}, {baaa}, {baab}, {baba}, {babb}, {bbaa}, {bbab}, {bbba}, {a,aab}, {a,aba}, {a,abb}, {a,baa}, {a,bab}, {a,bba}, {a,bbb}, {aa,ab}, {aa,ba}, {aa,bb}, {aaa,b}, {aab,b}, {ab,ba}, {ab,bb}, {aba,b}, {abb,b}, {b,baa}, {b,bab}, {b,bba}, {ba,bb}, {a,aa,b}, {a,ab,b}, {a,b,ba}, {a,b,bb}.
Triangle T(n,k) begins:
1;
0, 1;
0, 1, 3;
0, 2, 12, 13;
0, 2, 38, 105, 73;
0, 3, 110, 588, 976, 501;
0, 4, 302, 2811, 8416, 9945, 4051;
0, 5, 806, 12354, 59488, 121710, 111396, 37633;
0, 6, 2109, 51543, 375698, 1185360, 1830822, 1366057, 394353;
|
|
MAPLE
|
h:= proc(n, i, k) option remember; `if`(n=0, 1, `if`(i<1, 0,
add(h(n-i*j, i-1, k)*binomial(k^i, j), j=0..n/i)))
end:
T:= (n, k)-> add((-1)^i*binomial(k, i)*h(n$2, k-i), i=0..k):
seq(seq(T(n, k), k=0..n), n=0..12);
|
|
MATHEMATICA
|
h[n_, i_, k_] := h[n, i, k] = If[n==0, 1, If[i<1, 0, Sum[h[n-i*j, i-1, k]* Binomial[k^i, j], {j, 0, n/i}]]];
T[n_, k_] := Sum[(-1)^i Binomial[k, i] h[n, n, k-i], {i, 0, k}];
|
|
CROSSREFS
|
Columns k=0-10 give: A000007, A000009 (for n>0), A320203, A320204, A320205, A320206, A320207, A320208, A320209, A320210, A320211.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|