algorithm - 'n' 数字序列的排列

Question

您可以通过多少种方式排列“n”（1 到 n）个数字的序列，使得在其值表示的索引处没有数字出现？

例如

1 can not be at first position
2 can not be at second position
.
.
n can not be at nth position

请给出一个通用的解决方案。也解决它为n = 6。它不是家庭作业。

Answer 1

您需要无定点排列，也称为derangements。它们数量的公式比可能具有固定点的排列数量的公式稍微复杂一些。

Answer 2

令 P(n) 为此类数字排列的n数量。

For 123456....n
Cases are of the form

2*****
3*****
4*****
5*****
.
.
n*****

Now 1 can be anywhere at the rest (n-1) positions.
If 1 is put at the position of the number replacing it...

21****
3*1***
4**1**
.
.
n****1

then first and the replaced numbers are fixed.
Then total cases = (n-1) * P(n-2)

Else if
1 is also restricted not to be at a particular position (positions in above cases)
Then total cases = (n-1) * P(n-1)

所以

P(n) = (P(n-1) + P(n-2)) * (n-1)

P(1) = 0

和 P(2) = 1

Answer 3

n事物round(n!/e)的紊乱（无定点排列）的数量e是自然对数的底。这里round的意思是最接近的整数函数。这在Wikipedia 文章中进行了描述，但其方式可以得到澄清。

对于n = 6一个容易计算有round(264.87...) = 265混乱。

实际上，您已经从 MathSE 提出了一个常见问题。