In how many ways can we choose 4 different numbers from the set ${1,2,3,...,8,9,10}$ so that no two numbers are next to each other?

Question

I did this question using PIE and I'm confused as to why I'm not getting the right answer.

My approach:

Use complementary counting. There are $\binom{10}{4}$ ways to choose 4 different numbers.

I then subtracted $9\cdot\binom{8}{2}$ because there are $9$ ways to choose the pair of numbers and then $\binom{8}{2}$ ways to choose the last two numbers.

I then added $8\cdot\binom{8}{1}$ because I subtracted this case twice and thus have to add it in once.

I then subtracted $7$.

I got a final answer of $7$, but the correct answer is $35$. What did I do wrong?

Answer 1

It looks like you applied the Inclusion-Exclusion Principle to cases with two consecutive, three consecutive, and four consecutive numbers. However, you should instead apply the Inclusion-Exclusion Principle to pairs of consecutive numbers.

There are $\binom{10}{4}$ ways to choose four numbers from the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$.

A pair of consecutive numbers: Your count is correct. The smaller of the two consecutive numbers must occur in one of the first nine positions. Choosing the smaller also determines the larger. The remaining two numbers can be selected in $\binom{8}{2}$ ways, so there are $$\binom{9}{1}\binom{8}{2}$$ such selections.

Two pairs of consecutive numbers: This can occur in two ways. The pairs can overlap, or they are disjoint.

Two overlapping pairs: This means that three consecutive numbers are selected. Since the smallest of these three consecutive numbers must occur in one of the first eight positions. That leaves seven choices for the remaining number. Hence, there are $$\binom{8}{1}\binom{7}{1}$$ such selections.

Two disjoint pairs: We have eight available positions, two for the pairs and six for the other six numbers. Choose two of the eight positions for the pairs. Doing so determines the pairs. For instance, if we choose the third and fifth positions, then the pairs are $3, 4$ and $6, 7$. $$1, 2, \boxed{3, 4}, 5, \boxed{6, 7}, 8, 9, 10$$ Hence, there are $$\binom{8}{2}$$ such selections.

Three pairs: Since we are only selecting four numbers, this can only occur if we have four consecutive numbers. The smallest of these numbers can be selected in seven ways. Hence, there are $$\binom{7}{1}$$ such selections.

By the Inclusion-Exclusion Principle, the number of ways four numbers can be selected from the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ such that no two consecutive numbers are selected is $$\binom{10}{4} - \binom{9}{1}\binom{8}{2} + \binom{8}{1}\binom{7}{1} + \binom{8}{2} - \binom{7}{1}$$

Answer 2

As an alternative method, imagine $6$ stars in a row (the non chosen numbers), and among them place $4$ bars in locations chosen from the $7$ gaps in between or outside of the $6$ stars. Now you have $10$ objects in a row and the $4$ bar locations correspond to the numbers you have chosen.

Convince yourself that there is a 1-1 correspondence between these star-bar things and the sets of $4$ numbers you want.

The total number of them is the number of ways to choose $4$ spots from a set of $7$ spots i.e. $C(7,4) = 35$.

Answer 3

Although I prefer the "gap solution" presented by @Ned, here is another way:

• Let $d_0$ be the smallest chosen number and $d_1,d_2,d_3$ the differences to the corresponding following ones. So we have to find the number of integer solutions of

$$d_0+d_1+d_2+d_3 \leq 10 \mbox{ with } 1\leq d_0, 2\leq d_1,d_2,d_3 $$

• Setting $y_0 =d_0-1$ and $y_i = d_i - 2$ for $i=1,2,3$ we now have to find the number of integer solutions of

$$y_0+y_1+y_2+y_3 \leq 3 \mbox{ with } 0\leq y_0,y_1,y_2,y_3 $$

So, we need to consider the $4$ cases where the RHS is $0,1,2,3$:

$$\underbrace{\binom{0+3}{3}}_{RHS=0} + \underbrace{\binom{1+3}{3}}_{RHS=1} + \underbrace{\binom{2+3}{3}}_{RHS=2} + \underbrace{\binom{3+3}{3}}_{RHS=3} = 35$$

Answer 4

Consider the map $\star\mapsto\square\times$ and $|\mapsto\times$ on a set of $4\,\star$s and $3\,|$s. That is, $$ \underbrace{\square\times}_\star\underbrace{\square\times}_\star\underbrace{\square\times}_\star\underbrace{\square\times}_\star\underbrace{\times}_|\underbrace{\times}_|\underbrace{\times}_| $$ Rearrange the $\star$s and $|$s in all $\binom{7}{3}$ ways possible. Convert to $\square$s and $\times$s and remove the rightmost $\times$. Number $1$ to $10$ from left to right. Choose the numbers on the $\square$s.

---

For example: $|\star\star\,|\star|\,\star\mapsto\underset1\times\,\underset2\square\underset3\times\underset4\square\underset5\times\underset6\times\,\underset7\square\underset8\times\underset9\times\,\underset{10}\square\to\{2,4,7,10\}$

---

$\binom{7}{3}=35$.

Answer 5

I wanted to solve this using PIE, symmetry, and only a 'start-up kit' of combinatorial truths.

We agree on this

The count for the number of ways of choosing $2$ different elements from $\{1,2,\dots,n\}$ that are not next to each other is given by

$\tag 1 \binom {n-1}{2}$

Also, in general, if $g(n,r)$ is the count of choosing $r$ different elements from $\{1,2,\dots,n\}$ that are not next to each other, then

$\tag 2 g(n,1) = n \; \text{ and } g(2r-1,r) = 1$

Using these facts and the counting principle we can solve the OP's problem using PIE.

The OP solutions set $\mathcal G$ is the union of two sets

$\tag 3 \mathcal L: A \in \mathcal L \text{ if its first two elements belong to } \{1,2,3,4,5\}$

$\tag 4 \mathcal R: A \in \mathcal R \text{ if its last two elements belong to } \{6,7,8,9,10\}$

Exercise: Using only our kit (and don't forget to use symmetry arguments) show that

$\quad |\mathcal L| = 31$

$\quad |\mathcal R| = 31$

$\quad |\mathcal L \cap \mathcal R| = 27$

and so

$\quad |\mathcal G| = |\mathcal L \cup \mathcal R| = |\mathcal L| + |\mathcal R| - |\mathcal L \cap \mathcal R| = 35$