1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ This works because you are counting the number of permutations with at least $k$ elements in there original position. $\endgroup$ – Daniel Mathias Jan 15 at 19:09
  • 1
    $\begingroup$ 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. $\endgroup$ – angryavian Jan 15 at 19:09
1
$\begingroup$

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''.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Spasoje Durovic Jan 15 at 19:24
  • $\begingroup$ @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!$... $\endgroup$ – Jose Brox Jan 15 at 19:47
  • $\begingroup$ @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. $\endgroup$ – Jose Brox Jan 15 at 19:52
  • $\begingroup$ @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|$$ $\endgroup$ – Jose Brox Jan 15 at 19:53
  • 1
    $\begingroup$ @SpasojeDurovic You are welcome, and no need to apologize, questions may be silly (I don't think this is one), but doubts and silliness are better out than in! $\endgroup$ – Jose Brox Jan 15 at 20:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.