查到一种递归的思想！！！ 设长度为n的序列的全错位排列一共有f(n)种，假设我们已经解决了f(1)到f(n-1)，那么当序列新增了一个元素an，显然全错位排列中该元素不能放在第n个位置上，假设该元素在从1到n-1的第i个位置，那么在新序列中第n个位置上的元素可能有两种情况： 第n个位置上的元素为ai  因为an和ai都不在原位置上，因此只需剩余的元素都是全错位排列，新序列就构成了全错位排列。那么除去ai和an还剩下n-2个元素，则这n-2个元素一共有f(n-2)种全错位排列，因为i的选择共有n-1种，因此该情况下一共有(n-1)*f(n-2)种全错位排列。 第n个位置上的元素不为ai  该种情况相当于，前n-1个元素做好了全错位排列，an与其中任意元素交换位置，新生成的序列也是一个全错位排列。这种情况下i的选择共有n-1种，n-1的元素的全错位排列共有f(n-1)种，因此该情况下一共有(n-1)*f(n-1)种全错位排列。 综合以上两种情况，f(n)=(n-1)f(n-2)+(n-1)*f(n-1)=(n-1)[f(n-2)+f(n-1)]  显然这个公式适用于n>2的情况，而f(1)=0,f(2)=1是之前已经列举得出的。  将n=3代入，得到f(3)=2*(0+1)=2，将n=4代入，得到f(4)=3*(1+2)=9，与列举所得到的结果相同。