OFFSET
0,3
COMMENTS
A(n,n) is the number of binary words of length n avoiding both subwords 101 and 010. A(4,4) = 10: 0000, 0001, 0011, 0110, 0111, 1000, 1001, 1100, 1110, 1111.
LINKS
Alois P. Heinz, Antidiagonals for n = 0..200, flattened
FORMULA
ceiling(A(n,n)/2) = A000045(n+1).
EXAMPLE
Square array A(n,k) begins:
1, 1, 1, 1, 1, 1, 1, ...
2, 2, 2, 2, 2, 2, 2, ...
4, 4, 4, 4, 4, 4, 4, ...
7, 6, 6, 6, 6, 6, 6, ...
12, 12, 10, 10, 10, 10, 10, ...
21, 20, 17, 16, 16, 16, 16, ...
37, 38, 28, 26, 26, 26, 26, ...
65, 66, 49, 42, 42, 42, 42, ...
114, 124, 84, 70, 68, 68, 68, ...
200, 224, 148, 116, 110, 110, 110, ...
351, 424, 263, 196, 178, 178, 178, ...
MAPLE
b:= proc(n, t, h, c, k) option remember; `if`(abs(c)>k*n, 0,
`if`(n=0, 1, b(n-1, [1, 3, 1][t], 2, c-`if`(h=3, k, 0), k)
+ b(n-1, 2, [1, 3, 1][h], c+`if`(t=3, 1, 0), k)))
end:
A:= (n, k)-> b(n, 1$2, 0, min(k, n)):
seq(seq(A(n, d-n), n=0..d), d=0..14);
MATHEMATICA
b[n_, t_, h_, c_, k_] := b[n, t, h, c, k] = If[Abs[c] > k n, 0, If[n == 0, 1, b[n - 1, {1, 3, 1}[[t]], 2, c - If[h == 3, k, 0], k] + b[n - 1, 2, {1, 3, 1}[[h]], c + If[t == 3, 1, 0], k]]];
A[n_, k_] := b[n, 1, 1, 0, Min[k, n]];
Table[Table[A[n, d - n], {n, 0, d}], {d, 0, 14}] // Flatten (* Jean-François Alcover, Mar 20 2020, from Maple *)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Alois P. Heinz, Apr 28 2018
STATUS
approved