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

combinatoricsinclusion-exclusion

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?

Best Answer

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