A164410 Number of binary strings of length n with no substrings equal to 0000 0001 or 0101.

13, 22, 38, 64, 108, 184, 312, 528, 896, 1520, 2576, 4368, 7408, 12560, 21296, 36112, 61232, 103824, 176048, 298512, 506160, 858256, 1455280, 2467600, 4184112, 7094672, 12029872, 20398096, 34587440, 58647184, 99443376, 168618256

Offset: 4

Author

R. H. Hardin, Aug 14 2009

Keywords

• nonn

Links

• R. H. Hardin, Table of n, a(n) for n=4..500
• Index entries for linear recurrences with constant coefficients, signature (1,0,2).

Programs

Mathematica

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

PARI

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

Formula

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