Editing Derangement (section)

=== Derivation by inclusion–exclusion principle ===

One may derive a non-recursive formula for the number of derangements of an ''n''-set, as well. For <math>1 \leq k \leq n</math> we define <math>S_k</math> to be the set of permutations of {{mvar|n}} objects that fix the {{nobr|{{mvar|k}}{{hairsp}}th}} object. Any intersection of a collection of {{mvar|i}} of these sets fixes a particular set of {{mvar|i}} objects and therefore contains <math>(n-i)!</math> permutations. There are <math display="inline">{n \choose i}</math> such collections, so the [[inclusion–exclusion principle]] yields
<math display="block">
\begin{align}
     |S_1 \cup \dotsm \cup S_n|
  &= \sum_i \left|S_i\right|
    - \sum_{i < j} \left|S_i \cap S_j\right|
    + \sum_{i < j < k} \left|S_i \cap S_j \cap S_k\right|
    + \cdots
    + (-1)^{n + 1} \left|S_1 \cap \dotsm \cap S_n\right|\\
  &= {n \choose 1}(n - 1)! - {n \choose 2}(n - 2)! + {n \choose 3}(n - 3)! - \cdots + (-1)^{n+1}{n \choose n} 0!\\
  &= \sum_{i=1}^n (-1)^{i+1}{n \choose i}(n - i)!\\
  &= n!\ \sum_{i=1}^n {(-1)^{i+1} \over i!},
\end{align}
</math>
and since a derangement is a permutation that leaves none of the ''n'' objects fixed, this implies
<math display="block">!n = n! - \left|S_1 \cup \dotsm \cup S_n\right| = n! \sum_{i=0}^n \frac{(-1)^i}{i!} ~.</math>

On the other hand, <math>n!=\sum_{i=0}^{n} \binom{n}{i}\ !i</math> since we can choose <math>n - i</math> elements to be in their own place and
derange the other {{mvar|i}} elements in just {{math|!''i''}} ways, by definition.<ref>{{cite journal |first=M.T.L. |last=Bizley |date=May 1967 |title=A note on derangements |journal=Math. Gaz. |volume=51 |issue=376 |pages=118–120 |doi=10.2307/3614384 |jstor=3614384 }}</ref>