A303696 Number A(n,k) of binary words of length n with k times as many occurrences of subword 101 as occurrences of subword 010; square array A(n,k), n>=0, k>=0, read by antidiagonals.

1, 1, 2, 1, 2, 4, 1, 2, 4, 7, 1, 2, 4, 6, 12, 1, 2, 4, 6, 12, 21, 1, 2, 4, 6, 10, 20, 37, 1, 2, 4, 6, 10, 17, 38, 65, 1, 2, 4, 6, 10, 16, 28, 66, 114, 1, 2, 4, 6, 10, 16, 26, 49, 124, 200, 1, 2, 4, 6, 10, 16, 26, 42, 84, 224, 351, 1, 2, 4, 6, 10, 16, 26, 42, 70, 148, 424, 616

Offset: 0

Author

Alois P. Heinz, Apr 28 2018

Keywords

• nonn
• tabl

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.

Examples

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

Links

• Alois P. Heinz, Antidiagonals for n = 0..200, flattened

Crossrefs

Columns k=0-3 give: A005251(n+3), A164146, A303430, A307795.

Main diagonal gives A128588(n+1).

Cf. A000045, A307796.

Programs

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 *)

Formula

ceiling(A(n,n)/2) = A000045(n+1).