# How many ways to choose $k$ out of $n$ numbers with exactly/at least $m$ consecutive numbers?

How many ways to choose $k$ out of $n$ numbers is a standard problem in undergraduate probability theory that has the binomial coefficient as its solution. An example would be lottery games were you have $13983816$ ways to choose $6$ numbers out of $49$.

My question is: How many ways are there to choose $k$ out of $n$ numbers with exactly/at least $m$ consecutive numbers?

An example would be how many ways are there to choose $6$ out of $49$ numbers with exactly/at least $5$ consecutive numbers, e.g. $\{2,3,4,5,6,26\}$? I read that the answer here is $1936$ ways for the "at least"-case.

I would like to have a general formula and if possible a derivation of it. Good references are also welcome. Thank you.

-
The "exactly/at least" wording is confusing, perhaps it could be worded as "a minimum of $m$ consecutive...". I think the derivation starts by noting that the consecutive constraint really reduces the number of "choices" by $m-1$... –  abiessu Sep 8 '13 at 10:11
@abiessu: It’s an abbreviation for two separate questions, one asking for the number of ways to choose them so that exactly $m$ are consecutive, the asking for the number of ways to choose them with at least $m$ consecutive. –  Brian M. Scott Sep 8 '13 at 19:57

First we are going to make some obvious restriction:

$$m \le k \le n$$

Note that if we choose the first number then the following $m-1$ numbers can't be chosen. For example in your example if we choose $2$ to be our first number, then it implies that $3,4,5,6$ are the second, third, fourth and fifth number respectivly.

There are $n-m+1$ to choose the first number, because if we choose a number greater that $n-m$ then we can't choose $m$ consecutive number starting with that one.

Now it's we need to chose $n-m$ random numbers for $k-m$ places.

Because you've mentioned lottery tickets, where the order isn't important we'll assume that in the calculation the order isn't important.

First I want you to note something. I'll again use your example. We take numbers from 1-5 as consecutive and we'll place them in the first 5 places, and then some random number but for the purpose of presentation we'll choose 6. Then the set will be:

$${1,2,3,4,5,6}$$

Now let's think like these, we'll choose the numbers from 2-6 and will place them in the last 5 places and the random number will be 1. The set then will be;

$${1,2,3,4,5,6}$$

Aren't this sets the same? But we choose the using 2 different ways, so that means we'll make some restrictions and we'll make 2 cases.

Case 1: $k=m$

Obviously we have space only to place the consecutive number so let $P(n,k,m)$ represent the number of ways to choose $k$ numbers out of $n$ numbers with $m$ consecutive numbers, so we have:

$$P(n,k,m) = n-m+1$$

Case 2: $k \ge m+1$

Note that if $1$ is the first number of the series we can't choose the predecessor, because there isn't one. So we have:

$$P(n,k,m) = (n-m) \times \binom{n-m-1}{k-m} + \binom{n-m}{k-m}$$

And if we calculate for your example we have:

$$P(49,6,5) = (49-5) \times \binom{49-5-1}{6-5} + \binom{49-5}{6-5}$$ $$P(49,6,5) = 44 \times \binom{43}{1} + \binom{44}{1}$$ $$P(49,6,5) = 44 \times 43 + 44$$ $$P(49,6,5) = 1936$$

-

Given a subset $S$ of $[n]$, let us denote by $x_i$ (resp. $y_i$) the lengths of the successive runs of elements inside (resp. outside) $S$. For example, if $n=7$ and $S=\{1,2,4,5,6\}$, then you have $x_1=2$ (corresponding to $1,2\in K$), $y_1=1$ (corresponding to $3\notin K$), $x_2=3$ and $y_2=1$.

Using the correspondence above, we have that any $k$-subset $S$ of $[n]$ with at least $m$ consecutive elements is uniquely determined by a unique pair $\bigl((x_i),(y_i)\bigr)$ of (finite) sequences of positive integers such that $\sum_ix_i=k, \sum_iy_i=n-k, x_i,y_i\geq1$ for each $i$ and $x_i\geq m$ for some $i$. If the sequence of $x$s has length $r$ (that is, if our subset $S$ has $r$ runs of consecutive elements), then the mutually excluding possibilities for the "braiding" of the sequence $(y_i)$ with the sequence $(x_1,\dots,x_r)$ are the following:

• If $1,n\in S$ then the braiding is of the form $x_1,y_1,x_2,y_2,\dots,x_{r-1},y_{r-1},x_r$.

• If $1,n\notin S$ then the braiding is of the form $y_1,x_1,y_2,x_2,\dots,y_r,x_r,y_{r+1}$.

• If $1\in S$ and $n\notin S$ then the braiding is of the form $x_1,y_1,x_2,y_2,\dots,x_r,y_r$.

• If $1\notin S$ but $n\in S$ then the braiding is of the form $y_1,x_1,y_2,x_2,\dots,y_r,x_r$.

Recall that the number of solutions in $\mathbb N$ of the equation $z_1+\cdots+z_p=q$ is precisely $\binom{p+q-1}{p-1}$, and the number of solutions in $\mathbb Z^+$ of the same equation is $\binom{q-1}{p-1}$ (because changing $z_i$ by $z_i-1$, then you are looking for solutions in $\mathbb N$ of $z_1+\cdots+z_p=q-p$). Since each $x_i$ must be $\geq1$, then changing $x_i$ by $x_i-1$ we see that we want solutions in $\mathbb N$ of $x_1+\cdots+x_r=k-r$ with $x_i\geq m-1$ for some $i$, so we must apply inclusion-exclusion. For each $j$ let $A_j=\bigl\{(x_1,\dots,x_r): x_1+\cdots+x_r=k-r, x_j\geq m-1\bigr\}$. If $1\leq j_1<\cdots<j_\ell\leq r$, then by changing $x_i$ by $x_i-(m-1)$ for $i=j_1,\dots,j_\ell$ we see that the elements in $A_{j_1}\cap\cdots\cap A_{j_\ell}$ correspond to solutions in $\mathbb N$ of $x_1+\cdots+x_r=k-r-\ell(m-1)$, and so $\bigl|A_{j_1}\cap\cdots\cap A_{j_\ell}\bigr|=\binom{k-\ell(m-1)-1}{r-1}$. Therefore the number of solutions $(x_1,\dots,x_r)$, for fixed $r$, is equal to

$$\sum_{\ell=1}^r(-1)^{\ell-1}\sum_{1\leq j_1<\cdots<j_\ell\leq r}\bigl|A_{j_1}\cap\cdots\cap A_{j_\ell}\bigr|=\sum_{\ell=1}^r(-1)^{\ell-1}\binom r\ell\binom{k-\ell(m-1)-1}{r-1}\,.$$

On the other hand, the number of solutions $(y_1,\dots,y_s)$ in $\mathbb Z^+$ of $y_1+\cdots+y_s=n-k$ is equal to $\binom{n-k-1}{s-1}$. Note that $s=r$ in two instances of the problem, $s=r+1$ in one instance and $s=r-1$ in the remaining instance. Thus, for fixed $r$, the total number of tuples $(y_i)$ that can be braided with a fixed sequence $(x_1,\dots,x_r)$ is equal to

\begin{align*} &\,\Biggl[\,\binom{n-k-1}{r-1}+\binom{n-k-1}{r}\Biggr]+\Biggl[\,\binom{n-k-1}{r}+\binom{n-k-1}{r+1}\Biggr]\\ =&\,\binom{n-k}{r}+\binom{n-k}{r+1}\\ =&\,\binom{n-k+1}{r+1}\,. \end{align*}

Consequently, the number of $k$-subsets of $[n]$ with at least $m$ consecutive members is equal to

$$N(n,k,m)=\sum_{r\geq1}\binom{n-k+1}r\sum_{\ell=1}^r(-1)^{\ell-1}\binom r\ell\binom{k-\ell(m-1)-1}{r-1}$$

and the number of $k$-subsets of $[n]$ with $m$ consecutive members but without $m+1$ consecutive members will be equal to $N(n,k,m)-N(n,k,m+1)$. I am assuming that when you ask for "exactly" $m$ consecutive members, you are allowing to have two or more such sequences of consecutive numbers (i.e., according to the notation above, $x_i=m$ can occur for more than one value of $i$); otherwise the problem is a lot more challenging.

Actually the restricted problem is not more difficult than the version above. Suppose that you want to construct a $k$-subset of $[n]$ containing exactly one run of $m$ consecutive numbers, and the other runs being of length less than $m$. Let $r\geq1$ be the number of runs of consecutive elements in your subset. As before, the possibilities for the runs of consecutive elements outside your subset contributes (multiplicatively) $\binom{n-k+1}{r+1}$ to the number of subsets. On the other hand, with $x_1,\dots,x_r$ as before, then exactly one of the numbers $x_i$ is equal to $m$. This can be made into $r$ ways. And now you are looking for solutions in $\mathbb Z^+$ of $z_1+\cdots+z_{r-1}=k-m$ (the $z_k$ are simply the variables $x_j$ with $j\ne i$) with $z_k<m$ for each $k$. This number can also be calculated through inclusion-exclusion: in fact, we want to calculate $\bigl|(A_1\cup\cdots\cup A_{r-1})^{\,c}\bigr|$, where $A_k=\bigl\{(w_1,\dots,w_{r-1})\in\mathbb N^{r-1}: w_1+\cdots+w_{r-1}=k-m-(r-1), w_k\geq m-1\bigr\}$ ($w_j=z_j-1$). Reasoning as in the first part of my answer we conclude that the number of desired sequences $(z_1,\dots,z_{r-1})$ is equal to

\begin{align*} &\,\binom{k-m-1}{r-2}-\sum_{\ell=1}^{r-1}(-1)^{\ell-1}\binom{r-1}\ell\binom{k-m-\ell(m-1)-1}{r-2}\\ =&\,\sum_{\ell=0}^{r-1}(-1)^\ell\binom{r-1}\ell\binom{k-m-\ell(m-1)-1}{r-2}\,. \end{align*}

Consequently the number of $k$-subsets of $[n]$ with exactly one run of $m$ consecutive members and all the other runs of consecutive members with length strictly less than $m$, is equal to

$$\sum_{r\geq1}r\,\binom{n-k+1}{r+1}\sum_{\ell=0}^{r-1}(-1)^\ell\binom{r-1}\ell\binom{k-m-\ell(m-1)-1}{r-2}\,.$$

-

After some further googling I found the following reference which gives a general formula and a derivation:

Lottery combinatorics by McPherson & Hodson

-