Derangements

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:

D(n + 1) = n (D(n) + D(n1))

Using the principle of inclusion and exclusion, we also get:

D(n) = n! (1/2! - 1/3! + ... + ((-1)^n)/n!)

Here are some diagrams that represent the derangements of sets with n elements.

3 elements, 2 derangements:

231 312

4 elements, 9 derangements:

2143 2341 2413 3142 3412 3421 4123 4312 4321

5 elements, 44 derangements:

[ derangement 5 ]

Derangement formulas from Fred S. Roberts, Applied Combinatorics, Prentice-Hall, 1984.

Designed and rendered on various weekends using Mathematica versions 3.0, 6.0, and 7.0.

Copyright © 1996–2017 by Robert Dickau.

[ home ] || [ 2010-12-24 ]


www.robertdickau.com/derangements.html