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