A164412 Number of binary strings of length n with no substrings equal to 0000 0001 or 0111.

13, 22, 37, 60, 98, 160, 259, 420, 681, 1102, 1784, 2888, 4673, 7562, 12237, 19800, 32038, 51840, 83879, 135720, 219601, 355322, 574924, 930248, 1505173, 2435422, 3940597, 6376020, 10316618, 16692640, 27009259, 43701900, 70711161, 114413062

Offset

4,1

Links

G. C. Greubel, Table of n, a(n) for n = 4..1000 (terms 4..500 from R. H. Hardin)

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

Formula

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

Mathematica

Rest[Rest[Rest[Rest[CoefficientList[Series[-x^4*(-13 - 9*x - 2*x^2 + 12*x^3 + 8*x^4)/((x - 1)*(1 + x + x^2)*(x^2 + x - 1)), {x, 0, 50}], x]]]]] (* G. C. Greubel, Oct 01 2017 *)

Prog

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

Crossrefs

Sequence in context: A162245 A159302 A172187 * A164472 A164446 A164506

Adjacent sequences: A164409 A164410 A164411 * A164413 A164414 A164415

Keyword

nonn

Author

R. H. Hardin, Aug 14 2009

Status

approved