郑金

一、提出问题

装错信封问题：一个人写了n封不同的信及相应的n个不同的信封，若他把这n封信都装错了信封，那么装错信封的装法共有多少种？这是被著名数学家欧拉称为“组合数论的一个妙题”.

把n个编号元素放在n个编号位置，元素编号与位置编号各不对应的排列方法称为错位排列法.

将编号分别为1，2，3，…，n的n个不同元素a1，a2，a3，…，an，安排在这n个位置作全排列，若某个排列中每个元素都错位，则把这个全排列称为这n个不同元素的一个全错位排列.n个不同元素所有的全错位排列的个数称为全错位排列数，记为Dn，易得D1=0，D2=1，D3=2.

二、递推关系式

对于n=4，D4推导如下：按分步乘法计数原理考虑，第一步，先安排好第一个位置，有C13=3种排法.

1234a3a1第二步，当安排好第一个位置后，假设安排的是a3，此时应考虑a1的位置，包括两种情况.若a1安排在第三个位置，则a2和a4排法是D2=1；若a1不安排在第三个位置，而a2不排在第二个位置，a4不排在第4个位置，对应的排法是D3=2.因此，当第一个位置安排的是a3时，对应的排法共有D2+D3=3，而第一个位置安排的各种情况地位相当，所以D4=C13（D2+D3）=9.

对于Dn，推导如下：

按分步乘法计数原理考虑，第一步，先安排好第一个位置，有C1n-1=n-1种排法.

12…m…nama1第二步，当安排好第一个位置后，假设安排的是am，此时应考虑a1所放的位置，包括两种情况.若a1安排在第m个位置，则对应的排法是Dn-2；若a1不安排在第m个位置，由于a2不排在第二个位置，…，an不排在第n个位置，对应的排法是Dn-1.因此，当第一个位置安排的是an时，对应的排法共有Dn-1+Dn-2.而第一……