at least $3$ digit not goes to its exact position

Question

Total number of arrangements of the $5$ digit number $12345$ in which at least $3$ digits are not in their exact position is?

My attempt:

At least $3$ digits do not go to their exact position = exactly $3$ digits not in their exact position + exactly $4$ digits not in their exact position + exactly $5$ digits not in their exact position.

For all $5$ not in their position, the number of cases are $$5!\bigg(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\frac{1}{5!}\bigg)$$

How do I solve it from here? Please help me.

Answer 1

The number of digits not fixed can be $3,4,5$ and these are mutually exclusive.

For example, for all $5$ not in their place, the formula is given as you mentioned, using the inclusion exclusion principle. Let us call the number of such permutations as $R$. Get $R = 44$.

Now, fix any one digit in these : now, we have to displace four numbers so that none of them are in their positions : this would give $4!(1 - \frac 1{1!} + \frac 1{2!} ...)$. Call this quantity $S$, we get $5S$ for this block. Get $S = 9$.

Fix any two digits : this can be done in $10$ ways . Next switch the remaining $3$ around for no matches : you would get(can be counted by hand) only $2$ such arrangements. Add everything up.

Answer 2

For exactly 4 digits not in position , first choose the one in position and then derange 4.

$$ = {5 \choose 1} 4! \left[ 1-\frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!}+ \frac{1}{4!} \right] = 5×9 = 45 $$

For 3 not in position = $5 \choose 2$(number of derangement of 3 things) = $10 \times 2$

Answer is $44 + 45 + 20 = 109$

Answer 3

As has already been commented, you can split into mutually exclusive cases, where exactly 5, 4, or 3 digits are not in their exact positions. However I find it much easier to enumerate the cases where exactly 5, 4, or 3 digits are in their exact positions, and subtract these from $5! = 120$ total permutations.

• Total number of permutations: $5! = 120$ permutations.
• Exactly 5 digits in exact position: $1$ permutation.
• Exactly 4 digits in exact position: not possible, if 4 digits are in exact position then the 5th one must also be, so $0$ permutations.
• Exactly 3 digits in exact position: from 5 digits you can choose 2 to swap, which makes $\binom{5}{2}! = 10$ permutations.

For there to be at least 3 digits not in exact position, that means there must be 0, 1, or 2 digits in exact position; that is, less than 3 digits in exact position. So the answer is the total number of permutations, minus the total number of cases where 3, 4, or 5 digits is in exact position. This is $120 - 1 - 0 - 10$, or $109$ permutations.

You can also check it by brute force with a program, by constructing all 120 permutations, and then checking which ones have at least 3 digits not in exact position. The following code does this in Python, and confirms the answer is 109.

import itertools as it
digits = [1, 2, 3, 4, 5]
answer = 0
for p in it.permutations(digits):
    notexact = [x!=y for x, y in zip(p, digits)]
    if sum(notexact) >= 3:  # at least 3 digits not in exact position
        answer += 1
print(answer)
>> 109

Out of 120 total permutations, $12345$ itself has 5 digits in exact position, and the following 10 permutations have 3 digits in exact position: $$\left\{ 12354, 12435, 12543, 13245, 14325, 15342, 21345, 32145, 42315, 52341\right\}$$ The other 109 permutations have at most 2 digits in exact position / have at least 3 digits not in exact position.