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:
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
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.