A Generating Function for the Distribution of Runs in Binary Words

Abstract: Let

N (n, r, k)

denote the number of binary words of length

n

that begin with

0

and contain exactly

k

runs (i.e., maximal subwords of identical consecutive symbols) of length

r

. We show that the generating function for the sequence

N (n, r, 0)

,

n = 0, 1, l d o t s

, is

(1 - x) (1 - 2 x + x^{r} - x^{r + 1})^{- 1}

and that the generating function for

N (n, r, k)

is

x^{k r}

time the

k + 1

power of this. We extend to counts of words containing exactly

k

runs of

1

s by using symmetries on the set of binary words.

This page was built for publication: A Generating Function for the Distribution of Runs in Binary Words