# Principle of inclusion-exclusion when counting number of unique faces

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.

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.

• How does this equation account for a different number of rolls of the die, say 10 versus 6? – Phil H Jun 19 at 6:50
• @PhilH The number of rolls, $k$, appears in the formula. – Mike Earnest Jun 19 at 17:09

No, you are misinterpreting. The equation you have is $$\mathbb{P}(\lvert F\rvert\leq 5)= \sum_{\lvert A\rvert=5}\mathbb{P}(F\subseteq A) -\sum_{\lvert A\rvert=4}\mathbb{P}(F\subseteq A) +\sum_{\lvert A\rvert=3}\mathbb{P}(F\subseteq A) -\sum_{\lvert A\rvert=2}\mathbb{P}(F\subseteq A) +\sum_{\lvert A\rvert=1}\mathbb{P}(F\subseteq A) -\sum_{\lvert A\rvert=0}\mathbb{P}(F\subseteq A) \tag{1}$$ where $$F$$ is the set of faces that show up, and $$A\subseteq \{1,2,3,4,5,6\}$$ is a subset of faces in each sum.

Expanding a little more, we have 6 events "only 1,2,3,4,5 are allowed", "only 1,2,3,4,6 are allowed", ..., "only 2,3,4,5,6 are allowed", or equivalently, the six events are "1 does not show up", "2 does not show up", ..., "6 does not show up". $$\lvert F\rvert\leq 5$$ is the union of these events, and intersecting $$k$$ of these events is precisely reducing the allowable faces to 6-$$k$$. So inclusion-exclusion gives $$\mathbb{P}(\lvert F\rvert\leq 5)=\sum_{\text{possible }1\text{-intersection}}\mathbb{P}(event) - \sum_{\text{possible }2\text{-intersection}}\mathbb{P}(event)+\dots$$ which is equation (1).

• I sort of understand the relation between this and the equation I gave, but could you elaborate on why $P(|F| = 5) = P(Y_k \leq 5)$? Why does the equation above give us the probability of getting a series of length $k$ where the number of unique faces is lower than or equal to five? – Ross Jun 18 at 20:29
• Oops, sorry it is $\lvert F\rvert\leq 5$ rather than $\lvert F\rvert=5$. – user10354138 Jun 18 at 20:39
• Ah yes thank you, for some reason when the events are"1 does not show up" (just as in Mike's answer) the equation/intuition instantly makes sense to me, but the other way around it doesn't. I'm still hoping to grasp it the other way around. But by indeed reading it as "only 1,2,3,4,5 are allowed" helps a lot. Thank you! – Ross Jun 18 at 20:54

The first term, $${6\choose5}\left(\frac56\right)^k$$, represents the probability that only five faces came up. There are $${6\choose5}$$ ways to choose which of the faces come up. The problem is that we have double-counted the cases where only four faces came up. For example, if only $$1,2,3,4$$ show up, we count this both as only $$1,2,3,4,5$$ showing up and as only $$1,2,3,4,6$$ showing up. So we have to subtract the cases where only four faces show up. This accounts for the second term. But then there is a double-counting problem when only three faces show up, and so on.

This is a typical application of the principal of inclusion and exclusion.

EDIT

When I say "five faces come up" I'm being a little sloppy. What I mean is that all the faces that show up belong to some set of five faces. This doesn't exclude the possibility that only four or fewer faces actually show up. So as you as in your comment, if the faces that show up belong to $$\{1,2,3,4\}$$ we've counted that once in the $$\{1,2,3,4,5\}$$ case and one in the $$\{1,2,3,4,6\}$$ case.

Now if you analyze the $$\{1,2,3\}$$ case, you see that we've counted it three times and subtracted it three times, so we have to add it back in.

• My apologies, I'm having trouble understanding. The first two sentences I understand, the third and especially the fourth I don't. Why is it, if we count all the cases where five faces have come up, we double count the case where only four faces came up? Is it because when we count $\{1, 2, 3, 4, 5\}$ and $\{1, 2, 3, 4, 6\}$, we've counted $\{1, 2, 3, 4\}$ twice? – Ross Jun 18 at 16:39
• @Roose I added some more details. If it's not clear now, ping me again. – saulspatz Jun 18 at 16:46
• Thank you. The case of $\{1, 2, 3\}$ I get after writing out the possibilities. There are 3 sets of cardinality 5 containing $\{1, 2, 3\}$, and 3 sets of cardinality 4 containing $\{1, 2, 3\}$. I guess the fundamental concept I am missing here, is why is it, that if we count $\{1, 2, 3, 4, 5\}$ and $\{1, 2, 3, 4, 6\}$, we are also implicitly counting $\{1, 2, 3\}$? I'm guessing this has to do with how the random variable is formulated? Is the probability equal to the following: we are counting all the possible sets out of $\{1, 2, \ldots, 6\}^k$ where there only 5 or less unique elements? – Ross Jun 18 at 17:11
• Suppose there are three rolls: $1$-$2$-$3$. This is an instance of the case where all the faces belong to $\{1,2,3\}$, but it's also an instance of the case where all the faces belong to $\{1,2,3,4,5\}$. We're counting sequences of rolls, not subsets. – saulspatz Jun 18 at 17:18
• So in the case of rolling $\{1,2,3\}$ we count it once for $\{1,2,3\}$, but also for $\{1, 2, 3, 4\}, \{1, 2, 3, 5\}, \{1, 2, 3, 6\}, \{1, 2, 3, 4, 5\}, \{1, 2, 3, 4, 6\}, \{1, 2, 3, 5, 6\}$, and we only want to count it once towards $\{1, 2, 3\}$, and the principle of inclusion/exclusion is the way we correct for this? And rolls is indeed what I meant, we're counting the rolls where there are only 5 or less unique faces, out of all possible rolls. – Ross Jun 18 at 17:37

I usually use a counting method to solve problems like this so I'll use the formula posted by Mike Ernest to solve the following specific problem. A die is rolled $$10$$ times, what is the probability that at most only five numbers from six show up?

$$P =\sum_{r=1}^6(-1)^{r+1}\binom6r\left(\frac{6-r}{6}\right)^{10}$$

$$= 6\cdot (\frac{5}{6})^{10} - 15\cdot (\frac{4}{6})^{10} + 20\cdot (\frac{3}{6})^{10} - 15\cdot (\frac{2}{6})^{10} + 6\cdot (\frac{1}{6})^{10} - 1\cdot (\frac{0}{6})^{10}$$

$$= .969033 - .260123 + .019531 - .000254 + 0 - 0\$$ (last two terms too small to count)

$$P = .7282$$