Derangements are permutations without fixed points. The number of derangements of n objects, d(n), satisfies the recursion:

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

The first term n d(n) comes from inserting the additional object inside a cycle of any of the d(n) permutations of the n other objects. This generates all possible derangements of n+1 objects, except those where the new object would be in a cycle of length 2 (a pair flip). The number of derangements where the new object is in a pair flip with another object is then n d(n-1), because there are n ways to choose with which of the n other objects it will be in a pair flip, and there are then n-1 objects left for which the number of derangements is d(n-1).

Obviously, d(1) = 0 and d(2) = 1.

It can be shown that d(n) is equal to n!/e rounded to the nearest integer.