Let $n$ be a positive integer. Find the number of permutations of $
(1, 2,…,n)$ such that no number remains in its original place.
Solution: To do this, first we are going to count the number of permutations where at
least one number remains in its place, according to the inclusion-exclusion principle, we must first add the permutations where a given number is
fixed, then subtract the permutations where 2 given numbers are fixed and so on.
To find a permutation that fixes $k$ given elements, we only have to arrange the rest,
which can be done in $(n − k)!$ ways. However, if we do this for every choice of
$k$ elements, we are counting ${n \choose
k}(n − k)! = \frac{n!}{k!} $ permutations. Since in total there are $n!$ permutations we get as our result:$$n!-\left(\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+…+(-1)^{n+1}\frac{n!}{n!}\right)$$
I'm a bit confused about a point of the solution, when we fix $k$ elements and rearrange the other $n-k$, some of the remaining elements will stay fixed in their position right? so why does this work?
Best Answer
Your confusion seems to be with the inclusion-exclusion principle in itself: when we say that $|A\cup B|=|A|+|B|-|A\cap B|$ it is precisely because $A$ and $B$ have some elements in common, those of $A\cap B$, and we are counting them twice, once in $|A|$ and again in $|B|$. In your problem it is the same, you look first at those permutations which have at least one fixed element, so you continue with the inclusion-exclusion principle until you take into account all the ``common elements''.