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.
 A: Let $l=n-k$, and line up $l$ sticks (representing the numbers not chosen).
If we let $x_i$ represent the number of integers in gap $i$, the number of choices with no string longer than $m$ is given by the number of solutions of $x_1+\cdots+x_{l+1}=k\;$ with $0\le x_i\le m$ for each $i$, 
so there are $\displaystyle s_1=\binom{n}{l}-\binom{l+1}{1}\binom{n-(m+1)}{l}+\binom{l+1}{2}\binom{n-2(m+1)}{l}-\cdots$ such choices.
To count the number of choices with at least one string of length $m$, we can subtract the number of choices with no string longer than $m-1$, which is given by the number of solutions of 
$\hspace{.2 in}x_1+\cdots+x_{l+1}=k\;$ with $0\le x_i\le m-1$ for each $i$, 
so there are $\displaystyle s_2=\binom{n}{l}-\binom{l+1}{1}\binom{n-m}{l}+\binom{l+1}{2}\binom{n-2m}{l}-\cdots$ such choices.
Then there are $\displaystyle s_1-s_2=\sum_{j=1}^{\lfloor\frac{k}{m}\rfloor}(-1)^{j+1}\binom{l+1}{j}\left[\binom{n-jm}{l}-\binom{n-j(m+1)}{l}\right]$ possibilities.

(I am using the nonstandard convention that $\dbinom{r}{l}=0$ if $r<l$.)
A: 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.
A: So we can arrange the $k$ choosen numbers in order, and therefore we are speaking of k-subsets from the set $\{1,\cdots , n\}$.
Let's
 - put a $0$ in front of the subset (sequence);
 - take the backward differences;
 - neglecting the first ($=a_1$), consider the differences from the 2nd to $k$-term.
$$ \bbox[lightyellow] {  
\eqalign{
  & 0,a_{\,1} ,a_{\,2} , \cdots ,a_{\,k} \quad \left| {\;1 \le j \le a_{\,j}  \le n} \right.\quad  \Rightarrow   \cr 
  & \;a_{\,1} ,a_{\,2}  - a_{\,1} , \cdots ,a_{\,k}  - a_{\,k - 1}  = a_{\,1} ,d_{\,2} , \cdots ,d_{\,k} \quad  \Rightarrow   \cr 
  &  \Rightarrow \quad d_{\,2} ,d_{\,3} , \cdots ,d_{\,k} \quad \left| \matrix{
  \;2 \le j \hfill \cr 
  \;1 \le d_{\,j}  = a_{\,j}  - a_{\,j - 1}  \le n - 1 \hfill \cr 
  \;1 \le \sum\limits_{2\, \le \,j\, \le \,k} {d_{\,j} }  = q = a_{\,k}  - a_{\,1}  \le n - 1 \hfill \cr}  \right. \cr} 
 } \tag{1}$$
Then we are looking for the
number of (standard) compositions of $0 \le q \le n-1$ into $1 \le k-1 \le n-1$ parts , each positive (and no greater than $n-1$) , that contain runs of contiguous ones no longer than $0 \le m-1$.
We will take for the moment the cumulative version "runs no longer than", and will later manage to get the version "runs with max length equal to".  
For $k=1$, the above scheme does not apply, but for subsets with one element ,clearly, the number of contiguous elements is $1$,
and there are $n$ possible subsets.
For $2 \le k$, the same value of $q=a_{k}-a_{1}$ can be attained in $n-q$ ways, and the result shall be summed over $1 \le q \le n-1$.
It is known that the number of compositions of $q$ into $k$ parts is
$$ \bbox[lightyellow] {  
N_{\,s\,c} (q,k) = \left[ {1 \le q} \right]\left( \matrix{
  q - 1 \cr 
  k - 1 \cr}  \right)
 } \tag{2.a}$$
where $[P]$ denotes the Iverson bracket.
We can part this quantity according to the number of ones that it contains, denoted by $0\le s \le k$, as
$$ \bbox[lightyellow] {  
\eqalign{
  & N_{\,s\,cs} (q,k,s) = \left[ {k = q} \right]\left[ {k = s} \right] + \left[ {k + 1 \le q} \right]\left( \matrix{
  q - k - 1 \cr 
  k - s - 1 \cr}  \right)\left( \matrix{
  k \cr 
  s \cr}  \right) =   \cr 
  &  = \left( {\left[ {k = q} \right]\left[ {k = s} \right] + \left[ {k + 1 \le q} \right]\left( \matrix{
  q - k - 1 \cr 
  k - s - 1 \cr}  \right)} \right)\left( \matrix{
  k \cr 
  s \cr}  \right) \cr} 
 } \tag{2.b}$$
where the second term (${{k} \choose {s}}$) corresponds to the number of binary string $(1,\cdots,X,\cdots)$ 
obtained by replacing with $X$ the parts greater than one, and the first factor to the number of ways to compose the $X$s.
Coming to the binary string, clearly we can change the $X$ with a $0$, then
the number of binary strings of a given length , number of ones, and max length of runs of ones
is extensively treated in this other post.
From there we have that  the
Number of binary strings, with $s$ ones , $m$ zeros and runs of ones which are not longer than $r$
 is given by
$$ \bbox[lightyellow] {  
N_b (s,r,m + 1)\quad \left| {\;0 \le {\rm integers  }\,s,m,r} \right.\quad  = \sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( { \le \,{s \over r}\, \le \,m + 1} \right)} {\left( { - 1} \right)^j \left( \matrix{
  m + 1 \cr 
  j \cr}  \right)\left( \matrix{
  s + m - j\left( {r + 1} \right) \cr 
  s - j\left( {r + 1} \right) \cr}  \right)} 
 }\tag {3.a}$$
Translating that into into our case, the number of
binary strings with  length $k$ and $s$ ones and runs of ones no longer than $m$ is
$$ \bbox[lightyellow] {  
\eqalign{
  & N_b (s,m,k + 1 - s)\quad \left| {\;0 \le {\rm integers  }\, s,m,k  - s} \right.\quad  =   \cr 
  &  = \left[ {\;0 \le s} \right]\left[ {\;0 \le m} \right]\left[ {\;s  \le k} \right]\sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( { \le \,\,k - s + 1} \right)} {\left( { - 1} \right)^j \left( \matrix{
  k + 1 - s \cr 
  j \cr}  \right)\left( \matrix{
  k - j\left( {m + 1} \right) \cr 
  s - j\left( {m + 1} \right) \cr}  \right)}  \cr} 
 } \tag{3.b}$$
Going back through the steps above, the
Number of composition of $q$, with length $k$ , number of ones $s$ and runs of ones no longer than $m$ 
will be the above multiplied by the first factor in (2.b)
$$ \bbox[lightyellow] {  
\eqalign{
  & N_{\,c\,q\,s}  = (q,k,s,m)\quad \left| {\;{\rm integers  }q,s,m,k} \right.\quad  =   \cr 
  &  = \left( {\left[ {k = q} \right]\left[ {k = s} \right] + \left[ {k + 1 \le q} \right]\left( \matrix{
  q - k - 1 \cr 
  k - s - 1 \cr}  \right)} \right)N_b (s,m,k - s + 1) =   \cr 
  &  = \left( {\left[ {k = q} \right]\left[ {k = s} \right] + \left[ {k + 1 \le q} \right]\left( \matrix{
  q - k - 1 \cr 
  k - s - 1 \cr}  \right)} \right)\; \cdot   \cr 
  &  \cdot \sum\limits_{\left( {0\, \le } \right)\,\,j\,\,\left( { \le \,\,k - s + 1} \right)} {\left( { - 1} \right)^j \left( \matrix{
  k + 1 - s \cr 
  j \cr}  \right)\left( \matrix{
  k - j\left( {m + 1} \right) \cr 
  s - j\left( {m + 1} \right) \cr}  \right)}  \cr} 
 } \tag{4}$$
Therefore, the
number of k-subsets from the set $\{1,\cdots , n\}$ having no more than $m$ contiguous characters
is
$$ \bbox[lightyellow] {  
\eqalign{
  & N_{c\,u\,m} (n,k,m) = \left[ {1 = k} \right]\left[ {1 \le m} \right]n +   \cr 
  &  + \left[ {2 \le k} \right]\sum\limits_{0\, \le \,q\, \le \,n - 1} {\sum\limits_{0\, \le \,s\, \le \,k} {\left( {n - q} \right)N_{\,c\,q\,s} (q,k - 1,s,m - 1)} }  \cr} 
 } \tag{5.a}$$
Finally, the number of k-subsets with one or more run of contiguous elements
of length $m$, and none longer will clearly be
$$ \bbox[lightyellow] {  
N_{c\,u\,m} (n,k,m)-N_{c\,u\,m} (n,k,m-1)
 } \tag{5.b}$$
