[Math] Inclusion–exclusion principle and permutations / derangements

combinatoricsdiscrete mathematicsinclusion-exclusion

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.

Best Answer

My previous answer contains a misinterpretation: the question actually has no thing to do with derangements.

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$

Related Question