Solution: 2017 Fall Midterm - 16

Author: Michiel Smid

Question

Let $X = \{1,2,...,20\}$. You choose a uniformly random 7-element subset $Y$ of $X$. Define the event

What is $\Pr(A)$?

(a)

$\frac{2 \cdot {20 \choose 6} - {20 \choose 5}}{{20 \choose 7}}$

(b)

$\frac{{19 \choose 6} + {19 \choose 6}}{{20 \choose 7}}$

(c)

$\frac{2 \cdot {19 \choose 7} - {18 \choose 7}}{{20 \choose 7}}$

(d)

$\frac{2 \cdot {19 \choose 6} - {18 \choose 5}}{{20 \choose 7}}$

Let’s break it down into 2 cases:

B = \enquote{3 is an element of $ Y $}
First, we assume that 3 is an element of $ Y $.
We choose 6 elements from the remaining 19 elements: $ |B| = \binom{19}{6} $
C = \enquote{13 is an element of $ Y $}
First, we assume that 13 is an element of $ Y $.
We choose 6 elements from the remaining 19 elements: $ |C| = \binom{19}{6} $
$ A = B \cup C $
$ B \cap C = $ \enquote{3 and 13 are elements of $ Y $}
First, we assume that 3 and 13 are elements of $ Y $.
We choose 5 elements from the remaining 18 elements: $ |B \cap C| = \binom{18}{5} $

$ |B \cup C| = |B| + |C| - |B \cap C| $

$ |B \cup C| = \binom{19}{6} + \binom{19}{6} - \binom{18}{5} $

$ |B \cup C| = 2 \cdot \binom{19}{6} - \binom{18}{5} $

There are a total of $ \binom{20}{7} $ ways to choose a 7-element subset of $ X $ of size 20.

$ Pr(A) = \frac{|B \cup C|}{\binom{20}{7}} $

$ Pr(A) = \frac{2 \cdot \binom{19}{6} - \binom{18}{5}}{\binom{20}{7}} $