# Inclusion–exclusion principle and permutations / derangements

In order to practice the Inclusion–exclusion principle and permutations / derangements, I tried to develop an exercise on my own.

Assume there are $6$ players throwing a fair die with $6$ sides. In this game, player 1 is required to throw a 1, player 2 is required to throw a 2 and so on. The game is won if at least one player throws his required number and at most three players throw their required numbers. Otherwise, the game is lost. How likely is it that the game is won?

Without loss of generality, we assume that the number of players and the sides of the die can be both described by the set $\{1, ... , 6\}$. Since the die is fair, it doesn't matter which player throws his required number. We simply need to count the number of permutations that have at least $1$ and at most $3$ fixed points. We define

$A_k = \{6\text{-permutations of}~\{1, ... , 6\}~\text{with fixed point}~ k\}$,

so $A_k$ contains every permutation on $\{1, ... , 6\}$ that has a fixed point $k$, so for example, $A_1$ would be the set of all permutations with the fixed point $1$.

Overall, there are $n! = 6!$ possible permutations, but only $|A_1 \cup A_2 \cup A_3|$ represent a win of the game. So we are searching for the value of

$$|A_1 \cup A_2 \cup A_3| \ / \ n!$$

Using the Inclusion–exclusion principle, we receive

$$|A_1 \cup A_2 \cup A_3| = |A_1| + |A_2| + |A_3| - |A_1 \cap A_2| - |A_1 \cap A_3| - |A_2 \cap A_3| + |A_1 \cap A_2 \cap A_3|$$

and thus,

$$|A_1 \cup A_2 \cup A_3| = 3\times(n-1)! \ - \ 3\times(n-2)! \ + \ 3\times(n-3)! = 306,$$

which gives us a probability of

$$306/6! = 0,425$$

to win the game.

• Could you clarify your definition of $A_k$? With the current definition, I don't see why the probability is $|A_1 \cup A_2 \cup A_3| \ / \ n!$. – pisco Sep 24 '17 at 10:09
• I tried to clarify my definition. My solution could be totally wrong, of course! At this point, I actually believe that I have to divide through $n^n$ actually, not $n!$. – Borol Sep 24 '17 at 10:18

For the game, the probability of exactly $k$ person get correct is $$P_k=\binom{6}{k}(\frac{5}{6})^{6-k}(\frac{1}{6})^k$$ So the answer is just $P_1+P_2+P_3 = 0.6564$
• Your denominator is incorrect. When each of the six players rolls a die, there are six possible outcomes. Hence, there are a total of $6^6$ possible outcomes rather $6!$ possible outcomes. – N. F. Taussig Sep 24 '17 at 10:21
• @N.F.Taussig I think we both are wrong. If the outcome of those 6 players is $1,2,3,3,3,3$, it satisfies the condition, but neither of us accounted for them. – pisco Sep 24 '17 at 10:26
A derangement is a permutation of a set that leaves no object in its proper place. However, as Pisco points out in the comments the outcome $(1, 2, 3, 3, 3, 3)$ satisfies the requirement that three of the players get the desired outcome while the other three do not, so this is not a problem about derangements. Each player has one good outcome and five bad ones. Hence, each player has probability $1/6$ of obtaining the desired outcome and $5/6$ of not getting the desired outcome. Hence, the probability that exactly $k$ of the players obtain the desired outcome is $$\binom{6}{k}\left(\frac{1}{6}\right)^k\left(\frac{5}{6}\right)^{6 - k}$$ Hence, the probability that at least one player and at most three players obtain the desired outcome is $$\binom{6}{1}\left(\frac{1}{6}\right)\left(\frac{5}{6}\right)^5 + \binom{6}{2}\left(\frac{5}{6}\right)^4 + \binom{6}{3}\left(\frac{1}{6}\right)^3\left(\frac{5}{6}\right)^3 = \frac{6 \cdot 5 + 15 \cdot 25 + 20 \cdot 125}{6^6} = \frac{30 + 375 + 2500}{6^6} = \frac{2905}{46656}$$