|
%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
|
