login
Number A(n,k) of words w where each letter of the k-ary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z; square array A(n,k), n>=0, k>=0, read by antidiagonals.
19

%I #29 Sep 14 2021 13:19:45

%S 1,1,1,1,1,1,1,2,1,1,1,6,3,1,1,1,24,15,7,1,1,1,120,105,106,19,1,1,1,

%T 720,945,2575,1075,56,1,1,1,5040,10395,87595,115955,13326,174,1,1,1,

%U 40320,135135,3864040,19558470,7364321,188196,561,1,1

%N Number A(n,k) of words w where each letter of the k-ary alphabet occurs n times and for every prefix z of w we have #(z,a_i) = 0 or #(z,a_i) >= #(z,a_j) for all j>i and #(z,a_i) counts the occurrences of the i-th letter in z; square array A(n,k), n>=0, k>=0, read by antidiagonals.

%C The words counted by A(n,k) have length n*k.

%H Alois P. Heinz, <a href="/A213275/b213275.txt">Antidiagonals n = 0..20, flattened</a>

%e A(0,k) = A(n,0) = 1: the empty word.

%e A(n,1) = 1: (a)^n for alphabet {a}.

%e A(1,2) = 2: ab, ba for alphabet {a,b}.

%e A(1,3) = 6: abc, acb, bac, bca, cab, cba for alphabet {a,b,c}.

%e A(2,2) = 3: aabb, abab, baab.

%e A(2,3) = 15: aabbcc, aabcbc, aacbbc, ababcc, abacbc, abcabc, acabbc, acbabc, baabcc, baacbc, bacabc, bcaabc, caabbc, cababc, cbaabc.

%e A(3,2) = 7: aaabbb, aababb, aabbab, abaabb, ababab, baaabb, baabab.

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

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

%e 1, 1, 2, 6, 24, 120, 720, ...

%e 1, 1, 3, 15, 105, 945, 10395, ...

%e 1, 1, 7, 106, 2575, 87595, 3864040, ...

%e 1, 1, 19, 1075, 115955, 19558470, 4622269345, ...

%e 1, 1, 56, 13326, 7364321, 7236515981, 10915151070941, ...

%e 1, 1, 174, 188196, 586368681, 3745777177366, 40684710729862072, ...

%p A:= (n, k)-> b([n$k]):

%p b:= proc(l) option remember;

%p `if`({l[]} minus {0}={}, 1, add(`if`(g(l, i),

%p b(subsop(i=l[i]-1, l)), 0), i=1..nops(l)))

%p end:

%p g:= proc(l, i) local j;

%p if l[i]<1 then return false

%p elif l[i]>1 then for j from i+1 to nops(l) do

%p if l[i]<=l[j] then return false

%p elif l[j]>0 then break

%p fi od fi; true

%p end:

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

%t a[n_, k_] := b[Array[n&, k]];

%t b[l_] := b[l] = If[l ~Complement~ {0} == {}, 1, Sum[If[g[l, i], b[ReplacePart[l, i -> l[[i]] - 1]], 0], {i, 1, Length[l]}]];

%t g[l_, i_] := Module[{j},

%t If[l[[i]] < 1, Return[False],

%t If[l[[i]] > 1, For[j = i+1, j <= Length[l], j++,

%t If[l[[i]] <= l[[j]], Return[False],

%t If[l[[j]] > 0, Break[]]]]]]; True];

%t Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* _Jean-François Alcover_, Dec 16 2013, translated from Maple *)

%Y Rows n=0-10 give: A000012, A000142, A001147, A213863, A213864, A213865, A213866, A213867, A213868, A213869, A213870.

%Y Columns k=0+1, 2-10 give: A000012, A005807(n-1) for n>0, A213873, A213874, A213875, A213876, A213877, A213878, A213871, A213872.

%Y Main diagonal gives A213862.

%Y Cf. A213276.

%K nonn,tabl

%O 0,8

%A _Alois P. Heinz_, Jun 08 2012