For the traditional classic problem of derangement (https://en.wikipedia.org/wiki/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.
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$.