Question

一道排列组合题

1、2、3、4、5 五个数字分别对应1、2、3、4、5 五个空格，要求每个数字不能填在自己的空格内，问一共有多少种情况？

Answer 1

解：
把这个问题一般化。设有n(正整数）个数字（或字母），分别对应n个空格。求每个数字不能填在自己的空格内的总的种数。

设总的种数为f(n)
可以证明下面的递推公式成立
f(n)=(n-1)[f(n-1)+f(n-2)]

(简述如下：它的思路是，我们去考虑比如1在第3个空格时，把所有的种数分成两种类型来计算，第一种3在第1个空格内，此时它对应的种数为f(n-2)；第二种3不在第1个空格内,此时它对应的种数为f(n-1)。而我们又知道，比如1，它是有n-1个选择的。）

易知，f(1)=0,f(2)=1
从而f(3)=2,f(4)=9,f(5)=44(这就是你要求的）
另有f(6)=265,f(7)=1854,f(8)=14833,…

且还可证得一个公式
f(n)=nf(n-1)+(-1)^n

还有
f(2n)=(2n)![1/2!-3/4!-5/6!-…-(2n-1)/(2n)!]
f(2n+1)=(2n+1)![0/1!+2/3!+4/5!+…+(2n)/(2n+1)!]

以上都是我自己的结果。做于1999年5月16日。
后来在书《国际数学奥林匹克（IMO）思想方法》（殷启正 陈志友 著）上见到了这个问题。知道这个问题曾被数学家贝努利研究过，被数学家欧拉称为组合中的一个妙题。

下面的公式是从书上摘的
f(n)=n![1-1/1!+1/2!-1/3!+1/4!-…+(-1)^k/k!+…+(-1)^n/n!]
最后说明一点，上面公式里，中括号里面的部分，当n趋向于无穷大时，它的极限是自然对数的底的倒数，即1/e.

Answer 2

44种情况