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

1, 2, 4, 8, 13, 23, 40, 68, 118, 203, 349, 602, 1036, 1784, 3073, 5291, 9112, 15692, 27022, 46535, 80137, 138002, 237652, 409256, 704773, 1213679, 2090056, 3599252, 6198214, 10673843, 18381253, 31654058, 54510940, 93872408, 161656153, 278385443, 479403064

Offset: 0

Author

R. H. Hardin, Aug 14 2009

Keywords

• nonn
• easy

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2000 (500 terms from R. H. Hardin)
• Index entries for linear recurrences with constant coefficients, signature (1,1,1,-1).

Programs

Mathematica

CoefficientList[Series[(13 + 10*x + 4*x^2 - 8*x^3)/(1 - x - x^2 - x^3 + x^4), {x, 0, 50}], x] (* Wesley Ivan Hurt, Jan 10 2017 *)
LinearRecurrence[{1,1,1,-1}, {13, 23, 40, 68}, 50] (* G. C. Greubel, Sep 19 2017 *)

PARI

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

Formula

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

Extensions

Edited by Alois P. Heinz, Dec 30 2023