AoPSWiki
Do you have what it takes to be the next brilliant trader, researcher, or developer at Jane Street Capital? Find out in the Careers in Mathematics Forum.
Personal tools

Derangement

From AoPSWiki

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 \{1,2,3\} are \{2, 3, 1\} and \{3, 1, 2\}, but \{3,2, 1\} is not a derangement of \{1,2,3\} because 2 is a fixed point.

Contents

Notation and formula

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

!n = n \cdot !(n - 1) + (-1)^n

and

!n = (n - 1)\cdot (!(n - 1) + !(n - 2))

and is given by the formula

!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.

For example, the number derangements of a 3-element set is 3! \cdot \sum_{k = 0}^3 \frac{(-1)^k}{k!} = 6\cdot\left(\frac{1}{1} - \frac{1}{1} + \frac{1}{2} - \frac{1}{6}\right) = 2, which we know to be correct.

The first few derangements, starting from n=0, are 1, 0, 1, 2, 9, 44, 265, 1854, 14833, 133496, 1334961, 14684570, \ldots.

Limit as n approaches ∞

From the recurrence !n=n\cdot!(n-1)+(-1)^{n}, we can find that \lim_{n\to\infty}\frac{!n}{n!} =\frac{1}{e} \approx 0.3679\ldots.

Also, !n = \left\lfloor\frac{n!}{e}+\frac{1}{2}\right\rfloor.

Problems

Introductory

See also

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

Retrieved from "http://www.artofproblemsolving.com/Wiki/index.php/Derangement"
Want to learn how to tackle those tough MATHCOUNTS and AMC counting and probability problems? Check out Art of Problem Solving's Introduction to Counting & Probability by David Patrick.
© Copyright 2008 AoPS Incorporated. All Rights Reserved. • Foundation • Privacy • Contact Us