Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
1  
@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
add comment

3 Answers

up vote 2 down vote accepted

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$$

share|improve this answer
add comment

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.

ADDENDUM

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}\,.$$

share|improve this answer
add comment

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

Lottery combinatorics by McPherson & Hodson

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.