A276785 Number of binary strings of length n containing the substring 11011.

0, 0, 0, 0, 0, 1, 4, 12, 31, 75, 175, 399, 894, 1975, 4313, 9330, 20026, 42704, 90558, 191117, 401654, 841016, 1755249, 3652663, 7581369, 15698735, 32438224, 66897295, 137718495, 283056086, 580906268, 1190538424, 2436854280, 4982012329, 10174319500, 20756971236, 42306806495, 86153127395

Offset: 0

Author

N. J. A. Sloane, Oct 05 2016, following a suggestion from Rick L. Shepherd

Keywords

• nonn
• easy

Links

• Aashir Shukla et al., How many Binary Strings of length N contain within it the substring '11011'?, Mathematics Stack Exchange, circa Sep 09 2016.

Crossrefs

Cf. A210021, A277678.

Formula

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

Equals 2^n - A210021(n).

a(n) = Sum_{k>0} A277678(n,k). - Alois P. Heinz, Oct 26 2016