Editing Derangement (section)

==Counting derangements==

Counting derangements of a set amounts to the ''hat-check problem'', in which one considers the number of ways in which ''n'' hats (call them ''h''<sub>1</sub> through ''h<sub>n</sub>'') can be returned to ''n'' people (''P''<sub>1</sub> through ''P<sub>n</sub>'') such that no hat makes it back to its owner.<ref>{{cite journal |last=Scoville |first=Richard |year=1966 |title=The Hat-Check Problem |journal=[[American Mathematical Monthly]] |volume=73 |issue=3 |pages=262–265 |doi=10.2307/2315337 |jstor=2315337}}</ref>

Each person may receive any of the ''n''&nbsp;&minus;&nbsp;1 hats that is not their own. Call the hat which the person ''P''<sub>1</sub> receives ''h<sub>i</sub>'' and consider ''h<sub>i</sub>''{{'}}s owner: ''P<sub>i</sub>'' receives either ''P''<sub>1</sub>'s hat, ''h''<sub>1</sub>, or some other. Accordingly, the problem splits into two possible cases:
# ''P<sub>i</sub>'' receives a hat other than ''h''<sub>1</sub>. This case is equivalent to solving the problem with ''n''&nbsp;&minus;&nbsp;1 people and ''n''&nbsp;&minus;&nbsp;1 hats because for each of the ''n''&nbsp;&minus;&nbsp;1 people besides ''P''<sub>1</sub> there is exactly one hat from among the remaining ''n''&nbsp;&minus;&nbsp;1 hats that they may not receive (for any ''P<sub>j</sub>'' besides ''P<sub>i</sub>'', the unreceivable hat is ''h<sub>j</sub>'', while for ''P<sub>i</sub>'' it is ''h''<sub>1</sub>). Another way to see this is to rename ''h''<sub>1</sub> to ''h''<sub>''i''</sub>, where the derangement is more explicit: for any ''j'' from 2 to ''n'', ''P''<sub>''j''</sub> cannot receive ''h''<sub>''j''</sub>.
# ''P<sub>i</sub>'' receives ''h''<sub>1</sub>. In this case the problem reduces to ''n''&nbsp;&minus;&nbsp;2 people and ''n''&nbsp;&minus;&nbsp;2 hats, because ''P''<sub>1</sub> received ''h<sub>i</sub>''{{'}}s hat and ''P''<sub>''i''</sub> received ''h''<sub>1</sub>'s hat, effectively putting both out of further consideration. 

For each of the ''n''&nbsp;&minus;&nbsp;1 hats that ''P''<sub>1</sub> may receive, the number of ways that ''P''<sub>2</sub>,&nbsp;...,&nbsp;''P<sub>n</sub>'' may all receive hats is the sum of the counts for the two cases.

This gives us the solution to the hat-check problem: Stated algebraically, the number !''n'' of derangements of an ''n''-element set is
<math display="block">!n = \left( n - 1 \right) \bigl({!\left( n - 1 \right)} + {!\left( n - 2 \right)}\bigr)</math> for <math> n \geq 2</math>,
where <math>!0 = 1</math> and <math>!1 = 0.</math><ref name="EC1">{{cite book|last = Stanley | first = Richard |author-link = Richard P. Stanley | title = Enumerative Combinatorics, volume 1 | edition = 2 | publisher = Cambridge University Press | year = 2012 | isbn = 978-1-107-60262-5| at = Example 2.2.1}}</ref>

The number of derangements of small lengths is given in the table below.
{{clear}}
{| class="wikitable"
|+ The number of derangements of an ''n''-element set {{OEIS|id=A000166}} for small ''n''
|- style="text-align: center;"
! ''n''
| 0 || 1 || 2 || 3 || 4 || 5 || 6 || 7 || 8 || 9 || 10 || 11 || 12 || 13
|-
! !''n''
| 1 || 0 || 1 || 2 || 9 || 44 || 265 || 1,854 || 14,833 || 133,496 || 1,334,961 || 14,684,570 || 176,214,841 || 2,290,792,932
|}

There are various other expressions for {{math|!''n''}}, equivalent to the formula given above.  These include
<math display="block">!n = n! \sum_{i=0}^n \frac{(-1)^i}{i!}</math> for <math> n \geq 0</math>
and
:<math>!n = \left[ \frac{n!}{e} \right] = \left\lfloor\frac{n!}{e}+\frac{1}{2}\right\rfloor</math> for <math>n \geq 1,</math>
where <math>\left[ x\right]</math> is the [[nearest integer function]] and <math>\left\lfloor x \right\rfloor</math> is the [[floor function]].<ref name=Hassani2003>
{{cite journal
 | last = Hassani  | first = Mehdi
 | year = 2003
 | title = Derangements and applications
 | journal = [[Journal of Integer Sequences]]
 | volume = 6  | issue = 1  | at = Article&nbsp;03.1.2  | no-pp=yes
 | bibcode = 2003JIntS...6...12H
 | url = http://www.cs.uwaterloo.ca/journals/JIS/VOL6/Hassani/hassani5.html
 | via = cs.uwaterloo.ca
}}
</ref><ref name=EC1/>

Other related formulas include<ref name=Hassani2003/><ref name=Mathworld-Subfactorial>{{MathWorld|urlname=Subfactorial|title=Subfactorial}}</ref>
<math display="block">!n = \left\lfloor \frac{n!+1}{e} \right\rfloor,\quad\ n \ge 1,</math>
<math display="block">!n = \left\lfloor \left(e + e^{-1}\right)n!\right\rfloor - \lfloor en!\rfloor,\quad n \geq 2,</math>
and
<math display="block">!n = n! - \sum_{i=1}^n {n \choose i} \cdot {!(n - i)},\quad\ n \ge 1.</math>

The following recurrence also holds:<ref name=EC1/>
<math display="block">
 !n = \begin{cases}
    1 & \text{if } n = 0, \\
  n \cdot \left( !(n-1) \right) + (-1)^n & \text{if }n > 0.
\end{cases}</math>

=== 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>