WOLFRAM|DEMONSTRATIONS PROJECT

Derangement Diagrams

​
number of points n
3
derangement
1
A derangement is a permutation that leaves no element in its original position. For example, (1234) shifts every element over (cyclically), so it is a derangement, but (124) leaves 3 fixed in place, so it is not a derangement. The number of derangements on a set of
n
elements is called the subfactorial of
n
(with notation
!n
), given by the formula
!n=n!
1
0!
-
1
1!
+
1
2!
-
1
3!
+
1
4!
+⋯+
n
(-1)
n!
, which is highly reminiscent of
1
e
=
1
2!
-
1
3!
+
1
4!
-
1
5!
+⋯
. The sequence of subfactorials is
!n=0,1,2,9,44,265,1854,…
, for
n=1,2,…
.