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

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

Main diagonal gives A128588(n+1).

Cf. A000045, A307796.

Sequence in context: A243851 A168266 A059250 * A131074 A059268 A300653

Adjacent sequences: A303693 A303694 A303695 * A303697 A303698 A303699

Keyword

nonn,tabl

Author

Alois P. Heinz, Apr 28 2018

Status

approved