2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.