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

Author

Félix Balado, Aug 06 2025

Keywords

• nonn
• easy

Examples

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

Links

• Paolo Xausa, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, signature (4,-4).

Crossrefs

Cf. A045623, A106472, A001792.

Programs

Mathematica

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

Python

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

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