Let D(n,k) denotes the number of derangement with total of n elements, and having exactly k fixed positions. So, I want to show that $$D(n,k)=\frac{n!}{k!}\sum_{r=0}^{n-k}(-1)^r\frac{1}{r!}$$, using the principle of inclusion and exclusion. So firstly, what I do is let $A_i$ denotes that the ith position doesn't have a fixed position. Now, I would let $|A_i \cap A_j \cap….|$, and the total elements in this set would be n-k. Now, we will need to calculate that $$|\overline{A_i} \cap \overline{A_j}….|$$. So, we know that $|S|=(n-k)!$, and each time, we would select k elements to be fixed, and the total number would be $nCk$. Next, we apply the PIE, and it would look like:
$$|\overline{A_i}\cap \overline{A_j}…|=nCk((n-k)! – （n-kC1)(n-k-1)!+(n-kc2)(n-k-2)!-…$$ Such answer is obtained by me from working backwords from the formulae. My question is, if one element in the n-k elements is fixed, why do we have (n-kC1)(n-k-1)! number of arrangements, since this might also count 2 and 3 and more elements to be kept fixed…
Thank you so much.
Obtain this formulae for derangement using Principle of Inclusion and Exclusion
derangements
Best Answer
The relevant formula, which you can find in Stanley's Enumerative Combinatorics (vol. 1, ch. 2, eq. 2.4) is
$$f_=(T) = \sum_{Y \supseteq T}(-1)^{\#(Y-T)} f_{\ge}(Y) $$
where $f_=(T)$ counts the number of derangements where $i$ is fixed if and only if $i \in T$ and $f_\ge(Y)$ is the number of derangements where if $i \in Y$ then $i$ is fixed (but there may be more fixed points).
The point of I/E is that we have a function we know, $f_\ge$, but it doesn't count what we want because it counts permutations with greater than or equal to $k$ fixed points rather than exactly $k$ fixed points. I/E says we can correct this by taking some sort of alternating sum and the fixed points with greater than $k$ fixed points will simply cancel.
For this problem, $D_{n,k} = \binom{n}{k}f_=(T)$ where $T$ is any set of size $k$. The number of sets $Y$ of size $\#T + r$ is $\binom{n - k}{r}$ and for each set $Y$, we have $f_{\ge}(Y) = (n - \#Y)! = (n - k-r)!$.
Putting this together, we have \begin{align} D_{n,k} &= \binom{n}{k} \sum_{r = 0}^{n - k} (-1)^r \binom{n - k}{r}(n - k - r)! \\ &= \frac{n!}{k!(n-k)!} \sum_{r = 0}^{n - k} (-1)^r \frac{(n - k)!}{r!(n-k-r)!} (n - k - r)! \\ &= \frac{n!}{k!} \sum_{r = 0}^{n - k} (-1)^r \frac{1}{r!}. \end{align}