OFFSET
0,2
COMMENTS
Each of the subwords 10001, 10011, 10111, 11001, 11101 and their binary complements give the same sequence.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (2,0,0,-1,1).
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
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Mar 16 2012
STATUS
approved