This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A118645 Number of binary strings of length n such that there exist three consecutive digits where at least two of them are 1's. 1
 0, 0, 1, 4, 10, 23, 51, 109, 228, 471, 964, 1960, 3967, 8003, 16107, 32362, 64941, 130200, 260866, 522415, 1045831, 2093129, 4188408, 8379967, 16764552, 33535872, 67081663, 134177863, 268377031, 536785286, 1073616333, 2147299732 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,4 COMMENTS We set a(2) = 1 by convention; there is one string of length 2 which has two consecutive 1's, namely 11. This also makes various formulas simpler. For n>=3, a(n) = 2^n - the sum of all terms in the (n-3)rd power of the 4 X 4 matrix [[1 1 0 0] [0 0 1 0] [0 0 0 1] [1 1 0 0]] because this matrix represents the transitions from the state where the last three bits are 000, 001, 010, 100 to the state after the next bit, always avoiding two 1's out of the last three bits. - Joshua Zucker, Aug 04 2006 Complementary to A048625 which starts 4,6,9,13,19,28,41,60,88,129,189. For n >= 3, a(n) + A048625(n-3) = 2^n. A048625 is a subsequence of A000930, A068921 and A078012. All of them satisfy the recurrence a(n) = a(n-1) + a(n-3). - Tanya Khovanova, Aug 22 2006 LINKS G. C. Greubel, Table of n, a(n) for n = 0..1000 Index entries for linear recurrences with constant coefficients, signature (3,-2,1,-2). FORMULA a(n) = 3*2^(n-3) + a(n-1) + a(n-3) for n >= 3. - Tanya Khovanova, Aug 22 2006 From R. J. Mathar, Oct 03 2011: (Start) G.f.: (x^3 + x^2)/(2*x^4 - x^3 + 2*x^2 - 3*x + 1). G.f.: x^2 * (x+1)/((2*x-1)*(x^3+x-1)). a(n) = 2^n - A000930(n+2). (End) EXAMPLE a(4) = 10 because we have: 0011, 0101, 0110, 0111, 1010, 1011, 1100, 1101, 1110, 1111. - Geoffrey Critzer, Jan 19 2014 MATHEMATICA nn=31; r=Solve[{s==1+x s+x b, a==x s, b==x a, c==x a+x b+2x c}, {s, a, b, c}]; CoefficientList[Series[c/.r, {x, 0, nn}], x] (* Geoffrey Critzer, Jan 19 2014 *) LinearRecurrence[{3, -2, 1, -2}, {0, 0, 1, 4}, 40] (* Harvey P. Dale, Dec 15 2014 *) PROG (PARI) x='x+O('x^50); concat([0, 0], Vec((x^3 + x^2)/(2*x^4 - x^3 + 2*x^2 - 3*x + 1))) \\ G. C. Greubel, May 02 2017 CROSSREFS Sequence in context: A266376 A057750 A295059 * A200759 A159347 A137531 Adjacent sequences:  A118642 A118643 A118644 * A118646 A118647 A118648 KEYWORD nonn,easy AUTHOR Tanya Khovanova, May 10 2006 EXTENSIONS More terms from Joshua Zucker, Aug 04 2006 Edited by Franklin T. Adams-Watters, Sep 30 2011 STATUS approved

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

Last modified November 13 19:25 EST 2018. Contains 317149 sequences. (Running on oeis4.)