A265725 Number of binary strings of length n having at least one run of length at least 4.

0, 0, 0, 0, 2, 6, 16, 40, 94, 214, 476, 1040, 2242, 4782, 10112, 21232, 44318, 92046, 190364, 392264, 805746, 1650518, 3372816, 6877656, 13998142, 28442918, 57707324, 116925600, 236630274, 478372062, 966145664, 1949583456, 3930972094, 7920443038, 15948482236

Offset: 0

Author

Jeffrey Shallit, Dec 14 2015

Keywords

• nonn

Comments

A "run" is a contiguous block of consecutive identical terms.

Examples

			For n=5 there are 6 such strings: 00000, 00001, 01111, and their complements.
		

Crossrefs

Cf. A000073, A050231, A167821.

Programs

PARI

x='x+O('x^100); concat(vector(4), Vec(2*x^4/((2*x-1)*(x^3+x^2+x-1)))) \\ Altug Alkan, Dec 14 2015

Formula

a(n) = 2^n - 2*A000073(n+2).

a(n) = 2*A050231(n-1) for n>0.

G.f.: 2*x^4/((2*x-1)*(x^3+x^2+x-1)). - Alois P. Heinz, Dec 14 2015

Extensions

More terms from Alois P. Heinz, Dec 14 2015