I read many articles on the derivation of the derangement formula but I can't understand them clearly. At first I read the Wikipedia article. I understand the recursive derivation of derangement. But I am interested in understanding the inclusion-exclusion based formula for derangements.
[Math] Derivation of derangement with inclusion-exclusion
derangementsinclusion-exclusion
Related Solutions
Inclusion-exclusion is a special case of the generalized Möbius inversion formula on a locally finite poset (partially-ordered set). For example:
- If the poset is the subsets of some given set $S$ with set inclusion as the partial order, you get the classic inclusion-exclusion formula.
- If the poset is the positive integers with divisibility as the partial order, you get the usual Möbius inversion formula in number theory (cf. André Nicolas's answer).
- If the poset is the positive integers with "$\leq$" as the partial order, you get the (backwards) finite difference operator.
- If the poset is bonds of a graph with refinement as the partial order, you get the chromatic polynomial of the graph.
So any application of these could be considered a use of the inclusion-exclusion formula, generally speaking.
For more information and examples, see
- The Wikipedia page on incidence algebra.
- Bender and Goldman's "On the Applications of Mobius Inversion in Combinatorial Analysis" (American Mathematical Monthly 82(8) 1975: 789-803).
- Rota's classic "On the Foundations of Combinatorial Theory I: Theory of Möbius Functions" (Probability Theory and Related Fields 2 (4) 1964: 340–368).
- Chapter 3 of Stanley's Enumerative Combinatorics, Vol. 1.
I'm not sure I would call them famous, but here are some examples I've seen on MSE. (The second was an answer to one of my questions; all the others are answers I've given.)
- Proving $a!\, b! = \sum_{i=0}^{b}\binom{b}{i}(-1)^{i}\frac{(a+b+1)!}{(a+i+1)}$. See here.
- A combinatorial proof that $\int {x^n e^x dx} = e^x \sum_{k = 0}^n ( - 1)^k \frac{n!}{(n-k)!}x^{n-k} + C$.
- A generalization of the derangement problem involving the number of fixed points with $n$ different permutations (rather than just 1).
- Proving $\sum\limits_{r=0}^n \frac{(-1)^r}{r+1}\binom{n}{r} = \frac1{n+1}$. See here.
We do not have to pick the last element. We can pick other element as well and the proof will still work.
If $j_n = n$, then it is not a derangement anymore. Hence $j_n = k$ where $k \neq n$.
We can change the proof.
You can pick a particular index $p \in \{ 1, \ldots, n\}$
For any derangement $(j_1, j_2, \ldots, j_n)$, we have $j_p \neq p$. Let $j_p = k$, where $k \in \{1, 2, \ldots, n\}\setminus \{p\}$. We now break the derangements on $n$ elements into two cases.
Case $1$: $j_k = p$
Case $2$: $j_k \neq p$.
Best Answer
Suppose we want to count $D_n$, the number of derangements of $\{1,\cdots,n\}$.
Let S be the set of all permutations of $\{1,\cdots,n\}$, and
let $T_i$ be the set of permutations which leave $i$ in its natural position.
Then $D_n=\lvert T_1^c\cap\cdots\cap T_n^c\rvert$
$=\lvert S\rvert-\sum_{i}\vert T_i\rvert+\sum_{i<j}\lvert T_i\cap T_j\rvert-\sum_{i<j<k}\lvert T_i\cap T_j\cap T_k\rvert+\cdots+(-1)^n\lvert T_1\cap\cdots\cap T_n\rvert$
$=n!-\binom{n}{1}(n-1)!+\binom{n}{2}(n-2)!-\binom{n}{3}(n-3)!+\cdots+(-1)^n\binom{n}{n}(n-n)!$
$=\displaystyle n!-\frac{n!}{1!}+\frac{n!}{2!}-\frac{n!}{3!}+\cdots+(-1)^n\frac{n!}{n!}=n!\left[1-\frac{1}{1!}+\frac{1}{2!~}-\frac{1}{3!}+\cdots+(-1)^n\frac{1}{n!}\right].$