A213275 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.

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, 720, 945, 2575, 1075, 56, 1, 1, 1, 5040, 10395, 87595, 115955, 13326, 174, 1, 1, 1, 40320, 135135, 3864040, 19558470, 7364321, 188196, 561, 1, 1

Offset: 0

Author

Alois P. Heinz, Jun 08 2012

Keywords

• nonn
• tabl

Comments

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

Examples

			A(0,k) = A(n,0) = 1: the empty word.
A(n,1) = 1: (a)^n for alphabet {a}.
A(1,2) = 2: ab, ba for alphabet {a,b}.
A(1,3) = 6: abc, acb, bac, bca, cab, cba for alphabet {a,b,c}.
A(2,2) = 3: aabb, abab, baab.
A(2,3) = 15: aabbcc, aabcbc, aacbbc, ababcc, abacbc, abcabc, acabbc, acbabc, baabcc, baacbc, bacabc, bcaabc, caabbc, cababc, cbaabc.
A(3,2) = 7: aaabbb, aababb, aabbab, abaabb, ababab, baaabb, baabab.
Square array A(n,k) begins:
  1, 1,   1,      1,         1,             1,                 1, ...
  1, 1,   2,      6,        24,           120,               720, ...
  1, 1,   3,     15,       105,           945,             10395, ...
  1, 1,   7,    106,      2575,         87595,           3864040, ...
  1, 1,  19,   1075,    115955,      19558470,        4622269345, ...
  1, 1,  56,  13326,   7364321,    7236515981,    10915151070941, ...
  1, 1, 174, 188196, 586368681, 3745777177366, 40684710729862072, ...
		

Links

• Alois P. Heinz, Antidiagonals n = 0..20, flattened

Crossrefs

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

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

Main diagonal gives A213862.

Cf. A213276.

Programs

Maple

A:= (n, k)-> b([n$k]):
b:= proc(l) option remember;
      `if`({l[]} minus {0}={}, 1, add(`if`(g(l, i),
       b(subsop(i=l[i]-1, l)), 0), i=1..nops(l)))
    end:
g:= proc(l, i) local j;
      if l[i]<1     then return false
    elif l[i]>1     then for j from i+1 to nops(l) do
      if l[i]<=l[j] then return false
    elif l[j]>0     then break
      fi od fi; true
    end:
seq(seq(A(n, d-n), n=0..d), d=0..12);

Mathematica

a[n_, k_] := b[Array[n&, k]];
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]}]];
g[l_, i_] := Module[{j},
     If[l[[i]] < 1, Return[False],
     If[l[[i]] > 1, For[j = i+1, j <= Length[l], j++,
     If[l[[i]] <= l[[j]], Return[False],
     If[l[[j]] > 0, Break[]]]]]]; True];
Table[Table[a[n, d-n], {n, 0, d}], {d, 0, 12}] // Flatten (* Jean-François Alcover, Dec 16 2013, translated from Maple *)