Derangement diagrams

_____________________________________
Back to Robert's Math Figures
_____________________________________
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(n - 1))

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 ]

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.

[Privacy Policy] [Terms of Use]

_____________________________________
Home || The Math Library || Quick Reference || Search || Help 
_____________________________________

© 1994-2014 Drexel University. All rights reserved.
http://mathforum.org/
The Math Forum is a research and educational enterprise of the Drexel University School of Education.The Math Forum is a research and educational enterprise of the Drexel University School of Education.

Copyright © 1996/7 Robert M. Dickau