错排问题的模型解释及求解

吴如光

(江苏省南京航空航天大学附属高级中学 210000)

一、错排问题

错排问题，又称更列问题，是组合数学中的经典问题之一.该问题有许多具体的形式，例如：①在写信时将n封信装到n个不同的信封里，有多少种全部装错信封的情况？②n个人各写一张贺卡相互赠送，有多少种赠送方法？从中概括出其数学模型：一个有n个元素的排列，若这个排列中所有的元素都不在自己原来的位置上，那么这样的排列就称为原排列的一个错排，n个元素的错排数记为Dn，求Dn的通项公式.

二、容斥原理解释

容斥原理：设A1,A2，…，An为有限集合，用|Ai|表示集合Ai中的元素个数，则有：

以装信封为例：记第i封信装对的事件为Ai(i=1,2…,n).

不难得出：|Ai|=(n-1)!,|Ai∩Aj|=(n-2)!,…,|A1∩A2∩…An|=1.

三、按分步计数原理解释

第1步：将1号信错放，有n-1种放法，不妨假设放在2号信封里；

第2步：将2号信错放，有两类放法：

①：2号信放入1号信封里，则其余n-2封信与信封将错放，有Dn-2种放法.

②：若2号信不放在1号信封里，此时相当于n-1封信(除1号信)放入n-1个信封(除2号信封)，每封信都有一个禁止放的信封，因此有Dn-1种放法.

由此可得递推关系：D1=0,D2=1,Dn=(n-1)·(Dn-1+Dn-2),n≥3.

∴Dn-n·Dn-1=-[Dn-1-(n-1)·Dn-2]，

∴Dn-n·Dn-1=(-1)n,(n≥2),

四、按分类计数原理解释

只需令引理中的an=n!，bn=Dn.

由引理可得：

以上对错排问题的几种不同看法，得到了不同的递推关系，但是殊途同归，加深了对错排问题的理解，其结论的形式优美，让我们再次感受到数学的美妙.