A164411 Number of binary strings of length n with no substrings equal to 0000, 0001, or 0110.

1, 2, 4, 8, 13, 22, 37, 63, 108, 184, 314, 535, 912, 1555, 2651, 4520, 7706, 13138, 22399, 38188, 65107, 111001, 189246, 322646, 550080, 937833, 1598914, 2725993, 4647553, 7923626, 13509012, 23031552, 39266557, 66945662, 114135845, 194590519

Offset

0,2

Links

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

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

Formula

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

Mathematica

LinearRecurrence[{1, 1, 0, 0, 1}, {1, 2, 4, 8, 13}, 50] (* G. C. Greubel, Sep 19 2017 *)
CoefficientList[Series[(1 + x + x^2 + 2*x^3 + x^4)/(1 - x - x^2 - x^5), {x, 0, 50}], x] (* G. C. Greubel, Sep 21 2017 *)

Prog

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

Crossrefs

Sequence in context: A164428 A164507 A164414 * A164443 A074467 A018066

Adjacent sequences: A164408 A164409 A164410 * A164412 A164413 A164414

Keyword

nonn

Author

R. H. Hardin, Aug 14 2009

Status

approved