2
$\begingroup$

Given a finite set $S$ with $|S|= n$, what is the number of permutations $\sigma$ such that

$$\sigma(i) \not= i, \forall i \in S $$

That is, permutations where every element is interchanged with another element. (The permutations which can be described as one cycle containing exactly $n$ elements?)

My naive failed attempt at a solution:

$|S|= n$, consider the first element. We have $n-1$ places to put it. Considering the second element the number of choices depends on where we put the first element. I reckon it's either $n-1$ or $n-2$. And the problem continues since the next choice depends on the previous one. I'm Lost.

$\endgroup$
2
$\begingroup$

This question is about the number of permutations with 0 fixed points (i.e. derangements), which is given by $D_{n,0}=n!\sum_{k=0}^n \frac{(-1)^k}{k!}$. See Wikipedia for a combinatorial proof. More generally, the number of permutations with $k$ fixed points is given by rencontres numbers.


Regarding your question in parentheses: This is not the same as the number of permutations with exactly one cycle of length $n$. For example, the permutation $(1 2 3 4) \to (2 1 4 3)$ has two cycles, $(12)$ and $(34)$, but no fixed points. The number of permutations with one cycle is $(n-1)!$ (the cycle notation of the permutation can be started with a fixed number, say $1$, after which the remaining $n-1$ numbers can be placed in any order).

$\endgroup$
  • 1
    $\begingroup$ Many thanks! I didn't know about rencontres numbers, interesting, I shall immediately read up on this. Thanks again! $\endgroup$ – John Smith Oct 3 '13 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.