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.

  • 1
    $\begingroup$ 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?) $\endgroup$ – joriki Jul 17 '15 at 6:48
  • $\begingroup$ @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. $\endgroup$ – 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}}\;. $$

This contains your two results as special cases.

  • $\begingroup$ thanks. How may I get the closed form formula for the particular coefficient? $\endgroup$ – Abu Bakar Jul 17 '15 at 12:30
  • 1
    $\begingroup$ @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$. $\endgroup$ – joriki Jul 17 '15 at 12:35

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.