login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

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.
11
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
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
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Apr 09 2014
STATUS
approved