Splitting $\{1,...,n\}$ into $m$ intervals using $k$ points What is the number of ways to chose a set $A  =\{a_1 , \ldots ,a_k \}$ from  $ N = \{1, \ldots, n\}$, s.t. $N-A$ consists of exactly $m$ maximal intervals, where an interval is defined as a subset of N consisting of consecutive numbers.
For example choosing $\{3,4,7\}$ from $\{1,2,3,4,5,6,7,8\}$ would result in the $3$ maximal intervals, $\{1,2\}$, $\{5,6\}$ and $\{8\}$
 A: Let's extend $N$ to $N_2 = \{0,1,2,3,\ldots,n,n+1\}$ with $n+2$ elements.  We chose $k+2$ elements of this for $A_2$, always including $0$ and $n+1$, so $N_2-A_2$ has $m$ non-empty runs and so $A_2$ has $m+1$ non-empty runs.  
In effect we have decomposed $N_2$ into $2m+1$ parts of non-empty runs.  The way of calculating this is well known and gives $${n+1 \choose 2m}$$ as a result for your question.  
If $k$ is fixed then it becomes very slightly more complicated: you have to decompose the $k+2$ elements of $A_2$ into $m+1$ non-empty parts and the $n-k$ elements of $N_2-A_2$ into $m$ parts, so the answer is $${k+1 \choose m}{n-k-1 \choose m-1}.$$
A: Suppose $A$ has size $k$. For example, suppose $n=10$, $m=5$ and $k=4$. Then, a choice of $A$ is the same as diving up $\{1,2,\ldots,10\}$ into runs of 0s and 1s, with $k=4$ ones and no two ones adjacent. So, for instance, 0010101010. 
The the $m$ intervals will contain a total of $n-k$ elements (the $0$s). The ways of choosing the lengths of the runs of $0$s correspond to compositions of $n-k$ into $m$ parts. There are $\binom{n-k-1}{m-1}$ ways to do that.  
Similarly, there are $k$ $1$s, divided into $m-1$ runs, which is compositions of $k$ into $m-1$ parts, so $\binom{k-1}{m-2}$. 
Once you have a composition for the $0$s and a composition for the $1$s, the set $A$ is totally determined (interleave the runs of $0$s and $1s$). So, summing over $k$ gives
$$\sum_{k=0}^n \binom{n-k-1}{m-1}\binom{k-1}{m-2}$$
