A213276 Number A(n,k) of n-length words w over a k-ary alphabet such that 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, 0, 1, 1, 0, 1, 2, 1, 0, 1, 3, 4, 1, 0, 1, 4, 9, 5, 1, 0, 1, 5, 16, 18, 9, 1, 0, 1, 6, 25, 46, 36, 14, 1, 0, 1, 7, 36, 95, 118, 74, 27, 1, 0, 1, 8, 49, 171, 315, 276, 165, 46, 1, 0, 1, 9, 64, 280, 711, 895, 712, 367, 91, 1, 0, 1, 10, 81, 428, 1414, 2506, 2535, 1805, 869, 162, 1, 0

Offset

0,8

Links

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

Formula

T(n,k) = Sum_{i=0..k} C(k,i) * A257783(n,k-i).

Example

A(0,k) = 1: the empty word.
A(n,1) = 1: (a)^n for alphabet {a}.
A(1,k) = k: number of words = size of the alphabet.
A(2,k) = k^2: all words with 2 letters from the alphabet.
A(3,2) = 5: aaa, aab, aba, baa, bbb for alphabet {a,b}.
A(3,3) = 18: aaa, aab, aac, aba, abc, aca, acb, baa, bac, bbb, bbc, bca, bcb, caa, cab, cba, cbb, ccc.
A(4,2) = 9: aaaa, aaab, aaba, aabb, abaa, abab, baaa, baab, bbbb.
A(5,2) = 14: aaaaa, aaaab, aaaba, aaabb, aabaa, aabab, aabba, abaaa, abaab, ababa, baaaa, baaab, baaba, bbbbb.
Square array A(n,k) begins:
  1, 1,  1,   1,    1,    1,     1,     1, ...
  0, 1,  2,   3,    4,    5,     6,     7, ...
  0, 1,  4,   9,   16,   25,    36,    49, ...
  0, 1,  5,  18,   46,   95,   171,   280, ...
  0, 1,  9,  36,  118,  315,   711,  1414, ...
  0, 1, 14,  74,  276,  895,  2506,  6104, ...
  0, 1, 27, 165,  712, 2535,  8151, 23527, ...
  0, 1, 46, 367, 1805, 7280, 25781, 83916, ...

Maple

A:= (n, k)-> h(n, k, 0, []):
h:= proc(n, k, m, l) option remember;
      `if`(n=0 and k=0, b(l), `if`(k=0 or n>0 and n<m, 0,
       add(h(n-j, k-1, max(m, j), [j, l[]]), j=max(1, m)..n)
          +h(n, k-1, m, [0, l[]], [])))
    end:
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..14);

Mathematica

a[n_, k_] := h[n, k, 0, {}];
h[n_, k_, m_, l_] := h[n, k, m, l] = If[n == 0 && k === 0, b[l], If[k == 0 || n > 0 && n < m, 0, Sum[h[n-j, k-1, Max[m, j], Join[{j}, l]], {j, Max[1, m], n}] + h[n, k-1, m, Join[{0}, l]]]];
b[l_] := b[l] = If[Complement[l, {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, 14}] // Flatten (* Jean-François Alcover, Dec 11 2013, translated from Maple *)

Crossrefs

Columns k=0-10 give: A000007, A000012, A213290, A213291, A213292, A213293, A213294, A213295, A213296, A213297, A213298.

Rows n=0-10 give: A000012, A001477, A000290, A081435(k-1), A213283, A213284, A213285, A213286, A213287, A213288, A213289.

Main diagonal gives A321704.

Cf. A182172, A213275, A257783.

Sequence in context: A361952 A323224 A118340 * A210391 A071921 A003992

Adjacent sequences: A213273 A213274 A213275 * A213277 A213278 A213279

Keyword

nonn,tabl

Author

Alois P. Heinz, Jun 08 2012

Status

approved