|
|
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
|
|
|
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
|
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|