Solution: 2022 Winter Final - 5

Author: Michiel Smid

Question

Let $S$ be a set of $m+w$ people, $m\ge 10$ of which are men and $w\ge 10$ of which are women. What does \[ \sum_{k=2}^{10} \binom{m}{m-k}\cdot\binom{w}{10-k} \] count?

(a)

The number $10$-element subsets of $S$ that include at least $2$ women?

(b)

The number subsets of $S$ of size at most $10$ that include at least $2$ men?

(c)

The number subsets of $S$ of size at most $10$ that include at least $2$ women?

(d)

The number $10$-element subsets of $S$ that include at least $2$ men?

(e)

None of the Above

Solution

The answer is: {The number 10-element subsets of S that include at least 2 men} and here is the explanation.

If we want to find the number of 10-element subsets that include at least 2 men, then to produce the subsets, we have to first choose the men that will be in the subset from the $m$ men in $S$. Using Theorem 3.7.1 from the textbook, we know that $\binom{n}{k} = \binom{n}{n - k}$, which means that if we want to chose $2 \leq k \leq 10$ men for the set $S$ then $\binom{m}{m-k}$ does that.

For the remaining elements in the subset, they have to be women. We have $w$ women to choose from, and for each value of $2 \leq k \leq 10$, we have $10 - k$ women to choose from, if we choose $k$ men. This is expressed in the expression $\binom{w}{10-k}$.

We use the Product Rule to determine the number of 10-element subsets for the specific $k$ amounts of men. We use the Sum Rule, expressed in the summation, to repeatedly calculate and sum the unique subsets containing $2, 3, … 10$ men and $8, 7, … 0$ women, respectively.