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

Comments

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

Links

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

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

Example

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

Prog

(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

Crossrefs

Cf. A000073, A050231, A167821.

Sequence in context: A371709 A078774 A174016 * A129952 A057711 A302239

Adjacent sequences: A265722 A265723 A265724 * A265726 A265727 A265728

Keyword

nonn

Author

Jeffrey Shallit, Dec 14 2015

Extensions

More terms from Alois P. Heinz, Dec 14 2015

Status

approved