A277678 Number T(n,k) of binary words of length n containing exactly k (possibly overlapping) occurrences of the subword 11011; 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, 437, 70, 5, 849, 158, 17, 1649, 351, 47, 1, 3202, 770, 118, 6, 6217, 1669, 283, 23, 12071, 3578, 664, 70, 1, 23438, 7599, 1535, 189, 7, 45510, 16016, 3500, 480, 30, 88368, 33545, 7876, 1182, 100, 1, 171586

Offset: 0

Author

Alois P. Heinz, Oct 26 2016

Keywords

• nonn
• tabf

Examples

			Triangle T(n,k) begins:
:     1;
:     2;
:     4;
:     8;
:    16;
:    31,   1;
:    60,   4;
:   116,  12;
:   225,  30,   1;
:   437,  70,   5;
:   849, 158,  17;
:  1649, 351,  47, 1;
:  3202, 770, 118, 6;
		

Links

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

Crossrefs

Column k=0 gives A210021.

Row sums give A000079.

Row sums except column k=0 give A276785.

Cf. A001787, A002264.

Programs

Maple

b:= proc(n, t) option remember; expand(
      `if`(n=0, 1,     b(n-1, [1, 1, 4, 1, 1][t])+
      `if`(t=5, x, 1)* b(n-1, [2, 3, 3, 5, 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^4+x^3+1), x^5*(x^3*(x^2+x-1))^(k-1))
                   /(x^5+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, {1, 1, 4, 1, 1}[[t]]] +
     If[t == 5, x, 1]*b[n-1, {2, 3, 3, 5, 3}[[t]]]]];
T[n_] := CoefficientList[b[n, 1], x];
Table[T[n], {n, 0, 20}] // Flatten (* Jean-François Alcover, Apr 29 2022, after Alois P. Heinz *)

Formula

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