Derangement
Definition of a derangement
In combinatorics, a derangement of a set of elements is a permutation such that no element remains in its original place. It is said 'a permutation without a fixed point'.
The number of derangements of a set of n elements is equal to the subfactorial of n (denoted by !n).
\(D_n = !n = n!\,\sum_{i=0}^n \dfrac{(-1)^i}{i!}\)
Derangement exemple
In a dance class there are 4 pairs of dancers. The teacher proposes that all dancers must change their partners for the next song. Calculate the number of possible configurations.
Answer: This is a permutation without a fixed point because no dancer should meet his initial partner. This is a derangement with n = 4.
Answer: \(D_4 =\, !4 = 4!\,\sum_{i=0}^4 \dfrac{(-1)^i}{i!} = 9\)
Derangement : a Table of first values
\(D_0 = 1\)
\(D_1 = 0\)
\(D_2 = 1\)
\(D_3 = 2\)
\(D_4 = 9\)
\(D_5 = 44\)
\(D_6 = 265\)
\(D_7 = 1854\)
\(D_8 = 14833\)
\(D_9 = 133496\)
`D_10 = 1334961`
`D_11 = 14684570`
D_12 = 176214841`
`D_13 = 2290792932`
`D_14 = 32071101049`
`D_15 = 481066515734`
`D_16 = 7697064251745`
`D_17 = 130850092279664`
`D_18 = 2355301661033953`
`D_19 = 44750731559645106`
`D_20 = 895014631192902121`
See also
Permutation
Arrangement
Combination