A164393 Number of binary strings of length n with no substrings equal to 0001 or 0011.

1, 2, 4, 8, 14, 25, 44, 76, 132, 228, 393, 678, 1168, 2012, 3466, 5969, 10280, 17704, 30488, 52504, 90417, 155706, 268140, 461760, 795190, 1369385, 2358196, 4061012, 6993404, 12043228, 20739449, 35715070, 61504344, 105915636, 182395602, 314100513

Offset

0,2

Links

R. H. Hardin, Table of n, a(n) for n = 0..500

Index entries for linear recurrences with constant coefficients, signature (2,0,0,-2,1).

Formula

a(n) = 2*a(n-1) - 2*a(n-4) + a(n-5). - Andrew Howroyd, Feb 14 2018

G.f.: 1/((1 - x)*(1 - x - x^2 - x^3 + x^4)). - R. J. Mathar, Dec 01 2011

Mathematica

LinearRecurrence[{2, 0, 0, -2, 1}, {1, 2, 4, 8, 14}, 50] (* G. C. Greubel, Sep 18 2017 *)

Prog

(PARI) Vec(1/((1 - x)*(1 - x - x^2 - x^3 + x^4)) + O(x^40)) \\ G. C. Greubel, Sep 18 2017

Crossrefs

Sequence in context: A291443 A210145 A020956 * A164391 A164153 A212588

Adjacent sequences: A164390 A164391 A164392 * A164394 A164395 A164396

Keyword

nonn

Author

R. H. Hardin, Aug 14 2009

Extensions

a(0)-a(3) prepended by Andrew Howroyd, Feb 14 2018

Status

approved