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

Links

Michael De Vlieger, Table of n, a(n) for n = 0..3321

Félix Balado and Guénolé C. M. Silvestre, Systematic Enumeration of Fundamental Quantities Involving Runs in Binary Strings, arXiv:2602.10005 [math.CO], 2026. See p. 38, Sect. 2.8.

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

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

Example

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.

Mathematica

LinearRecurrence[{3, 0, -5, 2}, {0, 0, 1, 2}, 35] (* James C. McMahon, Sep 05 2025 *)
(* Alternative: *)
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 *)

Crossrefs

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

Sequence in context: A094687 A369584 A336875 * A219753 A239305 A018013

Adjacent sequences: A387329 A387330 A387331 * A387333 A387334 A387335

Keyword

nonn,easy,changed

Author

Félix Balado, Aug 26 2025

Status

approved