OFFSET
0,2
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
Aashir Shukla et al., How many Binary Strings of length N contain within it the substring '11011'?, Mathematics Stack Exchange, circa Sep 09 2016.
Index entries for linear recurrences with constant coefficients, signature (2,0,-1,1,1).
FORMULA
G.f.: -(x^4+x^3+1)/(x^5+x^4-x^3+2*x-1).
a(n) = 2^n if n<5, and a(n) = 2*a(n-1) -a(n-3) +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 0011011, 0110110, 0110111, 0111011, 1011011, 1101100, 1101101, 1101110, 1101111, 1110110, 1110111 and 1111011 contain the subword 11011.
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|-1|0|2>>^n. <<1, 2, 4, 8, 16>>)[1, 1]: seq(a(n), n=0..40);
MATHEMATICA
LinearRecurrence[{2, 0, -1, 1, 1}, {1, 2, 4, 8, 16}, 40] (* Vincenzo Librandi, Oct 24 2016 *)
PROG
(Magma) I:=[1, 2, 4, 8, 16]; [n le 5 select I[n] else 2*Self(n-1)-Self(n-3)+Self(n-4)+Self(n-5): n in [1..40]]; // Vincenzo Librandi, Oct 24 2016
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Mar 16 2012
STATUS
approved