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.
- 633
1 Answers
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}
- 27,041