login
A292712
Number A(n,k) of multisets of nonempty words with a total of n letters over k-ary alphabet such that within each word every letter of the alphabet is at least as frequent as the subsequent alphabet letter; square array A(n,k), n>=0, k>=0, read by antidiagonals.
13
1, 1, 0, 1, 1, 0, 1, 1, 2, 0, 1, 1, 4, 3, 0, 1, 1, 4, 8, 5, 0, 1, 1, 4, 14, 25, 7, 0, 1, 1, 4, 14, 43, 53, 11, 0, 1, 1, 4, 14, 67, 139, 148, 15, 0, 1, 1, 4, 14, 67, 223, 495, 328, 22, 0, 1, 1, 4, 14, 67, 343, 951, 1544, 858, 30, 0, 1, 1, 4, 14, 67, 343, 1431, 3680, 5111, 1938, 42, 0
OFFSET
0,9
LINKS
FORMULA
G.f. of column k: Product_{j>=1} 1/(1-x^j)^A226873(j,k).
A(n,n) = A(n,k) for all k >= n.
A(n,k) = Sum_{j=0..n} A319495(n,j).
EXAMPLE
A(2,3) = 4: {aa}, {ab}, {ba}, {a,a}.
A(3,2) = 8: {aaa}, {aab}, {aba}, {baa}, {aa,a}, {ab,a}, {ba,a}, {a,a,a}.
A(3,3) = 14: {aaa}, {aab}, {aba}, {baa}, {abc}, {acb}, {bac}, {bca}, {cab}, {cba}, {aa,a}, {ab,a}, {ba,a}, {a,a,a}.
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, 1, 1, ...
0, 1, 1, 1, 1, 1, 1, 1, 1, ...
0, 2, 4, 4, 4, 4, 4, 4, 4, ...
0, 3, 8, 14, 14, 14, 14, 14, 14, ...
0, 5, 25, 43, 67, 67, 67, 67, 67, ...
0, 7, 53, 139, 223, 343, 343, 343, 343, ...
0, 11, 148, 495, 951, 1431, 2151, 2151, 2151, ...
0, 15, 328, 1544, 3680, 6620, 9860, 14900, 14900, ...
0, 22, 858, 5111, 16239, 31539, 53739, 78939, 119259, ...
MAPLE
b:= proc(n, i, t) option remember; `if`(t=1, 1/n!,
add(b(n-j, j, t-1)/j!, j=i..n/t))
end:
g:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), n!*b(n, 0, k)):
A:= proc(n, k) option remember; `if`(n=0, 1, add(add(d*
g(d, k), d=numtheory[divisors](j))*A(n-j, k), j=1..n)/n)
end:
seq(seq(A(n, d-n), n=0..d), d=0..14);
MATHEMATICA
b[n_, i_, t_] := b[n, i, t] = If[t == 1, 1/n!, Sum[b[n - j, j, t - 1]/j!, {j, i, n/t}]];
g[n_, k_] := If[k == 0, If[n == 0, 1, 0], n!*b[n, 0, k]];
A[n_, k_] := A[n, k] = If[n == 0, 1, Sum[Sum[d*g[d, k], {d, Divisors[j]}]* A[n - j, k], {j, 1, n}]/n];
Table[A[n, d-n], {d, 0, 14}, {n, 0, d}] // Flatten (* Jean-François Alcover, Jun 07 2018, from Maple *)
CROSSREFS
Rows n=0-1 give: A000012, A057427.
Main diagonal gives A292713.
Sequence in context: A049501 A102564 A215703 * A331571 A247504 A306800
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Sep 21 2017
STATUS
approved