0
$\begingroup$

My problem is: Assume that every time you buy a box of cereal, you receive one of the pictures of the New York Yankees players and there are $n$ on the team. Over some time you buy $m\ge$$n$ boxes of cereal. Use the Inclusion-Exclusion principle to show that the probability that you will get all $n$ pictures is: $1- {n \choose 1}({n-1 \over n})^m + {n \choose 2}({n-2 \over n})^m \ldots + (-1)^{n-1}{n \choose n-1}({1 \over n})^m $

I am new to this principle and to combinatorics in general so I may be missing some key information or obvious details. I understand that we have a point of reference so that the first term will always be $1$ but I do not understand how we can generate the other terms or where they come from in context of the problem.

$\endgroup$
2
$\begingroup$

Hint

For $i = 1, 2, \ldots, n$, let $E_i$ be the event that you do not have a picture of player $i$. By inclusion–exclusion, $$P(E_1 \cup \cdots \cup E_n) = \sum_{1 \leq i \leq n} P(E_i) - \sum_{1 \leq i < j \leq n} P(E_i \cap E_j) + \sum_{1 \leq i < j < k \leq n} P(E_i \cap E_j \cap E_k) - \cdots.$$ Now note that $E_1 \cap E_2 \cap \cdots \cap E_r$ is the event that $m$ independently chosen cereal boxes all yielded a photograph from the same set of $n-r$ players. What is the chance of this? Would it make a difference if the set of players were different, but still the same size?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.