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.
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
Examples
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, .
Links
- Alois P. Heinz, Rows n = 2..150
Crossrefs
Programs
-
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 *)