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

Links

Table of n, a(n) for n=0..37.

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

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

Crossrefs

Cf. A210021, A277678.

Sequence in context: A232580 A133546 A190376 * A171844 A324971 A273387

Adjacent sequences: A276782 A276783 A276784 * A276786 A276787 A276788

Keyword

nonn,easy

Author

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

Status

approved