A210021 Number of binary words of length n containing no subword 11011.
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
Examples
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.
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).
Programs
-
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
-
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 *)
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.