login
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

%I #19 Oct 05 2018 20:20:01

%S 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,

%T 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,

%U 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

%N 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.

%H Alois P. Heinz, <a href="/A240608/b240608.txt">Antidiagonals n = 0..36, flattened</a>

%e Square array A(n,k) begins:

%e 1, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 1, 1, 1, 1, 1, 1, 1, ...

%e 0, 1, 2, 2, 2, 2, 2, 2, 2, ...

%e 0, 1, 4, 5, 5, 5, 5, 5, 5, ...

%e 0, 1, 7, 13, 14, 14, 14, 14, 14, ...

%e 0, 1, 14, 35, 45, 46, 46, 46, 46, ...

%e 0, 1, 25, 94, 149, 164, 165, 165, 165, ...

%e 0, 1, 50, 254, 509, 629, 650, 651, 651, ...

%e 0, 1, 91, 688, 1756, 2511, 2742, 2770, 2771, ...

%p b:= proc(n, k, l) option remember; `if`(n=0, 1, `if`(nops(l)<k,

%p b(n-1, k, [l[], 1]), 0) +add(`if`(i=1 or l[i]<=l[i-1],

%p b(n-1, k, subsop(i=l[i]+1, l)), 0), i=1..nops(l)))

%p end:

%p A:= (n, k)-> b(n, min(k, n), []):

%p seq(seq(A(n, d-n), n=0..d), d=0..14);

%t 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_ *)

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

%Y Main diagonal gives A240617.

%Y Cf. A182172.

%K nonn,tabl

%O 0,13

%A _Alois P. Heinz_, Apr 09 2014