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

0, 0, 1, 2, 3, 5, 10, 20, 38, 70, 128, 234, 427, 776, 1404, 2531, 4550, 8161, 14608, 26099, 46550, 82901, 147441, 261913, 464759, 823902, 1459287, 2582615, 4567357, 8072082, 14257631, 25169443, 44410452, 78325112, 138082349, 243339192, 428683436, 754961473

Offset

0,4

Links

Andrew Howroyd, Table of n, a(n) for n = 0..1000

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

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

Formula

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

Mathematica

LinearRecurrence[{4, -6, 5, -2, -1, 1, -1}, {0, 0, 1, 2, 3, 5, 10}, 40] (* Harvey P. Dale, Jun 24 2025 *)

Crossrefs

Column 2 of A388718.

Cf. A000100, A384153.

Sequence in context: A093785 A105369 A047101 * A251703 A057755 A388263

Adjacent sequences: A384151 A384152 A384153 * A384155 A384156 A384157

Keyword

nonn,easy

Author

Félix Balado, May 20 2025

Status

approved