login
A210003
Number of binary words of length n containing no subword 10001.
2
1, 2, 4, 8, 16, 31, 60, 116, 224, 433, 837, 1618, 3128, 6047, 11690, 22599, 43688, 84457, 163271, 315633, 610177, 1179585, 2280356, 4408350, 8522156, 16474904, 31849037, 61570080, 119026354, 230099960, 444825787, 859930531, 1662404788, 3213735970, 6212746113
OFFSET
0,2
COMMENTS
Each of the subwords 10001, 10011, 10111, 11001, 11101 and their binary complements give the same sequence.
FORMULA
G.f.: -(x^4+1)/(x^5-x^4+2*x-1).
a(n) = 2^n if n<5, and a(n) = 2*a(n-1) -a(n-4) +a(n-5) otherwise.
EXAMPLE
a(7) = 116 because among the 2^7 = 128 binary words of length 7 only 12, namely 0010001, 0100010, 0100011, 0110001, 1000100, 1000101, 1000110, 1000111, 1010001, 1100010, 1100011 and 1110001 contain the subword 10001.
MAPLE
a:= n-> (<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>, <0|0|0|0|1>, <1|-1|0|0|2>>^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);
MATHEMATICA
LinearRecurrence[{2, 0, 0, -1, 1}, {1, 2, 4, 8, 16}, 40] (* Harvey P. Dale, Oct 05 2015 *)
CROSSREFS
Columns k=17, 19, 23, 25, 29 of A209972.
Sequence in context: A118891 A107066 A141019 * A209888 A210021 A226188
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Mar 16 2012
STATUS
approved