怎样计算一个排列重新排列后每个人都不在原来位置上的种类数

最近遇到一个问题。几个人在原位置，现在需要换位，要求是每个人在换位后都不在原位。

题目言简意赅，好像不是很难。但是仔细想想，觉得还真是棘手的。

听同学说这个问题在高考中只会涉及到 5 个人排列，答案似乎是 44 种排列方式。但是我偏偏要求 n 个人时的种类数。结果在我的不懈研究下，终于……

终于还是没有研究出来，但是我谷歌了一下，发现了一些做法。不过他们好像说得不清不楚，所以我也来凑凑热闹。

排列组合求解部分

这是一个递推的方法。首先，我们设 a_n 为有 n 个人重新排列后位置不在原位的种类数。显然我们有：

a₁ = 0
a₂ = 1

然后呢？我们看看有 n 个人的时候会有什么奇妙的事情发生。

第一步，我们先取 n 个人中的第一个，显然她不可以站在第一号位。但是她站 2~n 号位都行，这样她可以站的位置种类数就有 (n-1) 种。即如下：

1 2 3 4 ... i ... n  <--  这行数字表示第 n 号位
===================
? 1 ? ? ... ? ... ?
? ? 1 ? ... ? ... ?
? ? ? 1 ... ? ... ?
? ? ? ? ... 1 ... ?
? ? ? ? ... ? ... 1

第二步，我们考虑那个 1 站在了第 i 号位置的情况，因为每种其它的情况和那个 1 站在了第 i 号位置的情况其实是相同的。好，当 1 号站在了 i 号位，那么原来的 i 号将会在新的地方安家。

第一种情况，当 i 的新家刚好在 1 号位置上，通俗地说也就是 i 号与 1 号换了个位置，那么，这两个人都已经满足了题目中不能在原位的要求。并且 i 号与 1 号是换位，并没有影响别人的位置。所以这种情况下，其他 (n-2) 个人可以在剩余的 (n-2) 个位置上换位，就转化成了 (n-2) 个人换位的问题——这样的种类数其实刚好是 a_n-2.

第二种情况，是当 i 的新家在除了 1 号位和 i 号位的其它位置上时的情况。这种情况比较复杂。由于第 i 号位已经被 1 所占，那么我们不妨首先无视掉 i 号位和 1 号，考虑剩下的东东。此时：

1 2 3 4 ... (i-1) (i+1) ... n
=============================
? ? ? ? ...   ?     ?   ... ?

这种情况约定，i 号不能在 1 号位上，而其余的号不能在原位上。然后我们再想想，第 i 号位不是被我们移除了吗？（请注意反问语气。）所以 i 号的放置限制，仅仅是不能放在 1 号位上。然后，我们不妨把 i 看成是 1, 这样，这个 1 不可以放在 1 号位上，但可以放在其它的位置上，所以仍旧符合题意。这样一来，问题就转化成了 (n-1) 个人的换位问题——这样的种类数其实刚好是 a_n-1.

综上，我们第一步得到的种类数是 (n-1), 第二步中讨论了两种类型的情况，第一种情况得到的种类数是 a_n-2, 第二种情况得到的种类数是 a_n-1, 所以根据分类和分步计数原理，总的种类数是：

a_n = (n-1)(a_n-2+a_n-1)

真爽！接下来的事情就是对付这个递推数列了。

数列通项的推导

其实以上排列组合的过程是问题的难点，思路是我从网上找到的。递推数列的解倒不是很难，是我自己写的。

首先我们写出两个项来：

a_n+1 = n(a_n-1 + a_n) ①
a_n = (n-1)(a_n-2 + a_n-1) ②

然后，我们把①中的 a_n 用②代换，化简得到：

a_n+1 = n²a_n-1+n(n-1) a_n-2 ③

由③=①得：

na_n-1 + (n-1) a_n-2 = a_n-1 + a_n

整理得：

(n-1) a_n-2 – a_n-1 = – (na_n-1 – a_n)

不妨设 b_n = na_n-1 – a_n, 上式即：

b_n-1 = - b_n

因此可知，b_n 是一个以 -1 为公比的等比数列：

b_n = (-1)ⁿ⁺¹, n>1

据设，得：

a_n = na_n-1 + (-1)ⁿ

然后，我们算上一组（请注意 a₁ = 0）：

a₂ = 2a₁ + 1 = 1

a₃ = 3a₂ - 1 = 3 x 1 – 1

a₄ = 4a₃ + 1 = 4 x ( 3 x 1 – 1 ) + 1 = 4 x 3 – 4 + 1

a₅ = 5a₄ - 1 = 5 x ( 4 x 3 – 4 + 1 ) – 1 = 5 x 4 x 3 – 5 x 4 + 5 – 1

…

[latex size=2]a_n=n!(\frac{1}{2!}-\frac{1}{3!}+\frac{1}{4!}-\ldots \frac{1}{n!})[/latex]

或者为了便于记忆，你可以记住这种形式：

[latex size=1]a_n=A_n^n-A_n^{n-1}+A_n^{n-2}-\ldots A_n^0[/latex]