A277751 Number T(n,k) of binary words of length n containing exactly k (possibly overlapping) occurrences of the subword 01101; triangle T(n,k), n>=0, k=0..max(0,floor((n-2)/3)), read by rows.

1, 2, 4, 8, 16, 31, 1, 60, 4, 116, 12, 225, 30, 1, 436, 72, 4, 845, 166, 13, 1637, 375, 35, 1, 3172, 828, 92, 4, 6146, 1802, 230, 14, 11909, 3872, 562, 40, 1, 23075, 8243, 1333, 113, 4, 44711, 17404, 3106, 300, 15, 86633, 36501, 7114, 778, 45, 1, 167863, 76104

Offset: 0

Author

Alois P. Heinz, Oct 28 2016

Keywords

• nonn
• tabf

Examples

			Triangle T(n,k) begins:
:     1;
:     2;
:     4;
:     8;
:    16;
:    31,   1;
:    60,   4;
:   116,  12;
:   225,  30,  1;
:   436,  72,  4;
:   845, 166, 13;
:  1637, 375, 35, 1;
:  3172, 828, 92, 4;
		

Links

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

Crossrefs

Columns k=0-2 give: A209888, A317780, A317781.

Row sums give A000079.

Cf. A001787, A317669.

Programs

Maple

b:= proc(n, t) option remember; expand(
      `if`(n=0, 1,     b(n-1, [2, 2, 2, 5, 2][t])+
      `if`(t=5, x, 1)* b(n-1, [1, 3, 4, 1, 3][t])))
    end:
T:= n-> (p-> seq(coeff(p, x, i), i=0..degree(p)))(b(n, 1)):
seq(T(n), n=0..20);
# second Maple program:
gf:= k-> `if`(k=0, (x+1)*(x^2-x+1), x^5*(x^3*(x-1)^2)^(k-1))
                   /(x^5-2*x^4+x^3-2*x+1)^(k+1):
T:= (n, k)-> coeff(series(gf(k), x, n+1), x, n):
seq(seq(T(n, k), k=0..max(0, floor((n-2)/3))), n=0..20);

Mathematica

b[n_, t_] := b[n, t] = Expand[
     If[n==0, 1,     b[n-1, {2, 2, 2, 5, 2}[[t]]] +
     If[t==5, x, 1]* b[n-1, {1, 3, 4, 1, 3}[[t]]]]];
T[n_] := CoefficientList[b[n, 1], x];
T /@ Range[0, 20] // Flatten (* Jean-François Alcover, Feb 22 2021, after first Maple program *)

Formula

G.f. of column k=0: (x+1)*(x^2-x+1)/(x^5-2*x^4+x^3-2*x+1); g.f. of column k>0: x^5*(x^3*(x-1)^2)^(k-1)/(x^5+x^4-x^3+2*x-1)^(k+1).

Sum_{k>=0} k * T(n,k) = A001787(n-4) for n > 3.