login
Number of binary words of length n containing no subword 100001.
2

%I #15 Feb 09 2017 08:26:25

%S 1,2,4,8,16,32,63,124,244,480,944,1857,3653,7186,14136,27808,54703,

%T 107610,211687,416424,819176,1611457,3170007,6235937,12267137,

%U 24131522,47470763,93382976,183700022,361368844,710873303,1398407365,2750902517,5411487988

%N Number of binary words of length n containing no subword 100001.

%C Each of the subwords 100001, 100011, 100101, 100111, 101001, 101011, 101111, 110001, 110101, 111001, 111101 and their binary complements give the same sequence.

%H Indranil Ghosh, <a href="/A210031/b210031.txt">Table of n, a(n) for n = 0..3396</a> (terms 0..1000 from Alois P. Heinz)

%H <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,0,0,-1,1).

%F G.f.: -(x^5+1)/(x^6-x^5+2*x-1).

%F a(n) = 2^n if n<6, and a(n) = 2*a(n-1) -a(n-5) +a(n-6) otherwise.

%e a(8) = 244 because among the 2^8 = 256 binary words of length 8 only 12, namely 00100001, 01000010, 01000011, 01100001, 10000100, 10000101, 10000110, 10000111, 10100001, 11000010, 11000011, 11100001 contain the subword 100001.

%p a:= n-> (Matrix(6, (i, j)-> `if`(i=j-1, 1, `if`(i=6, [1, -1, 0, 0, 0, 2][j], 0)))^n. <<1, 2, 4, 8, 16, 32>>)[1, 1]: seq(a(n), n=0..40);

%Y Columns k=33, 35, 37, 39, 41, 43, 47, 49, 53, 57, 61 of A209972.

%K nonn,easy

%O 0,2

%A _Alois P. Heinz_, Mar 16 2012