[Information Index] [Generation Index] [COS homepage]

Information on Derangements

A derangement of the integers [n]={1,2,...,n} is a permutation of [n] such that no element is in its natural position. That is, pi is not equal to i for any i. In cycle notation, a derangement is a permutation of [n] which does not contain any 1-cycles. All 9 derangements for n=4 are shown in the table below.

One-Line notation
 Cycle notation
2 3 4 1
(1234)
4 3 1 2
(1423)
3 1 4 2
(1342)
3 4 2 1
(1324)
2 4 1 3
(1243)
4 1 2 3
(1432)
2 1 4 3
(12)(34)
4 3 2 1
(14)(23)
3 4 1 2
(13)(24)

The number of derangements of length n, d(n) can be computed using the following well-known recurrence relation, n > 2:

d(n) = (n-1) d(n-1) + (n-1) d(n-2)

The algorithm used by COS to generate derangements is based on this recurrence relation and is from the paper: U. Taylor and F. Ruskey, Fast Generation of Restricted Classes of Permutations, Manuscript 1995.

The recurrence relation above can be manipulated so that it takes on the form

d(n) = n d(n-1) + (-1)n

The d(n) numbers are sometimes called the subfactorial or recontres numbers. The values of d(n) for n=0,1,2,...,10 are 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961. This is sequence A000166(M1937) in Neil J. Sloane's database of integer sequences.

Programs available:
[Information Index] [Generation Index] [COS homepage]
Questions?? Email The wizard of COS.
(Please note that the suffix XXXX must be removed from the preceeding email address.)
It was last updated Wednesday, 10-May-2006 10:32:14 PDT.
There have been 4778 visitors to this page since May 16, 2000 .
©Frank Ruskey, 1995-2003.