This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A118646 a(n) is the number of binary strings of length n such that there exists a subsequence of length 4 containing 3 or more ones. 3

%I

%S 0,0,1,5,13,31,71,159,346,739,1559,3258,6756,13922,28547,58300,118668,

%T 240880,487835,986085,1990025,4010658,8073786,16237521,32629241,

%U 65522823,131498801,263774439,528880599,1060044148,2124001923

%N a(n) is the number of binary strings of length n such that there exists a subsequence of length 4 containing 3 or more ones.

%C Or there are 3 ones in a row - this is relevant only for a(3).

%C Complementary to A118647, namely a(n) = 2^(n+3) - A118647(n).

%H <a href="/index/Rec#recLCC">Index to sequences with linear recurrences with constant coefficients</a>, signature (3,-1,-2,1,-2,-1,2).

%F a(n) = a(n-1) + a(n-2) + a(n-4) - a(n-6) + 13*2^(n-6).

%F a(n)= +3*a(n-1) -a(n-2) -2*a(n-3) +a(n-4) -2*a(n-5) -a(n-6) +2*a(n-7).

%F G.f. x^3*(-1-2*x+x^2+x^3) / ( (2*x-1)*(x^6-x^4-x^2-x+1) ). - R. J. Mathar, Nov 28 2011

%e a(4) is 5 because only the following binary strings of length 4 satisfy the conditions: 0111, 1011, 1101, 1011, 1111.

%K nonn

%O 1,4

%A _Tanya Khovanova_, May 10 2006, Aug 17 2006

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Puzzles | Hot | Classics
Recent Additions | More pages | Superseeker | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .