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

%I #13 Dec 15 2015 06:17:58

%S 0,0,0,0,2,6,16,40,94,214,476,1040,2242,4782,10112,21232,44318,92046,

%T 190364,392264,805746,1650518,3372816,6877656,13998142,28442918,

%U 57707324,116925600,236630274,478372062,966145664,1949583456,3930972094,7920443038,15948482236

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

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

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

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

%F G.f.: 2*x^4/((2*x-1)*(x^3+x^2+x-1)). - _Alois P. Heinz_, Dec 14 2015

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

%o (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

%Y Cf. A000073, A050231, A167821.

%K nonn

%O 0,5

%A _Jeffrey Shallit_, Dec 14 2015

%E More terms from _Alois P. Heinz_, Dec 14 2015