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

1, 2, 4, 8, 15, 28, 54, 104, 198, 380, 736, 1424, 2756, 5360, 10456, 20416, 39944, 78352, 153952, 302912, 596976, 1178304, 2328544, 4606848, 9124448, 18089920, 35895552, 71283968, 141664832, 281718528, 560561024, 1115994112, 2222846080, 4429381888, 8829667840

Offset: 0

Author

Alois P. Heinz, Feb 06 2020

Keywords

• nonn
• easy

Examples

			a(4) = 15 = 2^4 - 1: 0101 is not counted.
a(5) = 28 = 2^5 - 4: 00101, 10101, 01010, 01011 are not counted.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..3322
• Index entries for linear recurrences with constant coefficients, signature (4,-6,8,-10,4).

Crossrefs

Cf. A118869, A118870.

Programs

Maple

a:= n-> 2^n-(<<0|1|0|0|0>, <0|0|1|0|0>, <0|0|0|1|0>
            , <0|0|0|0|1>, <4|-10|8|-6|4>>^n)[1, 5]:
seq(a(n), n=0..39);

Mathematica

LinearRecurrence[{4,-6,8,-10,4},{1,2,4,8,15},50] (* Harvey P. Dale, Mar 07 2024 *)

Formula

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)).

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