A240608 Number A(n,k) of n-length words w over a k-ary alphabet such that w is empty or a prefix z concatenated with letter a_i and i=1 or 0 < #(z,a_{i-1}) >= #(z,a_i), where #(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, 1, 1, 0, 1, 1, 2, 1, 0, 1, 1, 2, 4, 1, 0, 1, 1, 2, 5, 7, 1, 0, 1, 1, 2, 5, 13, 14, 1, 0, 1, 1, 2, 5, 14, 35, 25, 1, 0, 1, 1, 2, 5, 14, 45, 94, 50, 1, 0, 1, 1, 2, 5, 14, 46, 149, 254, 91, 1, 0, 1, 1, 2, 5, 14, 46, 164, 509, 688, 182, 1, 0, 1, 1, 2, 5, 14, 46, 165, 629, 1756, 1872, 336, 1, 0

Offset: 0

Author

Alois P. Heinz, Apr 09 2014

Keywords

• nonn
• tabl

Examples

			Square array A(n,k) begins:
  1, 1,  1,   1,    1,    1,    1,    1,    1, ...
  0, 1,  1,   1,    1,    1,    1,    1,    1, ...
  0, 1,  2,   2,    2,    2,    2,    2,    2, ...
  0, 1,  4,   5,    5,    5,    5,    5,    5, ...
  0, 1,  7,  13,   14,   14,   14,   14,   14, ...
  0, 1, 14,  35,   45,   46,   46,   46,   46, ...
  0, 1, 25,  94,  149,  164,  165,  165,  165, ...
  0, 1, 50, 254,  509,  629,  650,  651,  651, ...
  0, 1, 91, 688, 1756, 2511, 2742, 2770, 2771, ...
		

Links

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

Crossrefs

Columns k=0-10 give: A000007, A000012, A026010(n-1) for n>0, A240609, A240610, A240611, A240612, A240613, A240614, A240615, A240616.

Main diagonal gives A240617.

Cf. A182172.

Programs

Maple

b:= proc(n, k, l) option remember; `if`(n=0, 1, `if`(nops(l) b(n, min(k, n), []):
seq(seq(A(n, d-n), n=0..d), d=0..14);

Mathematica

b[n_, k_, l_List] := b[n, k, l] = If[n == 0, 1, If[Length[l] l[[i]]+1]], 0], {i, 1, Length[l]}]]; A[n_, k_] := b[n, Min[k, n], {}]; Table[ Table[A[n, d-n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Jan 19 2015, after Alois P. Heinz *)