A386250 Total number of ones in runs of 1's of length >= 4 over all binary strings of length n.

0, 0, 0, 0, 4, 13, 36, 92, 224, 528, 1216, 2752, 6144, 13568, 29696, 64512, 139264, 299008, 638976, 1359872, 2883584, 6094848, 12845056, 27000832, 56623104, 118489088, 247463936, 515899392, 1073741824, 2231369728, 4630511616, 9596567552, 19864223744, 41070624768, 84825604096, 175019917312

Offset

0,5

Links

Michael De Vlieger, Table of n, a(n) for n = 0..3312

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. 111, Sect. 8.1.

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

Formula

For n>=4, a(n) = (5*n-12)*2^(n-5).

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

For n>=6, a(n) = 4*a(n-1) - 4*a(n-2). - Wesley Ivan Hurt, Feb 20 2026 (range added by Falk Hüffner, May 21 2026)

Example

For n=6 there are eight binary strings that contain runs of 1s of length >= 4: 001111, 011110, 011111, 101111, 111100, 111101, 111110 and 111111; the runs of length >= 4 in these strings contain a(6) = 36 ones.

Mathematica

LinearRecurrence [{4, -4}, {0, 0, 0, 0, 4, 13}, 36] (* Hugo Pfoertner, Aug 14 2025, corrected by Michael De Vlieger, Feb 16 2026 *)

Crossrefs

Cf. A001787, A066373, A128135, A053220.

Sequence in context: A053563 A221882 A235996 * A036636 A036643 A000299

Adjacent sequences: A386247 A386248 A386249 * A386251 A386252 A386253

Keyword

nonn,easy

Author

Félix Balado, Aug 14 2025

Status

approved