A386878 Number of runs of 1's of length <= 3 over all binary strings of length n.

0, 1, 3, 8, 19, 45, 104, 236, 528, 1168, 2560, 5568, 12032, 25856, 55296, 117760, 249856, 528384, 1114112, 2342912, 4915200, 10289152, 21495808, 44826624, 93323264, 193986560, 402653184, 834666496, 1728053248, 3573547008, 7381975040, 15233712128, 31406948352

Offset

0,3

Links

Paolo Xausa, 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. 100, Sect. 8.1.

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

Formula

For n>=4, a(n) = (3+7*(n+1))*2^(n-5); for n<4, a(n) = (n+1)*2^(n-2).

G.f.: x*(x^2+x+1)*(x-1)^2/(2*x-1)^2. - Alois P. Heinz, Aug 14 2025

Example

For n=3, the breakdown of the 8 runs of 1s is as follows: 001 (1), 010 (1), 011 (1), 100 (1), 101 (2), 110 (1) and 111 (1).
For n=4, the breakdown of the 19 runs of 1s is as follows: 0001 (1), 0010 (1), 0011 (1), 0100 (1), 0101 (2), 0110 (1), 0111 (1), 1000 (1), 1001 (2), 1010 (2), 1011 (2), 1100 (1), 1101 (2) and 1110 (1).

Mathematica

LinearRecurrence[{4, -4}, {0, 1, 3, 8, 19, 45}, 40] (* Paolo Xausa, Aug 19 2025 *)

Prog

(Python)
def A386878(n): return (0, 1, 3, 8, 19)[n] if n<5 else 3+7*(n+1)<<n-5 # Chai Wah Wu, Aug 19 2025

Crossrefs

Cf. A045623, A106472, A001792.

Sequence in context: A079490 A361506 A026789 * A308372 A096576 A309537

Adjacent sequences: A386875 A386876 A386877 * A386879 A386880 A386881

Keyword

nonn,easy

Author

Félix Balado, Aug 06 2025

Status

approved