A387332 Number of binary strings of length n that contain at least one maximal run of ones of even length.

0, 0, 1, 2, 6, 13, 31, 67, 148, 315, 672, 1410, 2951, 6123, 12663, 26054, 53449, 109278, 222890, 453533, 921107, 1867427, 3780396, 7642719, 15433236, 31132582, 62744943, 126354087, 254265823, 511337918, 1027733205, 2064578674, 4145578078, 8320744045, 16694805175

Offset: 0

Author

Félix Balado, Aug 26 2025

Keywords

• nonn
• easy
• new

Examples

			a(5) = 13 because there are 13 binary strings of length 5 that contain at least one run of ones of even length: 00011, 00110, 01011, 01100, 01101, 01111, 10011, 10110, 11000, 11001, 11010, 11011, and 11110.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (3,0,-5,2).

Crossrefs

Cf. A000079, A027934 (same for odd length).

Programs

Mathematica

LinearRecurrence[{3,0,-5,2},{0,0,1,2},35] (* or *) CoefficientList[Series[-x^2 * (1-x) / ((x^3 - 2*x^2 - x + 1) * (2*x - 1)),{x,0,34}],x] (* James C. McMahon, Sep 05 2025 *)

Formula

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

a(n) ~ 2^n. - Stefano Spezia, Aug 28 2025