A307796 Number T(n,k) of binary words of length n such that k is the difference of numbers of occurrences of subword 101 and subword 010; triangle T(n,k), n>=0, -floor(n/3)<=k<=floor(n/3), read by rows.

1, 2, 4, 1, 6, 1, 2, 12, 2, 6, 20, 6, 1, 12, 38, 12, 1, 3, 28, 66, 28, 3, 10, 56, 124, 56, 10, 1, 24, 119, 224, 119, 24, 1, 4, 60, 236, 424, 236, 60, 4, 15, 134, 481, 788, 481, 134, 15, 1, 42, 304, 950, 1502, 950, 304, 42, 1, 5, 114, 656, 1902, 2838, 1902, 656, 114, 5

Offset: 0

Author

Alois P. Heinz, Apr 29 2019

Keywords

• nonn
• tabf

Examples

			T(8,2) = 10: 01101101, 10101101, 10110101, 10110110, 10110111, 10111011, 10111101, 11011011, 11011101, 11101101.
T(8,-2) = 10: 00010010, 00100010, 00100100, 01000010, 01000100, 01001000, 01001001, 01001010, 01010010, 10010010.
T(9,3)  = 1: 101101101.
T(9,-3) = 1: 010010010.
Triangle T(n,k) begins:
  :                      1                   ;
  :                      2                   ;
  :                      4                   ;
  :                1,    6,   1              ;
  :                2,   12,   2              ;
  :                6,   20,   6              ;
  :           1,  12,   38,  12,   1         ;
  :           3,  28,   66,  28,   3         ;
  :          10,  56,  124,  56,  10         ;
  :      1,  24, 119,  224, 119,  24,  1     ;
  :      4,  60, 236,  424, 236,  60,  4     ;
  :     15, 134, 481,  788, 481, 134, 15     ;
  :  1, 42, 304, 950, 1502, 950, 304, 42, 1  ;
		

Links

• Alois P. Heinz, Rows n = 0..250, flattened

Crossrefs

Columns k=0-2 give: A164146, A284449, A286209.

Row sums give A000079.

T(3n-4,n-2) gives A000217 for n >= 3.

Cf. A002264, A057711, A303696.

Programs

Maple

b:= proc(n, t, h) option remember; `if`(n=0, 1, expand(
      `if`(h=3, 1/x, 1)*b(n-1, [1, 3, 1][t], 2)+
      `if`(t=3, x, 1)*b(n-1, 2, [1, 3, 1][h])))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=-iquo(n, 3)..iquo(n, 3)))(b(n, 1$2)):
seq(T(n), n=0..15);

Mathematica

b[n_, t_, h_] := b[n, t, h] = If[n == 0, 1, Expand[If[h == 3, 1/x, 1]* b[n-1, {1, 3, 1}[[t]], 2] + If[t == 3, x, 1]*b[n-1, 2, {1, 3, 1}[[h]]]]];
T[n_] := Table[Coefficient[#, x, i], {i, -Quotient[n, 3], Quotient[n, 3]}]& @ b[n, 1, 1];
Table[T[n], {n, 0, 15}] // Flatten (* Jean-François Alcover, May 08 2019, after Alois P. Heinz *)

Formula

T(n,k) = T(n,-k).

Sum_{k = -floor(n/3)..floor(n/3)} T(n,k) * k^2/2 = A057711(n-2) for n > 1.