$4$-element subsets of the set $\{1,2,3,\ldots,10\}$ that do not contain any pair of consecutive numbers

Solution 1:

Let's apply your strategy of using the Inclusion-Exclusion Principle.

There are $\binom{10}{4}$ four-element subsets of a ten-element set. From these, we must exclude those subsets containing at least two consecutive numbers.

A string of at least two consecutive numbers in the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ can begin with any of the nine numbers less than $10$. Once we select a pair of consecutive numbers beginning with one of these nine numbers, we must select two additional elements of the ten-element set from the eight elements that are not in the pair of consecutive numbers, which we can do in $\binom{8}{2}$ ways. Thus, it appears we have $9 \cdot \binom{8}{2}$ sets containing at least two consecutive numbers. However, we have overcounted since we have counted sets containing two disjoint pairs twice. There are $\binom{8}{2}$ such sets since we must exclude from the $\binom{9}{2}$ ways of selecting two of the nine numbers less than $10$ as starting points for the two pairs of consecutive integers the $\binom{8}{1}$ ways of selecting consecutive starting points that would prevent them from being disjoint. Note that it is a consequence of Pascal's Identity that $\binom{9}{2} - \binom{8}{1} = \binom{8}{2}$. Hence, there are $$9 \cdot \binom{8}{2} - \left[\binom{9}{2} - \binom{8}{1}\right] = 9 \cdot \binom{8}{2} - \binom{8}{2} = 8 \cdot \binom{8}{2}$$ four-element subsets containing at least two consecutive numbers.

A string of at least three consecutive numbers in the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ can begin with any of the eight numbers less than $9$. Once we select a triple of consecutive numbers, we can select the remaining element in the subset from one of the seven elements in the set that are not in the triple, giving $$8 \cdot \binom{7}{1}$$ four-element subsets that contain at least three consecutive numbers.

A string of four consecutive numbers in the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ can begin with any of the seven numbers less than $8$.

Thus, by the Inclusion-Exclusion Principle, the number of four-element subsets of the set $\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$ that do not contain consecutive numbers is $$\binom{10}{4} - 8 \cdot \binom{8}{2} + 8 \cdot \binom{7}{1} - 7 = 210 - 224 + 56 - 7 = 35$$

Addendum: A more efficient approach is to arrange six blue and four green balls in a row so that no two of the green balls are consecutive, then number the balls from left to right. The numbers on the green balls are the desired subset of four numbers, no two of which are consecutive, selected from the set $[10] = \{1, 2, 3, 4, 5, 6, 7, 8, 9, 10\}$.

Line up six blue balls in a row. This creates seven spaces, five between successive blue balls and two at the ends of the row. $$\square b \square b \square b \square b \square b \square b \square$$ To ensure that no two of the green balls are consecutive, we select four of these seven spaces in which to place a green ball, which can be done in $$\binom{7}{4} = 35$$ ways. We now number the balls from left to right. The numbers on the green balls are the desired subset of four numbers selected from the set $[10]$, no two of which are consecutive.

Solution 2:

Since $ \binom{10}{4} $ is not a big number, we may use a brute-force approach and get the number $35$. https://gist.github.com/mtp1376/32851179f609f182dd4d

Solution 3:

Final answer:

$$35$$

If we start with a simpler problem, of counting how many 4 element subsets there are of $\{1, \dotsc, 10\}$, then that's ${10 \choose 4}$. Another way of thinking about binomial coefficient ${n \choose r}$ is the number of $n$-character strings over the alphabet $\{0,1\}$ with $r$ $1$s. The equivalence of this is due to the fact that the $1$ tells you what's in the subset and the $0$ tells you what isn't. We'll use the latter picture now.

A $1$ can't be followed by a $1$ so must be followed by a $0$. So our alphabet will be $\{0,10\}$ instead of $\{0,1\}$. The extra $0$ after the $1$ stops you from including consecutive numbers. Our strings will have four $10$s and two $0$s, which makes the number ${6 \choose 2} = \frac{6 \cdot 5}{2} = 15$. We also need to include the strings which end in $1$, which means adding ${6 \choose 3} = 20$.