Solution: 2016 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,\dots,n\}$. What is the number of $k$-element subsets of $S$ that do not contain 1 or do not contain 2?

(a)

${n - 2 \choose k}$

(b)

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

(c)

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

(d)

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

Solution

Let’s break it down I guess

Let T be the set of all $k$-element subsets of $S$.
$ |T| = \binom{n}{k} $
Let A be the event that there is a 1 and a 2 in the subset.
That means we've gotten 1 and 2 already, leaving us with n-2 elements in the bag
This also means we have to choose k-2 more elements from the bag
$ |A| = \binom{n-2}{k-2} $

Let’s just subtract the number of ways to get 1 or 2 from the total number of ways to get a subset.

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