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,8

Comments

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

Links

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

Example

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

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 *)

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.

Sequence in context: A229557 A332700 A256268 * A069777 A225816 A227655

Adjacent sequences: A213272 A213273 A213274 * A213276 A213277 A213278

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 08 2012

Status

approved