Combinations of 5 integers from 1 to 100 such that differences between the sorted integers of each combination is at least 5 but not more than 10?

Question

For example , I am trying to count combinations like [1,6,14,21,27] because the minimum difference between two sequential integers in the combination is 5 and the maximum distance is 8, but I don't want to count combinations like [2,4,9,16,25] because the smallest difference between the sorted numbers is 2 (too small) or combinations like [5,30,35,41,48] because the largest distance between sorted numbers is 25 (too large).

I know that the total number of ways to select 5 numbers from 100 is "100 choose 5" = 75,287,520 so the answer must be less than this.

Is there a general formula or algorithm for this type of problem?

Answer 1

Let the integers chosen be $x_1,x_2,x_3,x_4,x_5$

Construct the related 6-tuple $(y_1,y_2,y_3,y_4,y_5,y_6)$ where $y_1=x_1$, $y_2=x_2-x_1$, $\dots$, $y_5=x_5-x_4$ and $y_6=100-x_5$

Notice that the conditions you placed on the distances between adjacent numbers as well as the telescoping properties of $y$ implies the following:

$\begin{cases}y_1+y_2+\dots+y_6=100\\ 1\leq y_1\\ 5\leq y_2\leq 10\\ 5\leq y_3\leq 10\\ 5\leq y_4\leq 10\\ 5\leq y_5\leq 10\\ 0\leq y_6 \end{cases}$

Note that there is a bijection between the problem of counting the number of ways of choosing the five numbers from 1-100 with the desired properties and the problem of counting the number of 6-tuples of integers satisfying the above conditions.

From here, let us make the change of variable $z_1=y_1-1$, $z_i=y_i-5$ for $i\in\{2,3,4,5\}$ and $z_6=y_6$. This puts us to the system:

$\begin{cases}z_1+z_2+\dots+z_6=79\\ 0\leq z_1\\ 0\leq z_2\leq 5\\ 0\leq z_3\leq 5\\ 0\leq z_4\leq 5\\ 0\leq z_5\leq 5\\ 0\leq z_6\end{cases}$

From here, approach via inclusion exclusion based on which of the upper bound conditions are violated. Let $A_2,A_3,A_4,A_5$ be the events where the second, third, fourth, and fifth upper bound conditions are violated respectively.

We try to count $|A_2^c\cap A_3^c\cap\dots A_5^c| = |\Omega\setminus (A_2\cup A_3\cup\dots\cup A_5)|$

$=|\Omega|-|A_2|-|A_3|-|A_4|-|A_5|+|A_2\cap A_3|+|A_2\cap A_4|+\dots - |A_2\cap A_3\cap A_4|-\dots + |A_2\cap A_3\cap A_4\cap A_5|$

From this question we know the number of solutions where no upper bound condition is violated is $|\Omega|=\binom{79+6-1}{6-1}=\binom{84}{5}$

If some of them are violated, that means that $z_i>5$ for whichever $i$ are violated. I.e. $z_i\geq 6$. An appropriate change of variable will put this back into the known form.

For example, $|A_2\cap A_3|$ counts the number of solutions to $\begin{cases}a_1+a_2+\dots+a_6=67\\ 0\leq a_i\end{cases}$ and will have $\binom{67+6-1}{6-1}=\binom{72}{5}$ solutions.

Recognizing the symmetry between the numbers, we find the final total to be:

$$\binom{84}{5}-4\binom{78}{5}+\binom{4}{2}\binom{72}{5}-\binom{4}{3}\binom{66}{5}+\binom{60}{5}=90720$$

Answer 2

The 5 integers chosen create 6 gaps, so let $y_i$ be the number of integers in gap $i$ for $1\le i\le 6$.

Then $y_1+\cdots+y_6=95$ with $y_1, y_6\ge0$ and $4\le y_i\le9$ for $2\le i\le5$.

If $t_1=y_1, t_6=y_6$, and $t_i=y_i-4$ for $2\le i\le 5$,

then $t_1+\cdots+t_6=79$ with $t_i\ge0$ for each $i$ and $t_i\le 5$ for $2\le i\le 5$.

Using Inclusion-Exclusion, this equation has

$\displaystyle\binom{84}{5}-\binom{4}{1}\binom{78}{5}+\binom{4}{2}\binom{72}{5}-\binom{4}{3}\binom{66}{5}+\binom{4}{4}\binom{60}{5}$ solutions.

Answer 3

Choose the first integer

$$\sum_{q=1}^{100} z^q = z \sum_{q=0}^{99} z^q = z \frac{1-z^{100}}{1-z}$$

Choose four gaps at least five and not more than ten:

$$(z^5+z^6+\cdots+z^{10})^4 = (z^5 (1+\cdots+z^5))^4 = z^{20} \frac{(1-z^6)^4}{(1-z)^4}.$$

Extract those values that terminate in at most one hundred:

$$[z^{100}] \frac{1}{1-z} z^{20} \frac{(1-z^6)^4}{(1-z)^4} z \frac{1-z^{100}}{1-z} \\ = [z^{79}] \frac{1}{(1-z)^6} (1-z^6)^4 (1-z^{100}).$$

Now the multiple of $z^{100}$ does not contribute to $[z^{79}]$ and we get

$$[z^{79}] \frac{1}{(1-z)^6} (1-z^6)^4 = [z^{79}] \frac{1-4z^6+6z^{12}-4z^{18}+z^{24}}{(1-z)^6}$$

This is

$$[z^{79}] \frac{1}{(1-z)^6} - 4 [z^{73}] \frac{1}{(1-z)^6} \\ + 6 [z^{67}] \frac{1}{(1-z)^6} - 4 [z^{61}] \frac{1}{(1-z)^6} + [z^{55}] \frac{1}{(1-z)^6} \\ = {79+5\choose 5} - 4 {73+5\choose 5} \\ + 6 {67+5\choose 5} - 4 {61+5\choose 5} + {55+5\choose 5} \\ = 90720.$$