login
A210021
Number of binary words of length n containing no subword 11011.
4
1, 2, 4, 8, 16, 31, 60, 116, 225, 437, 849, 1649, 3202, 6217, 12071, 23438, 45510, 88368, 171586, 333171, 646922, 1256136, 2439055, 4735945, 9195847, 17855697, 34670640, 67320433, 130716961, 253814826, 492835556, 956945224, 1858113016, 3607922263, 7005549684
OFFSET
0,2
LINKS
Aashir Shukla et al., How many Binary Strings of length N contain within it the substring '11011'?, Mathematics Stack Exchange, circa Sep 09 2016.
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
Column k=27 of A209972. Cf. A276785.
Column k=0 of A277678.
Sequence in context: A141019 A210003 A209888 * A226188 A239556 A152718
KEYWORD
nonn,easy
AUTHOR
Alois P. Heinz, Mar 16 2012
STATUS
approved