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

0, 1, 2, 4, 9, 20, 43, 91, 191, 398, 824, 1697, 3480, 7111, 14487, 29439, 59694, 120820, 244153, 492716, 993171, 1999923, 4023679, 8089182, 16251760, 32632321, 65490672, 131377999, 263452079, 528125695, 1058395038, 2120551916, 4247705401, 8506995748, 17034321659

Offset

0,3

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 pp. 15, 24, 33.

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

Formula

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

Crossrefs

Column 1 of A388718.

Cf. A000071, A384154.

Sequence in context: A175104 A179744 A123720 * A266930 A034007 A109975

Adjacent sequences: A384150 A384151 A384152 * A384154 A384155 A384156

Keyword

nonn,easy

Author

Félix Balado, May 20 2025

Status

approved