# Number of combinations of selecting $r$ numbers from first $n$ natural numbers of which exactly $m$ are consective.

Number of combinations of selecting $r$ numbers from first $n$ natural numbers of which exactly $m$ are consective.

Say $g(n,r,m)$ is the number of such combinations. The two cases of $m=r$ and $m=1$ are easy:

$g(n,r,r) = n-r+1$

$g(n,r,1) = \binom{n-r+1}{r}$

Example: $n=5, r=3, m=1$

Here we have to select three numbers from set $\{1,2,3,4,5\}$

So $g(5,3,3) = 5-2+1 = 3$, The subsets being $\{\{1,2,3\},\{2,3,4\},\{3,4,5\}\}$

So $g(5,3,2) = 6$, With subsets $\{\{1,2,4\},\{1,3,4\},\{1,2,5\},\{2,3,5\},\{1,4,5\},\{2,4,5\}\}$

$g(5,3,1) = \binom{5-3+1}{3}=\binom{3}{3}=1$, The subsets $\{1,3,5\}$

I am looking for a general formula to enumerate for values of $m$ other then $m=1$ and $m=r$.

By trial I found that for $n$ even and $r=n/2$ the enumerations are given by A203717 in $n/2^{nd}$ row and the value is $n/2+1$ times the $m^{th}$entry.

• What exactly does it mean that "exactly $m$ are consecutive"? Is the selection allowed to contain two or more runs of $m$ consecutive numbers? (I guess so, since your examples for $m=1$ contain lots of runs of $1$ consecutive number?) – joriki Jul 17 '15 at 6:48
• @joriki I realize. "Exactly" was meant for the longest run of consecutive numbers. So as not to count the codes that have both three consecutive runs and one run in $m=1$ case. – Abu Bakar Jul 17 '15 at 11:53

You can do this using generating functions. If we let $x^k$ represent $k$ consecutive numbers and one gap, the number of ways to make them fill $n+1$ slots (plus $1$ for the extra gap) is
$$[x^r]\left(1+x+\cdots+x^m\right)^{n-r+1}=[x^r]\left(\frac{1-x^{m+1}}{1-x}\right)^{n-r+1}\;,$$
where $[x^r]$ denotes extracting the coefficient of $x^r$. Since this allows up to $m$ consecutive numbers and we want exactly $m$ consecutive numbers, we need to subtract the number of selections with up to $m-1$ consecutive numbers, so the result is
$$[x^r]\left(\left(\frac{1-x^{m+1}}{1-x}\right)^{n-r+1}-\;\left(\frac{1-x^m}{1-x}\right)^{n-r+1}\right)=[x^r]\frac{\left(1-x^{m+1}\right)^{n-r+1}-\left(1-x^m\right)^{n-r+1}}{(1-x)^{n-r+1}}\;.$$
• @Galaxy: You can use the binomial expansion for the numerator and the negative binomial series for the denominator -- that gives you a double sum which you can rearrange according to powers of $x$, giving you a single sum for the coefficient of $x^r$. – joriki Jul 17 '15 at 12:35