Number of subsets of $[n]$ with $k$ runs

Question

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$?

Answer 1

Between $k$ runs, there must be $k-1$ "non-runs". Before the first and after the last run, there may be one extra non-run each. Thus, adding runs and non-runs, we have between $2k-1$ and $2k+1$ groups, where in the case of $2k$ groups there is a factor of $2$ because we can start with a run or a non-run. The number of divisions of $[n]$ into $j$ groups of consecutive numbers each containing at least one number is $\binom{n-1}{j-1}$, so the total number we're looking for is

$$ \binom{n-1}{2k-2}+2\binom{n-1}{2k-1}+\binom{n-1}{2k}\;. $$

Then two applications of the recurrence for Pascal's triangle yield

$$ \binom{n+1}{2k}\;. $$

Come to think of it, that was unnecessarily complicated – we can just distribute $2k$ partition lines spaced at least $1$ apart and allow them to lie at $0$ or $n$; that yields the same result more directly.