[Math] How many ways to choose $k$ out of $n$ numbers with exactly/at least $m$ consecutive numbers

binomial-coefficientscombinatoricsprobability

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.

Best Answer

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

Related Question