A derangement (or complete permutation) of a set is a permutation that leaves no element in its original position. The number of derangements of a set with n elements can be computed recursively using this formula:
Using the principle of inclusion and exclusion, we also get:
Here are some diagrams that represent the derangements of sets with n elements.
3 elements, 2 derangements:
4 elements, 9 derangements:
5 elements, 44 derangements:
6 elements, 265 derangements:
(Diagram is several dozen kilobytes, so let me know if you're really intent on seeing it.)
Derangement formulas from Fred S. Roberts, Applied Combinatorics, Prentice-Hall, 1984.
Designed and rendered on a Saturday using Mathematica 3.0 for the Apple Macintosh.
Home || The Math Library || Quick Reference || Search || Help