A276785 -id:A276785 - cp's OEIS frontend

A210021 Number of binary words of length n containing no subword 11011.

1, 2, 4, 8, 16, 31, 60, 116, 225, 437, 849, 1649, 3202, 6217, 12071, 23438, 45510, 88368, 171586, 333171, 646922, 1256136, 2439055, 4735945, 9195847, 17855697, 34670640, 67320433, 130716961, 253814826, 492835556, 956945224, 1858113016, 3607922263, 7005549684

Offset: 0

Alois P. Heinz, Mar 16 2012

			a(7) = 116 because among the 2^7 = 128 binary words of length 7 only 12, namely 0011011, 0110110, 0110111, 0111011, 1011011, 1101100, 1101101, 1101110, 1101111, 1110110, 1110111 and 1111011 contain the subword 11011.

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Aashir Shukla et al., How many Binary Strings of length N contain within it the substring '11011'?, Mathematics Stack Exchange, circa Sep 09 2016.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1,1).

Column k=27 of A209972. Cf. A276785.

Column k=0 of A277678.

I:=[1,2,4,8,16]; [n le 5 select I[n] else 2*Self(n-1)-Self(n-3)+Self(n-4)+Self(n-5): n in [1..40]]; // Vincenzo Librandi, Oct 24 2016

a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>, <0|0|0|0|1>, <1|1|-1|0|2>>^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);

LinearRecurrence[{2, 0, -1, 1, 1}, {1, 2, 4, 8, 16}, 40] (* Vincenzo Librandi, Oct 24 2016 *)

G.f.: -(x^4+x^3+1)/(x^5+x^4-x^3+2*x-1).

a(n) = 2^n if n<5, and a(n) = 2*a(n-1) -a(n-3) +a(n-4) +a(n-5) otherwise.

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.

Original entry on oeis.org

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

Alois P. Heinz, Oct 26 2016

			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;

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

Column k=0 gives A210021.
Row sums give A000079.
Row sums except column k=0 give A276785.
Cf. A001787, A002264.

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

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

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.

cp's OEIS Frontend

A210021 Number of binary words of length n containing no subword 11011.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Magma

Maple

Mathematica

Formula