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

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

Crossrefs

Cf. A118869, A118870.

Sequence in context: A118870 A171857 A190160 * A088532 A271364 A036621

Adjacent sequences: A332049 A332050 A332051 * A332053 A332054 A332055

Keyword

nonn,easy

Author

Alois P. Heinz, Feb 06 2020

Status

approved