Solution: 2018 Fall Midterm - 10

Author: Michiel Smid

Question

Let $n \geq 1$ be an integer and consider a set $\mathcal{B} = \{B_1,B_2,\dots,B_n\}$ of $n$ beer bottles and a set $\mathcal{C} = \{C_1,C_2,\dots,C_n\}$ of $n$ cider bottles.
For any integer $k$ with $0 \leq k \leq n$, consider subsets $X$ of $\mathcal{B} \cup \mathcal{C}$, such that $X$ consists of exactly $k$ bottles and no two bottles in $X$ have the same index. (For example, if $B_n \in X$, then $C_n \notin X$.)
Let $F(n,k)$ be the number of such subsets X.
Which of the following is true for all integers $n \geq 2$ and $k$ with $1 \leq k \leq n - 1$?

(a)

$F(n,k) = F(n-1,k)\ +$ $ F(n-1,k-1)$

(b)

$F(n,k) = F(n-1,k)\ +$ $ 2 \cdot F(n-1,k-1)$

(c)

$F(n,k) = F(n,k-1)\ +$ $ F(n-1,k-1)$

(d)

$F(n,k) = F(n,k-1)\ +$ $ 2 \cdot F(n-1,k-1)$

Solution

To derive the recurrence relation for $ F(n,k) $, we consider two cases:

$ X $ does not contain $ B_n $ or $ C_n $:
In this case, $ X $ is a subset of the first $ n-1 $ pairs, so there are $ F(n-1, k) $ such subsets.
$ X $ contains either $ B_n $ or $ C_n $ (but not both):
If $ X $ contains $ B_n $, then the remaining $ k-1 $ elements must be chosen from the first $ n-1 $ pairs, which can be done in $ F(n-1, k-1) $ ways.
Similarly, if $ X $ contains $ C_n $, then the remaining $ k-1 $ elements must be chosen from the first $ n-1 $ pairs, which can also be done in $ F(n-1, k-1) $ ways.
Since $ B_n $ and $ C_n $ are mutually exclusive, we get $ 2 \cdot F(n-1, k-1) $ ways in total.

Adding these two cases together, we obtain the recurrence relation:

$F(n,k) = F(n-1,k) + 2 \cdot F(n-1,k-1)$

This holds for all integers $ n \geq 2 $ and $ k $ with $ 1 \leq k \leq n - 1 $.