TAOCP 5.1.3 Exercise 17
We are asked to count the binary sequences \(a_1 a_2 \ldots a_n\) (each \(a_j \in \{0,1\}\)) that contain exactly \(k\) runs, where a run is defined by the condition that there are exactly \(k-1\) ind...
Exercise 17. [M25] Among all $2^n$ sequences $a_1, a_2 \ldots a_n$, where each $a_j$ is either 0 or 1, how many have exactly $k$ runs (that is, $k-1$ occurrences of $a_j > a_{j+1}$)?
Verified: yes
Solve time: 17m
Solution
We are asked to count the binary sequences (a_1 a_2 \ldots a_n) (each (a_j \in {0,1})) that contain exactly (k) runs, where a run is defined by the condition that there are exactly (k-1) indices (j) with (a_j > a_{j+1}). Because the alphabet is ({0,1}), the inequality (a_j > a_{j+1}) occurs precisely when (a_j = 1) and (a_{j+1} = 0). Thus we must count the binary strings of length (n) that contain exactly (k-1) occurrences of the pattern “10”.
Let (d = k-1) be the number of descents (occurrences of “10”). Every such string can be uniquely decomposed by cutting at each of these (d) descents. Write the string as [ B_0,; 10,; B_1,; 10,; \ldots,; 10,; B_d ] where each (B_i) is a (possibly empty) binary string that itself contains no occurrence of “10”. A binary string without “10” can only consist of some 0’s followed by some 1’s, i.e. it has the form (0^{a_i}1^{b_i}) with (a_i, b_i \ge 0). There are (d+1) such blocks.
The total length of the string is [ \sum_{i=0}^{d} (a_i + b_i) + 2d = n, ] so [ \sum_{i=0}^{d} (a_i + b_i) = n - 2d. ] The number of non‑negative integer solutions ((a_0,b_0,\ldots,a_d,b_d)) to this equation is the number of ways to distribute (n-2d) indistinguishable objects into (2(d+1)) boxes: [ \binom{(n-2d) + 2(d+1) - 1}{2(d+1)-1} = \binom{n+1}{2d+1}. ] Substituting (d = k-1) gives (\binom{n+1}{2k-1}).
This formula is valid when (n-2d \ge 0), i.e. (2k-2 \le n) or (k \le \lfloor (n+2)/2 \rfloor). For larger (k) the binomial coefficient is zero, which correctly reflects the impossibility of having more runs.
Hence the number of binary sequences of length (n) with exactly (k) runs is [ \boxed{\binom{n+1}{2k-1}}. ]
Notes
The sum of these numbers over all feasible (k) is (\sum_{k} \binom{n+1}{2k-1} = 2^n), the total number of binary sequences of length (n), as expected. The result is a well‑known binomial identity; it can also be obtained via a bijection with subsets of ({1,\dots,n+1}) of odd cardinality.