A164409 Number of binary strings of length n with no substrings equal to 0000 0001 or 0100.

13, 22, 39, 69, 121, 212, 372, 653, 1146, 2011, 3529, 6193, 10868, 19072, 33469, 58734, 103071, 180877, 317417, 557028, 977516, 1715421, 3010354, 5282803, 9270673, 16268897, 28549924, 50101624, 87922221, 154292742, 270764887, 475159253

Offset

4,1

Links

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

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

Formula

G.f.: x^4*(13-4*x+8*x^2)/(1-2*x+x^2-x^3). - R. J. Mathar, Nov 30 2011

Mathematica

LinearRecurrence[{2, -1, 1}, {13, 22, 39}, 50] (* G. C. Greubel, Sep 19 2017 *)

Prog

(PARI) my(x='x+O('x^50)); Vec(x^4*(13-4*x+8*x^2)/(1-2*x+x^2-x^3)) \\ G. C. Greubel, Sep 19 2017

Crossrefs

Sequence in context: A164445 A164418 A301788 * A301962 A298235 A111676

Adjacent sequences: A164406 A164407 A164408 * A164410 A164411 A164412

Keyword

nonn,easy

Author

R. H. Hardin, Aug 14 2009

Status

approved