|
%I #24 Aug 12 2022 20:17:13
%S 1,2,4,8,16,31,60,116,225,437,849,1649,3202,6217,12071,23438,45510,
%T 88368,171586,333171,646922,1256136,2439055,4735945,9195847,17855697,
%U 34670640,67320433,130716961,253814826,492835556,956945224,1858113016,3607922263,7005549684
%N Number of binary words of length n containing no subword 11011.
%H Alois P. Heinz, <a href="/A210021/b210021.txt">Table of n, a(n) for n = 0..1000</a>
%H Aashir Shukla et al., <a href="http://math.stackexchange.com/questions/1920508/how-many-binary-strings-of-length-n-contain-within-it-the-substring-11011">How many Binary Strings of length N contain within it the substring '11011'?</a>, Mathematics Stack Exchange, circa Sep 09 2016.
%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,-1,1,1).
%F G.f.: -(x^4+x^3+1)/(x^5+x^4-x^3+2*x-1).
%F a(n) = 2^n if n<5, and a(n) = 2*a(n-1) -a(n-3) +a(n-4) +a(n-5) otherwise.
%e 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.
%p 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);
%t LinearRecurrence[{2, 0, -1, 1, 1}, {1, 2, 4, 8, 16}, 40] (* _Vincenzo Librandi_, Oct 24 2016 *)
%o (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
%Y Column k=27 of A209972. Cf. A276785.
%Y Column k=0 of A277678.
%K nonn,easy
%O 0,2
%A _Alois P. Heinz_, Mar 16 2012
|
