login
A293109
Number T(n,k) of multisets of nonempty words with a total of n letters over k-ary alphabet containing the k-th letter such that within each prefix of a word every letter of the alphabet is at least as frequent as the subsequent alphabet letter; triangle T(n,k), n>=0, 0<=k<=n, read by rows.
14
1, 0, 1, 0, 2, 1, 0, 3, 3, 1, 0, 5, 10, 4, 1, 0, 7, 24, 17, 5, 1, 0, 11, 62, 58, 26, 6, 1, 0, 15, 140, 193, 107, 37, 7, 1, 0, 22, 329, 603, 439, 178, 50, 8, 1, 0, 30, 725, 1852, 1663, 852, 275, 65, 9, 1, 0, 42, 1631, 5539, 6283, 3767, 1500, 402, 82, 10, 1
OFFSET
0,5
LINKS
FORMULA
T(n,k) = A293108(n,k) - A293108(n,k-1) for k>0, T(n,0) = A293108(n,0).
EXAMPLE
Triangle T(n,k) begins:
1;
0, 1;
0, 2, 1;
0, 3, 3, 1;
0, 5, 10, 4, 1;
0, 7, 24, 17, 5, 1;
0, 11, 62, 58, 26, 6, 1;
0, 15, 140, 193, 107, 37, 7, 1;
0, 22, 329, 603, 439, 178, 50, 8, 1;
MAPLE
h:= l-> (n-> add(i, i=l)!/mul(mul(1+l[i]-j+add(`if`(l[k]
<j, 0, 1), k=i+1..n), j=1..l[i]), i=1..n))(nops(l)):
g:= proc(n, i, l) option remember;
`if`(n=0, h(l), `if`(i<1, 0, `if`(i=1, h([l[], 1$n]),
g(n, i-1, l) +`if`(i>n, 0, g(n-i, i, [l[], i])))))
end:
A:= proc(n, k) option remember; `if`(n=0, 1, add(add(g(d, k, [])
*d, d=numtheory[divisors](j))*A(n-j, k), j=1..n)/n)
end:
T:= (n, k)-> A(n, k) -`if`(k=0, 0, A(n, k-1)):
seq(seq(T(n, k), k=0..n), n=0..12);
MATHEMATICA
h[l_] := Function[n, Total[l]!/Product[Product[1 + l[[i]] - j + Sum[If[l[[k]] < j, 0, 1], {k, i + 1, n}], {j, 1, l[[i]]}], {i, n}]][Length[l]];
g[n_, i_, l_] := g[n, i, l] = If[n == 0, h[l], If[i < 1, 0, If[i == 1, h[Join[l, Table[1, n]]], g[n, i - 1, l] + If[i > n, 0, g[n - i, i, Append[l, i]]]]]];
A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[Sum[g[d, k, {}]*d, {d, Divisors[j]}]*A[n - j, k], {j, 1, n}]/n];
T[n_, 0] := A[n, 0]; T[n_, k_] := A[n, k] - A[n, k - 1];
Table[T[n, k], {n, 0, 12}, {k, 0, n}] // Flatten (* Jean-François Alcover, Jul 09 2018, after Alois P. Heinz *)
CROSSREFS
Columns k=0-10 give: A000007, A000041 (for n>0), A293797, A293798, A293799, A293800, A293801, A293802, A293803, A293804, A293805.
Row sums give A293110.
T(2n,n) gives A293111.
Sequence in context: A107238 A258170 A055830 * A233530 A079123 A121548
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Sep 30 2017
STATUS
approved