A384155 a(n) is the number of binary strings of length n whose shortest run of 1s is of length 3.

0, 0, 0, 1, 2, 3, 4, 6, 11, 21, 38, 65, 108, 179, 299, 502, 842, 1406, 2337, 3872, 6403, 10575, 17445, 28742, 47293, 77720, 127578, 209210, 342768, 561131, 917910, 1500476, 2451158, 4001723, 6529439, 10648199, 17356589, 28278426

Offset: 0

Author

Félix Balado, May 31 2025

Keywords

• nonn
• easy

Links

• Index entries for linear recurrences with constant coefficients, signature (4,-6,4,0,-1,-1,1,0,-1).

Crossrefs

Cf. A384153, A384154.

Programs

Mathematica

LinearRecurrence[{4, -6, 4, 0, -1, -1, 1, 0, -1}, {0, 0, 0, 1, 2, 3, 4, 6, 11}, 50] (* Amiram Eldar, May 31 2025 *)

Formula

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