1
$\begingroup$

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

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

  • 3
    http://en.wikipedia.org/wiki/Derangement The article does a pretty good job of describing what I mean by a derangement.2012-09-28

2 Answers 2

1

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.

1

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