We throw a die a number of times. We let $Y_k$ be the number of different faces that came up after $k$ throws. Now we want $P[Y_k \leq 5]$.
According to the answer sheet, we use the principle of inclusion-exclusion here to arrive at the following answer:
$P(Y_k \leq 5) = \binom{6}{5}(\frac{5}{6})^k – \binom{6}{4}(\frac{4}{6})^k + \binom{6}{3}(\frac{3}{6})^k – \binom{6}{2}(\frac{2}{6})^k + \binom{6}{1}(\frac{1}{6})^k – \binom{6}{0}(\frac{0}{6})^k$
(which I believe to be equal to)
$P(Y_k \leq 5) = P(Y_k = 5) – P(Y_k = 4) + P(Y_k = 3) – P(Y_k = 2) + P(Y_k = 1) – P(Y_k = 0)$
But I just can't wrap my head around how the principle of inclusion-exclusion was exactly used here. My first thought was that it has something to do with the fact that if we see 5 faces, we've also seen at least 4 faces, etc. so that $[Y_k \leq 4]$ is a subset of $[Y_k \leq 5]$. I've tried to manually calculate (using the principle of inclusion-exclusion) $P(Y_k = 1 \cup Y_k = 2 \cup Y_k = 3 \cup Y_k = 4 \cup Y_k = 5)$ but I don't arrive at the same answer.
So far I haven't come to a good intuitive understanding yet, it would be great if someone could help me grasp this.
Best Answer
Let $E_i$ be the event that face number $i$ does not appear, for each $i=1,2,\dots,6$. Then event $\{Y_k\le 5\}$ is the same as the event that at least one $E_i$ occurs, i.e. that at least one face is missing. Therefore, using the principle of inclusion exclusion, and the symmetry of the problem, \begin{align} P(Y_k\le 5) &=P\left(\bigcup_{i=1}^6E_i\right) \\&=\sum_{r=1}^6(-1)^{r+1}\binom{6}rP(E_1\cap E_2\cap\dots\cap E_r) \\&=\sum_{r=1}^6(-1)^{r+1}\binom6r\left(\frac{6-r}{6}\right)^k. \end{align} This is where the equality you were given comes from.