login
Number A(n,k) of n-length words w over a k-ary alphabet {a1,a2,...,ak} such that #(w,a1) >= #(w,a2) >= ... >= #(w,ak) >= 0, where #(w,x) counts the letters x in word w; square array A(n,k), n>=0, k>=0, read by antidiagonals.
27

%I #23 Sep 06 2018 12:30:42

%S 1,1,0,1,1,0,1,1,1,0,1,1,3,1,0,1,1,3,4,1,0,1,1,3,10,11,1,0,1,1,3,10,

%T 23,16,1,0,1,1,3,10,47,66,42,1,0,1,1,3,10,47,126,222,64,1,0,1,1,3,10,

%U 47,246,522,561,163,1,0,1,1,3,10,47,246,882,1821,1647,256,1,0

%N Number A(n,k) of n-length words w over a k-ary alphabet {a1,a2,...,ak} such that #(w,a1) >= #(w,a2) >= ... >= #(w,ak) >= 0, where #(w,x) counts the letters x in word w; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%H Alois P. Heinz, <a href="/A226873/b226873.txt">Antidiagonals n = 0..140, flattened</a>

%F A(n,k) = Sum_{i=0..min(n,k)} A226874(n,i).

%e A(4,3) = 23: aaaa, aaab, aaba, aabb, aabc, aacb, abaa, abab, abac, abba, abca, acab, acba, baaa, baab, baac, baba, baca, bbaa, bcaa, caab, caba, cbaa.

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 3, 3, 3, 3, 3, 3, ...

%e 0, 1, 4, 10, 10, 10, 10, 10, ...

%e 0, 1, 11, 23, 47, 47, 47, 47, ...

%e 0, 1, 16, 66, 126, 246, 246, 246, ...

%e 0, 1, 42, 222, 522, 882, 1602, 1602, ...

%e 0, 1, 64, 561, 1821, 3921, 6441, 11481, ...

%p b:= proc(n, i, t) option remember;

%p `if`(t=1, 1/n!, add(b(n-j, j, t-1)/j!, j=i..n/t))

%p end:

%p A:= (n, k)-> `if`(k=0, `if`(n=0, 1, 0), n!*b(n, 0, k)):

%p seq(seq(A(n, d-n), n=0..d), d=0..14);

%t 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}]]; a[n_, k_] := If[k == 0, If[n == 0, 1, 0], n!*b[n, 0, k]]; Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* _Jean-François Alcover_, Dec 13 2013, translated from Maple *)

%Y Columns k=0-10 give: A000007, A000012, A027306, A092255, A092429, A226875, A226876, A226877, A226878, A226879, A226880.

%Y Main diagonal gives: A005651.

%Y Cf. A131632, A182172.

%K nonn,tabl

%O 0,13

%A _Alois P. Heinz_, Jun 21 2013