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

Links

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

Example

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

Maple

b:= proc(n, k, l) option remember; `if`(n=0, 1, `if`(nops(l)<k,
      b(n-1, k, [l[], 1]), 0) +add(`if`(i=1 or l[i]<=l[i-1],
      b(n-1, k, subsop(i=l[i]+1, l)), 0), i=1..nops(l)))
    end:
A:= (n, k)-> 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]<k, b[n-1, k, Append[l, 1]], 0] + Sum[If[i == 1 || l[[i]] <= l[[i-1]], b[n-1, k, ReplacePart[l, i -> 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 *)

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.

Sequence in context: A182458 A238093 A238095 * A080934 A320955 A288942

Adjacent sequences: A240605 A240606 A240607 * A240609 A240610 A240611

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 09 2014

Status

approved