Counting Runs of Ones and Ones in Runs of Ones in Binary Strings Counting runs in binary strings

Abstract—Consider a binary string (a symmetric Bernoulli sequence) of length �. For a positive integer �, 1 ≤ � ≤ �, we exactly enumerate, in all 2 � possible binary strings of length �, the number of all runs of 1s of length (equal, at least) � and the number of 1s in all runs of 1s of length at least �. To solve these counting problems, we use probability theory and we obtain simple and easy to compute explicit formulae as well as recursive schemes, for these potential useful in engineering numbers. Keywords-runs; symmetric Bernoulli trials; probability theory; combinatorial problem