Take the 2-minute tour ×

How to find all the derangements of [n]. Specifically,if n is 4?

What is the process to get all the derangments in general?

share|improve this question
Sorry, what do you mean by 'derangement'? Give an example. –  Berci Sep 28 '12 at 9:40
en.wikipedia.org/wiki/Derangement The article does a pretty good job of describing what I mean by a derangement. –  user1210233 Sep 28 '12 at 9:43

2 Answers 2

A braindead method would be to list all the permutations of $[n]$ and then remove the ones with fixed points. You can list all the permutations of $[n]$ by listing them in lexicographic order, for example.

Another method is as follows. The elements of $S_n$ with no fixed points are precisely those permutations which contain no $1$-cycles when written as a product of disjoint cycles. For $n=4$ these permutations must have cycle type $(2,2)$ or $(4)$, i.e. they look like $(\,\cdot\ \cdot\,)(\,\cdot\ \cdot\,)$ or $(\,{\cdot}\ {\cdot}\ {\cdot}\ {\cdot}\,)$. They're easy enough to find; then apply each of these to your set.

share|improve this answer

A general method is described in Gray code for derangements by Jean-Luc Baril and Vincent Vajnovszki, Discrete Applied Mathematics $140$ ($2004$) $207$–$221$.

share|improve this answer

Your Answer


