login
A209888
Number of binary words of length n containing no subword 01101.
5
1, 2, 4, 8, 16, 31, 60, 116, 225, 436, 845, 1637, 3172, 6146, 11909, 23075, 44711, 86633, 167863, 325256, 630226, 1221144, 2366125, 4584673, 8883398, 17212733, 33351899, 64623621, 125216632, 242623433, 470114310, 910907331, 1765000872, 3419917668, 6626533192
OFFSET
0,2
COMMENTS
Notice that the proper suffix 01 of 01101 is also a prefix of 01101. If instead of 01101 subword 01011 is not allowed, we get A107066 with A107066(n) < a(n) for all n >= 8. Word 01101101 of length 8 is the smallest binary word having two or more copies of 01101.
FORMULA
G.f.: (x+1)*(x^2-x+1) / (x^5-2*x^4+x^3-2*x+1).
a(n) = 2^n if n<5, and a(n) = 2*(a(n-1)+a(n-4)) -a(n-3) -a(n-5) otherwise.
EXAMPLE
a(6) = 60 because among the 2^6 = 64 binary words of length 6 only 4, namely 001101, 011010, 011011 and 101101 contain the subword 01101.
MAPLE
a:= n-> (Matrix(5, (i, j)-> `if`(i=j-1, 1, `if`(i=5, [-1, 2, -1, 0, 2][j], 0)))^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);
MATHEMATICA
CoefficientList[Series[(x + 1)*(x^2 - x + 1)/(x^5 - 2*x^4 + x^3 - 2*x + 1), {x, 0, 40}], x] (* Wesley Ivan Hurt, Apr 28 2017 *)
LinearRecurrence[{2, 0, -1, 2, -1}, {1, 2, 4, 8, 16}, 40] (* Harvey P. Dale, Sep 17 2017 *)
CROSSREFS
Column 22 of A209972.
Column k=0 of A277751.
Sequence in context: A107066 A141019 A210003 * A210021 A226188 A239556
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 14 2012
STATUS
approved