5个人的错排问题

Question

数学排列组合问题
5个人写信,每个人写一封,放在桌上排成一排.每个人拿一封,但不能是自己的信,问有多少种不同的拿信方式.【请附过程,感激不尽】

Answer 1

“错排问题”的递推公式是：f(n)=(n-1)*[f(n-1) + f(n-2)]

---证明------------

先排①号球，共有（n-1）种； -- 第1步，后面用乘法原理

再排②号球，分2种情况 -- 后面用加法原理

放入1号盒，则其余(n-2)个球的排列方式就是（n-2）个球的不对位排列，即f(n-2)

如不放入1号盒，则这(n-1)个球的排列方式就是（n-1）个球的不对位排列，即f(n-1)

所以，f(n)=(n-1)*[f(n-1) + f(n-2)]。

--计算-------------------

f(1)=0

f(2)=1

f(3)=2*[f(2)+f(1)]=2

f(4)=3*[f(3)+f(2)]=9

f(5)=4*[f(4)+f(3)]=44

Answer 2

这是错排问题.
d[1]=0
d[2]=1
d[3]=2
d[4]=9
d[5]=44
…………
d[n]=(n-1)*(d[n-1]+d[n-2])