A332052 - OEIS

%I #15 Mar 07 2024 12:25:20

%S 1,2,4,8,15,28,54,104,198,380,736,1424,2756,5360,10456,20416,39944,

%T 78352,153952,302912,596976,1178304,2328544,4606848,9124448,18089920,

%U 35895552,71283968,141664832,281718528,560561024,1115994112,2222846080,4429381888,8829667840

%N Number of binary words of length n with an even number of occurrences of the subword 0101.

%H Alois P. Heinz, <a href="/A332052/b332052.txt">Table of n, a(n) for n = 0..3322</a>

%H <a href="/index/Rec#order_05">Index entries for linear recurrences with constant coefficients</a>, signature (4,-6,8,-10,4).

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

%F a(n) = Sum_{k>=0} A118869(n,2*k).

%e a(4) = 15 = 2^4 - 1: 0101 is not counted.

%e a(5) = 28 = 2^5 - 4: 00101, 10101, 01010, 01011 are not counted.

%p a:= n-> 2^n-(<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>

%p             , <0|0|0|0|1>, <4|-10|8|-6|4>>^n)[1, 5]:

%p seq(a(n), n=0..39);

%t LinearRecurrence[{4,-6,8,-10,4},{1,2,4,8,15},50] (* _Harvey P. Dale_, Mar 07 2024 *)

%Y Cf. A118869, A118870.

%K nonn,easy

%O 0,2

%A _Alois P. Heinz_, Feb 06 2020