Solution: 2019 Fall Midterm - 3

Author: Michiel Smid

Question

Let $k$ and $n$ be integers with $2 \leq k \leq n$ and consider the set $S = \{1,2,...,n\}$. What is the number of $k$-element subsets of $S$ that do not contain 1 or do not contain 2?

(a)

${n - 1 \choose k} + {n - 1 \choose k}$

(b)

${n - 2 \choose k}$

(c)

${n \choose k} - {n - 2 \choose k - 2}$

(d)

${n \choose k} - {n - 1 \choose k - 1} - {n - 1 \choose k - 1}$

Solution

Determine the set of all $k$-element subsets of $S$ that do contain 1 or 2

We place 1 in the k-element subset

We then place 2 in the k-element subset

We choose the remaining $k-2$ elements from the remaining $n-2$ elements in $S$: $\binom{n-2}{k-2}$

Thus, the total number of $k$-element subsets of $S$ that contain 1 or 2 is $2 \cdot \binom{n-2}{k-2}$
Profit

Thus, the total number of $k$-element subsets of $S$ that do not contain 1 or 2 is $\binom{n}{k} - \binom{n-2}{k-2}$