<s>[INST] Numbers of ways to choose $k$ out of the first $n$ natural numbers so the longest string of consecutive numbers is exactly $m$? How many ways can $k$ numbers be chosen from the first $n$ natural numbers so that the longest string of consecutive numbers is exactly $m$ numbers long
For example, if choosing $k = 7$ distinct numbers from the first $n = 14$ natural numbers ($1-14$), how many combinations of numbers are there that have exactly $m = 3$ consecutive numbers?
Some sets that satisfy this would be $[1,2,3,5,7,10,13]$, $[1,2,3,7,8,10,11]$, or $[1,2,3,6,9,10,11]$.
Obviously $m \le k \le n$, and the order of the numbers picked does not matter, but there is no repetition, so $[1,2,3]$ is the same as $[2,1,3]$, but $[1,1,3]$ is not allowed.
For cases when $m \gt \frac k2$ I believe the equation 
$$2* \binom {n-m-1}{k-m} + (n-m-1)*\binom{n-m-2}{k-m}$$
will produce the correct answer, but for values of $m \le \frac k2$ I do not know how to account for multiple strings of consecutive digits in the same set (eg. $[\textbf{1,2,3},6,\textbf{8,9,10}]$) not being counted twice.

If anyone could give me help with this example that I could extrapolate from or (ideally) a formula or any references to solve for a general case it would be much appreciated.
 [/INST] Another more practical solution uses a recurrence relation. Let the size of the gaps between the $n-k$ numbers not chosen be $x_1,x_2,...,x_{n-k+1}$. Then the problem reduces to how many ways are there such that $\forall i$, $x_i\in [0,1...m]$, $\sum_{i=1}^{n-k+1}x_i = k$ and at least one of $x_i = m$. 
To solve this first consider the solutions of another similar problem, $\forall i$, $x_i\in [0,1...m]$, $\sum_{i=1}^{y}x_i = k$ where the constraint at least one of $x_i = m$ doesn't exist and $n-k+1$ has been replaced by $y$. Let the number of solutions of this problem be the function $S(y,k,m)$. Next consider removing the last $x_i$ in a solution of $y,k,m$. Then the remaining $x_i$ will give us a solution of $y-1,k-a,m$ for some $a\in [0,1...m]$. Therefore $S(y,k,m) = \sum_{a=0}^{m}S(y-1,k-a,m)$. $S(1,k,m) = 1$ iff $k\in [0,1...m]$ which allows us to tabulate all other values.
For example in the $m=2$ case:
$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|} 
\hline \text{y\k} & \text{0} & \text{1} & \text{2} & \text{3} & \text{4} & \text{5} & \text{6} & \text{7} & \text{8} & \text{9} & \text{10} \\ 
\hline \text{1} & \text{1} & \text{1} & \text{1} & \text{0} & \text{0} & \text{0} & \text{0} & \text{0} & \text{0} & \text{0} & \text{0} \\
\hline \text{2} & \text{1} & \text{2} & \text{3} & \text{2} & \text{1} & \text{0} & \text{0} & \text{0} & \text{0} & \text{0} & \text{0} \\
\hline \text{3} & \text{1} & \text{3} & \text{6} & \text{7} & \text{6} & \text{3} & \text{1} & \text{0} & \text{0} & \text{0} & \text{0} \\
\hline \text{4} & \text{1} & \text{4} & \text{10} & \text{16} & \text{19} & \text{16} & \text{10} & \text{4} & \text{1} & \text{0} & \text{0} \\
\hline \text{5} & \text{1} & \text{5} & \text{15} & \text{30} & \text{45} & \text{51} & \text{45} & \text{30} & \text{15} & \text{5} & \text{1} \\
\hline \end{array}$$
Then let $P(y,k,m)$ be the number of solutions of the problem with the constraint at least one of $x_i = m$ included. $P(y,k,m) = S(y,k,m) - S(y,k,m-1)$.
For example $P(3,3,2) = S(3,3,2) - S(3,3,1) = 7-1 = 6$ (with $S(3,3,1)$ quickly worked out by hand).
Therefore the number of solutions of the original problem with $n=5, k=3, m=2$ is $P(5-3+1,3,2) = P(3,3,1) = 6$ and as the possible solutions of this problem are $[1,2,4], [1,2,5], [2,3,5], [1,3,4], [1,3,5], [2,3,5]$ this is indeed correct.
Although this is a bit time consuming by hand it should be possible to get a computer to use the recurrence relation to generate the solutions.
</s>