Voozh

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

(list; graph; refs; listen; history; text; internal format)

OFFSET

0,2

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

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

EXAMPLE

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

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