Derangement

This online tool calculates the number of derangements of a set of n elements.

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`