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

Links

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

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.

Example

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;

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

Crossrefs

Column k=0 gives A210021.

Row sums give A000079.

Row sums except column k=0 give A276785.

Cf. A001787, A002264.

Sequence in context: A244825 A220843 A277751 * A018763 A054517 A054016

Adjacent sequences: A277675 A277676 A277677 * A277679 A277680 A277681

Keyword

nonn,tabf

Author

Alois P. Heinz, Oct 26 2016

Status

approved