login
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
OFFSET
0,2
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..2000 (first 500 terms from R. H. Hardin)
FORMULA
G.f.: (x+1)*(x^2+1)/((x-1)*(x^5+2*x^4+2*x^3+x^2-1)). - 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*(-14-11*x-5*x^2+6*x^3+12*x^4+8*x^5)/((1-x)*(x^5+2*x^4+2*x^3+ x^2-1))) \\ G. C. Greubel, Sep 18 2017
CROSSREFS
Sequence in context: A210145 A020956 A164393 * A164153 A212588 A164392
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