

A164391


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


1



1, 2, 4, 8, 14, 25, 44, 77, 134, 233, 405, 703, 1220, 2117, 3673, 6372, 11054, 19176, 33265, 57705, 100101, 173645, 301221, 522526, 906422, 1572363, 2727565, 4731484, 8207665, 14237766, 24698130, 42843633, 74320480, 128923094, 223641776, 387949454, 672972561
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,2


LINKS

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


FORMULA

G.f.: (x+1)*(x^2+1)/((x1)*(x^5+2*x^4+2*x^3+x^21)).  R. J. Mathar, Nov 28 2011
a(n) = 1.6443631... * 1.7346913...^n + O(1), where 1.7346913... is the real root of x^5  x^3  2x^2  2x  1. [Charles R Greathouse IV, Jan 18 2012]


MATHEMATICA

LinearRecurrence[{1, 1, 1, 0, 1, 1}, {14, 25, 44, 77, 134, 233}, 50] (* G. C. Greubel, Sep 18 2017 *)


PROG

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


CROSSREFS

Sequence in context: A210145 A020956 A164393 * A164153 A212588 A164392
Adjacent sequences: A164388 A164389 A164390 * A164392 A164393 A164394


KEYWORD

nonn,easy


AUTHOR

R. H. Hardin, Aug 14 2009


EXTENSIONS

Conjectured g.f. verified by Charles R Greathouse IV, Jan 18 2012
Edited by Alois P. Heinz, Oct 12 2017


STATUS

approved



