In the textbook I'm using to train Olympic combinatorics Combinatorial problems in Mathematical competitions by Yao Zhang there is a problem which I personally found peculiarly interesting the Euler-Bernoulli misaddressed letter problem:
How many ways to distribute $n$ distinct letters into $n$ envelops so that no letter gets to its corresponding envelop?
At first I didn't get the points and they I tried different things of what I've learned, I couldn't go farther and eventually looked at the solution, but there are things I couldn't understand at all.
The solution said that what we wanted to count was actually how many permutations of $\{1,2, \cdots, n\}$ there are such that $k$ is not at the $k^{th}$ place for any $1 \le k \le n$. And that these permutations are called derangements. Also said that this kind of permutations are permutations with not fixed point.
I know that this might be something not so difficult but I really get kind of confuse. Can someone tell with a little more detail what does it mean that stuff of permutations (With/without) fixed points?
Going a little further in the solution we set as $S$ the set of all permutations of $\{1,2, \cdots , n\} $ and $A_{i}$ the set of permutations $\{a_{1},a_{2}, \cdots , a_{n}\} $ of $\{1,2, \cdots , n\} $ satisfying $a_{i} = i$ $( i = 1,2,3 … n)$. So, I can understand this because you can use The sieve formula to get exactly the the intersection of the complement of all the sets in which the $k_{th}$ permutation is in the $k_{th}$ place.
What I can't understand very well is the cardinalities of $A_{i}$'s sets, for example how do you know that $\lvert A_{i} \rvert = (n-1)!$, $ \lvert A_{i} \cup A_{j} \rvert = (n-2)!$ or even that $ \lvert A_{i_{1}} \cup A_{i_{2}} \cup \cdots \cup A_{i_{k}} \rvert = (n-k)! $ for $ ( 1 \le i_{1} < i_{2}< \cdots < i_{k} \le n)$. I will show you the solution anyways, to help you understand better what I'm trying to ask for.
Any help, idea or correction will be welcome! Thanks for your time and attention (:
Best Answer
Let's say we want to calculate $|A_1|$. What's that? The number of ways to permute $1,2,\ldots,n$ such that the first term is $1$. Well, the first term is fixed, and we can freely permute the remaining $n-1$ numbers in $(n-1)!$ ways. The same goes for the other numbers; in calculating $|A_i|$ one of the terms is fixed and the remaining $n-1$ terms are permuted freely in $(n-1)!$ ways.
While calculating $|A_1\cap A_2|$, we have now fixed the first and second term. How many terms remain? Well, $n-2$ of them which can be permuted in $(n-2)!$ ways. I think you can see now how this and the further terms generalise.
Hope this helps. Ask anything if not clear :)