For the traditional classic problem of derangement (), there is a formula $n! = (n-1)(!(n-1)+!(n-2))$, which calculates current results based on previous iteration in a recursive way.
The question here is whether we have another way to calculate this directly, and whether it is correct. Here is how I calculate it. I appreciate comments.
- The first person has $n-1$ choices, suppose the first person select the 2nd person (any person is fine, just an example);
- The 2nd person has $n-1$ choices, since that no. 2 is already selected, suppose the 2nd person selects the 3rd person;
- The 3rd person has $n-2$ choices, since hat no.3 is already selected,
- And so on...
So the result is $(n-1) \cdot (n-1) \cdot (n-2) \cdot (n-3) \cdot \ldots \cdot 2 \cdot 1$. Is that correct? Thanks.
Quote for the problem mentioned,
Suppose that there are $n$ persons who are numbered $1, 2, \dots, n$. Let there be $n$ hats also numbered $1, 2, \dots, n$. We have to find the number of ways in which no one gets the hat having same number as their number.
Regards, Lin.
$\endgroup$ 251 Answer
$\begingroup$As Andre Nicolas mentioned in the comments, your proposed formula is incorrect.
Let $D_n$ denote the number of derangements of a sequence with length $n$.
Since you gave a formula for positive $n$, let's compare your formula with $D_n$ for small positive $n$.
$D_1 = 0$ since every element in the sequence $\{1\}$ is a fixed point, that is, it is in its proper position. Your formula gives $1 - 1 = 0$, which is correct.
$D_2 = 1$ since the only derangement of the sequence $\{1, 2\}$ is the sequence $\{2, 1\}$. Your formula gives $(2 - 1)(2 - 1) = 1$, which is also correct.
$D_3 = 2$. To see this, we list the permutations of the sequence. The numbers shown in red are fixed points. \begin{align*} &\{\color{red}{1}, \color{red}{2}, \color{red}{3}\}\\ &\{\color{red}{1}, 3, 2\}\\ &\{2,1,\color{red}{3}\}\\ &\{2,3,1\}\\ &\{3,1,2\}\\ &\{3,\color{red}{2},1\} \end{align*} Since a derangement contains no fixed points, the only derangements of the sequence $\{1, 2, 3\}$ are $\{2, 3, 1\}$ and $\{3, 1, 2\}$. Your formula gives $(3 - 1)(3 - 1)(3 - 2) = 4$, which is incorrect.
What went wrong?
We cannot place $1$ in the first position, so it must be placed in either the second position or the third position.
If $1$ is placed in the second position, then $2$ must be placed in the third position, for otherwise we obtain the sequence $\{2,1,\color{red}{3}\}$, which is not a derangement since $3$ is a fixed point, contrary to your assumption that we have two choices for where we place $2$.
If $1$ is placed in the third position, then $3$ must be placed in the second position, for otherwise we obtain the sequence $\{3, \color{red}{2}, 1\}$, which is not a derangement since $2$ is a fixed point, contrary to your assumption that we have two choices for where we place $3$.
$\endgroup$ 2
