Buy 16 Happy Meals, each time get a toy from a set of 8. What is the probability that the whole set is collected?

A straightforward application of the inclusion-exclusion principle will do.

The sets under consideration are sets of Happy Meals. Happy Meals are the same or different only based on the sequence of toys received.

We have subsets now with different properties. Let \(A\subset \{1,\ldots,8\}\) be a set of toys, and \(T_{A}\) be the set of Happy Meals that do not contain toys in \(A\). For example, \(T_{\{1\}}\) is the set of Happy Meals missing toy 1. What we really want to find is the size of this set:

\( T_{\{\}}\backslash(T_{\{1\}}\cup\cdots\cup T_{\{8\}}) \)

which contain just those Happy Meals that aren’t missing any toys.

Here’s where we apply the inclusion-exclusion principle. The size of the second part above is:
\(\sum_{i=1}^{8} (-1)^{i-1} (\sum_{A:|A|=i} |T_A|)\)
or
\((|T_{\{1\}}|+ \cdots +|T_{\{8\}}|) – (|T_{\{1\}}\cap T_{\{2\}}|+ \cdots +|T_{\{7\}}\cap T_{\{8\}}|) + (|T_{\{1\}}\cap T_{\{2\}}\cap T_{\{3\}}| + \cdots ) – \cdots\)

Now, notice the following interesting fact:

\(T_{A \cup B} = T_A \cap T_B\),

because the Happy Meals that are missing toys in \(A\cup B\) are exactly those that do not contain toys in \(A\) and do not contain toys in \(B\). Further note that \(|T_A|=|T_B|\) if \(|A|=|B|\), because the number of Happy Meals only depends on the number of excluded toys that characterizes them. So replace \(|T_A|\) by \(N_{|A|}\)

Taking the above into consideration, we find the size of \(T_{\{1\}}\cup\cdots\cup T_{\{8\}}\) to be

\(\sum_{i=1}^{8} (-1)^{i-1} (\sum_{A:|A|=i} N_i) = \sum_{i=1}^{8} (-1)^{i-1} {8\choose i} N_i\)

Clearly, the number of Happy Meals that do not contain some particular pre-determined \(i\) toys is \(N_i = (8-i)^{16}\), so the size of the set is \(\sum_{i=1}^{8} (-1)^{i-1} {8 \choose i} (8-i)^{16}\) or \({8 \choose 1}7^{16} – {8 \choose 2}6^{16} + {8 \choose 3}5^{16} – {8 \choose 4}4^{16} + {8 \choose 5}3^{16} – {8 \choose 6}2^{16} + {8 \choose 7}1^{16} = 195119050093696\).

The answer to the original problem is

\((8^{16} – 195119050093696)/8^{16} = 343/1118 \approx 0.3068\).

The solution is at once generalizable to any number of toys and any number of Happy Meals.