# Counting with Principle of inclusion-exclusion

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?

• This works because you are counting the number of permutations with at least $k$ elements in there original position. – Daniel Mathias Jan 15 at 19:09
• Yes, that is the point of the adding and subtracting (inclusion-exclusion): to fix the over-counting that results because "some of the remaining elements will stay fixed in their position," as you noted. – angryavian Jan 15 at 19:09

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''.
• Okay so, when I count the number of permutations that fix at least one element I have ${n \choose 1}(n-1)!$ , so what happens is we fix only the first element and permute the others, then we fix only the second and permute and so on... once I've done this, if I take $n! - {n \choose 1}(n-1)!$ I would remove all the permutations s.t. at least one element is fixed, but, when I do so, some of the cases that occured during that $n$ permutations will be overcounted because when we permute the $n-1$ remaining elements we'll end up with some cases that were previously counted, that's it right? – Spasoje Durovic Jan 15 at 19:24
• @SpasojeDurovic That's more or less it! I'll try to give a more precise explanation (since you are using "at least one element fixed" in the wrong place). When you remove from all permutations the first $n!/1!$ term, you are removing those which have one fixed element and $n-1$ arbitrary. But if they are arbitrary, some repetitions will occur, so you are not removing all permutations s.t. at least one element is fixed, but only a lower bound of that. Then you realize that you have overcounted permutations with at least $2$ fixed elements, and you bound that quantity by below by $n!/2!$... – Jose Brox Jan 15 at 19:47
• @SpasojeDurovic ...but then you have overcounted permutations with at least 3 fixed elements when you tried to fix the problem with 2-fixed permutations from 1-fixed ones; so you approximate the error by $n!/3!$ and keep going. – Jose Brox Jan 15 at 19:52
• @SpasojeDurovic In the same vein, when you have 3 sets, $|A\cup B\cup C|\leq|A|+|B|+|C|$ but we have counted $|A\cap B|,|A\cap C|,|B\cap C|$ twice each, so we remove them once, but then we have removed $|A\cap B\cap C|$ thrice and we included it thrice in our first approximation, so we have no $|A\cap B\cap C|$ contribution and we have to include it, to get $$|A\cup B\cup C|=|A|+|B|+|C|-(|A\cap B|+|A\cap C|+|B\cap C|)+|A\cap B\cap C|$$ – Jose Brox Jan 15 at 19:53