This is an exercise from Douglas West's course on combinatorics. Given a set $S \subseteq [n] = \{1, 2, \ldots, n\}$, a run in $S$ is a maximal subset of $S$ that contains only consecutive integers. For example, if $n = 9$ and $S = \{1,2,3,5,6,9\}$ then $S$ contains 3 runs, namely $\{1,2,3\}, \{5,6\}, \{9\}$. Given $n$, how many subsets of $[n]$ have exactly $k$ runs?
This is easy if $k = 1$. If $S$ is a singleton, then there are $n$ choices. Otherwise, $S$ is a consecutive set of integers which is completely determined by two numbers, so there are $\binom{n}{2}$ choices when $S$ is not a singleton. Hence, for $k = 1$, we have $\binom{n+1}{2}$ subsets of $[n]$ that contain exactly one run.
For $k = 2$, my attempt is as follows. Choose a number between $2$ and $n-1$, say $m$. Then the number of ways to choose a subset with a single run on $[m-1]$ is $\binom{m}{2}$ and the number of ways to choose a subset with a single run on $[n] \setminus [m]$ is $\binom{n-m+1}{2}$. Hence, the total number of subsets of $[n]$ with exactly two runs is $\sum_{m=2}^{n-1} \binom{m}{2}\binom{n-m+1}{2}$. First question (but this is related to the question below), is there a nicer answer?
For general $k$, we can choose $k-1$ integers from $[n]$ such that all $k-1$ integers are pair non-consecutive and then apply the reasoning to each "block" of $[n]$. But this gives an ugly summation formula.
Is there an easier/better method to proceed that will produce a "nicer" answer for general $k$?