login
A320264
Number T(n,k) of proper multisets of nonempty words with a total of n letters over k-ary alphabet such that all k letters occur at least once in the multiset; triangle T(n,k), n>=2, 1<=k<=n-1, read by rows.
4
1, 1, 2, 3, 11, 9, 4, 38, 84, 52, 7, 125, 523, 766, 365, 10, 364, 2676, 7096, 7775, 3006, 16, 1041, 12435, 52955, 100455, 87261, 28357, 22, 2838, 54034, 348696, 1020805, 1497038, 1074766, 301064, 32, 7645, 225417, 2120284, 8995801, 19823964, 23605043, 14423564, 3549177
OFFSET
2,3
LINKS
Alois P. Heinz, Rows n = 2..150
FORMULA
T(n,k) = A257740(n,k) - A319501(n,k).
EXAMPLE
T(2,1) = 1: {a,a}.
T(3,2) = 2: {a,a,b}, {a,b,b}.
T(4,3) = 9: {a,a,b,c}, {a,a,bc}, {a,a,cb}, {b,b,a,c}, {b,b,ac}, {b,b,ca}, {c,c,a,b}, {c,c,ab}, {c,c,ba}.
Triangle T(n,k) begins:
.
. .
. 1, .
. 1, 2, .
. 3, 11, 9, .
. 4, 38, 84, 52, .
. 7, 125, 523, 766, 365, .
. 10, 364, 2676, 7096, 7775, 3006, .
. 16, 1041, 12435, 52955, 100455, 87261, 28357, .
. 22, 2838, 54034, 348696, 1020805, 1497038, 1074766, 301064, .
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:
g:= proc(n, k) option remember; `if`(n=0, 1, add(add(
d*k^d, d=numtheory[divisors](j))*g(n-j, k), j=1..n)/n)
end:
T:= (n, k)-> add((-1)^i*(g(n, k-i)-h(n$2, k-i))*binomial(k, i), i=0..k):
seq(seq(T(n, k), k=1..n-1), n=2..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}]]];
g[n_, k_] := g[n, k] = If[n == 0, 1, Sum[Sum[
d*k^d, {d, Divisors[j]}]*g[n - j, k], {j, 1, n}]/n];
T[n_, k_] := Sum[(-1)^i*(g[n, k-i]-h[n, n, k-i])*Binomial[k, i], {i, 0, k}];
Table[Table[T[n, k], {k, 1, n - 1}], {n, 2, 12}] // Flatten (* Jean-François Alcover, Feb 13 2021, after Alois P. Heinz *)
CROSSREFS
Column k=1 gives A047967.
Row sums give A320265.
T(n+1,n) gives A006152.
Sequence in context: A086146 A083758 A127494 * A335173 A265563 A265547
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Oct 08 2018
STATUS
approved