A391450 Number of binary strings of length n where the number of runs equals the number of 1s.

1, 1, 0, 2, 4, 5, 12, 25, 42, 83, 168, 312, 600, 1187, 2284, 4410, 8644, 16835, 32736, 64062, 125340, 244983, 480020, 941485, 1846338, 3624661, 7122312, 13999280, 27532664, 54185637, 106684708, 210141817, 414133250, 816477435, 1610317200, 3177234510, 6271083324, 12381650255, 24454325508, 48313318291

Offset

0,4

Comments

A run is a maximal block of consecutive identical digits.

The empty string (n=0) has 0 runs and 0 ones; since 0 = 0, a(0) = 1.

The formula follows from the identity (see Sinha & Sinha): the number of length-n binary strings with R runs of 1s and C total 1s is binomial(C-1,R-1)*binomial(n-C+1,R). Given R runs of 1s, the total number of runs is 2R-1, 2R, or 2R+1 depending on whether the string has 1s at both endpoints, exactly one endpoint, or neither. Setting total runs equal to C and summing over valid values of R yields the formula.

Links

Alois P. Heinz, Table of n, a(n) for n = 0..3328

K. Sinha and B. P. Sinha, On the distribution of runs of ones in binary strings, Computers & Mathematics with Applications, 58(9), 2009, 1816-1829.

Formula

a(0) = a(1) = 1; For n >= 2: a(n) = Sum_{m=1..floor(n/3)} 2*binomial(2*m-1, m-1)*binomial(n-2*m-1, m-1) + Sum_{m=1..floor((n-1)/3)} binomial(2*m, m)*binomial(n-2*m-2, m-1) + Sum_{m=1..floor((n-2)/3)} binomial(2*m, m-1)*binomial(n-2*m-2, m).

a(n) = A345908(n) + A370048(n-1). - Alois P. Heinz, Dec 10 2025

Example

a(4) = 4: valid strings are 0011 (2 runs, 2 ones), 1011 (3 runs, 3 ones), 1100 (2 runs, 2 ones), 1101 (3 runs, 3 ones).

Maple

b:= proc(n, c, t) option remember; `if`(abs(c)>n, 0,
     `if`(n=0, 1, add(b(n-j, c+t*j-1, 1-t), j=1..n)))
    end:
a:= n-> add(b(n, 0, i), i=0..signum(n)):
seq(a(n), n=0..39);  # Alois P. Heinz, Dec 10 2025
# Alternative:
a:= proc(n) option remember; `if`(n<5, [1$2, 0, 2, 4][n+1],
      (4*(5-n)*(5*n-2)*a(n-5) +2*(8*n^2-39*n+10)*a(n-4) -(n+4)*(n-8)*a(n-3)
       +(9*n^2-35*n+16)*a(n-2) -(3*n-4)*(n-2)*a(n-1))/((n+1)*(n-4)))
    end:
seq(a(n), n=0..39);  # Alois P. Heinz, Dec 10 2025

Prog

(Python)
import math
def a(n):
    if n <= 1: return 1
    term1 = sum(2 * math.comb(2*m-1, m-1) * math.comb(n-2*m-1, m-1) for m in range(1, n//3 + 1))
    term2 = sum(math.comb(2*m, m) * math.comb(n-2*m-2, m-1) for m in range(1, (n-1)//3 + 1))
    term3 = sum(math.comb(2*m, m-1) * math.comb(n-2*m-2, m) for m in range(1, (n-2)//3 + 1))
    return term1 + term2 + term3
result_list = [a(n) for n in range(100)]
print(result_list)

Crossrefs

Cf. A000120, A005811, A345908, A370048, A357183.

Sequence in context: A091071 A353850 A050599 * A281643 A102932 A128457

Adjacent sequences: A391447 A391448 A391449 * A391451 A391452 A391453

Keyword

nonn

Author

Austen M. Fletcher, Dec 09 2025

Status

approved