# Derangement

A **derangement** is a permutation with no fixed points. That is, a derangement of a set leaves no element in its original place. For example, the derangements of are and , but is not a derangement of because 2 is a fixed point.

## Contents

## Notation and formula

The number of derangements of an -element set is called the th derangement number or *rencontres number*, or the *subfactorial* of and is sometimes denoted or . (Note that using this notation may require some care, as can potentially mean both and .) This number satisfies the recurrences

and

and is given by the formula

For example, the number derangements of a 3-element set is , which we know to be correct.

The first few derangements, starting from , are

## Proof of Formula

This can be proven using PIE. First, you take , which represents all arrangements of the whole sequence. Then, you must subtract all arrangements in which each element appears in its original location, and now you have . Then, you must add back in permutations in which each set of two elements stay in their original positions, as we subtracted them twice. Now, we have . PIE continues to give us this pattern. We have to alternate between subtracting and adding.

Now, we can change the form of . This is written as . We can now write our relation as . We can factor out and get .

## Limit as n approaches

From the recurrence , we can find that

Also,

## Problems

### Introductory

## See also

*This article is a stub. Help us out by expanding it.*