装错信封问题.docVIP

装错信封问题

我们在学习排列组合问题时经常会遇到一些很有意思的问题，在此举一例，希望借助此例，学会自己解决问题，并对问题进行深入的探索。

1．问题的提出

1〕同室四人各写一张贺年卡，先集中起来，然后每人从中拿一张别人送出的贺年卡，那么四张贺年卡的不同分配方式有〔〕

〔A〕6种〔B〕9种〔C〕11种〔D〕23种

2〕有5个客人参加宴会，他们把帽子放在衣帽寄放室内，宴会结束后每人戴了一顶帽子回家，回家后，他们的妻子都发现他们戴了别人的帽子。问5个客人都不戴自己帽子的戴法有多少种？

上述两个问题，实质上是完全一样的。是被著名数学家欧拉〔LeonhardEuler，1707—1783〕称为“组合数论的一个妙题”的“装错信封问题”的两个特例。“装错信封问题”是由当时最有名的数学家约翰·伯努利〔JohannBernoulli，1667—1748〕的儿子丹尼尔·伯努利〔DanidBernoulli，1700—1782〕提出来的，大意如下：一个人写了封信都装错了信封，问都装错信封的装法有多少种？

2．建立数学模型

“装错信封问题”及两个特例，其实就是个不同元素的一类特殊排列问题，本文试就给出这类问题的数学模型及求解公式，为方便，我们先把个不同的元素及相应的位置都编上序号1，2，…，，并且约定：在个不同元素的排列中

1°假设编号为的元素排在第个位置，那么称元素在原位；否那么称元素不在原位。

2°假设所有的元素都不在原位，那么称这种排列为个不同元素的一个错排〔假设每个元素都在原位那么称为序排〕。

按照上面约定，“装错信封问题”即为个不同元素的错排问题，那么可构建“装错信封问题”的数学模型为

在个不同元素的全排列中，有多少种不同的错排？

3．模型求解

应用集合中的容斥原理，我们就可得到“装错信封问题”的数学模型的求解公式。

设表示个不同元素的全排列的集合

为元素在原位的排列的集合。

〔1≤＜≤＝为元素与在原位的排列的集合。

……

〔1≤＜＜…＜≤，＝1，2，…，＝为元素，，…，均在原位的排列的集合。

……

为个元素的序排的集合。

那么它们的排列数〔即各个集合中元素的个数〕分别为

=〔〕！

……

……

又因为集合有种，有种，…，有种，…，有种。

所以，根据容斥原理即得“装错信封问题”的数学模型的求解公式〔即个不同元素的错排数〕为

记为eq\o\ac(○,*)

4应用举例

一个元素的错排数显然为0，二个不同元素的错排数为1，三个不同元素的错排数为2，均可由公式eq\o\ac(○,*)验证，由公式eq\o\ac(○,*)还可求得四个不同元素的错排数为

4！·〔〕=9，

五个不同元素的错排数为

，

那么本文开头的问题1〕共有9种不同的分配方式，应选〔B〕。问题2〕共有44种不同的戴法，下面再举几例说明公式eq\o\ac(○,*)的应用。

例1设有编号为1，2，3，4，5的五个球和编号为1，2，3，4，5的五个盒子，现将这五个球投放入五个盒内，要求每个盒内投放一个球，并且恰好有两个球的编号与盒子的编号相同，那么这样的投放方法的总数为〔〕

〔A〕20种〔B〕30种〔C〕60种〔D〕120种

解此题实质上是三个元素的错排问题，但由于题中未指明是哪三个元素进行的错排，故此题可分两步求解。

第一步，先选出三个被错排的元素，有种。

第二步，对已选出的三个元素进行错排，有2种。

所以，根据乘法原理可得投放方法总数为·2=20种，应选〔A〕

例2某省决定对所辖8个城市的常政一把手进行任职交流，要求把每个干部都调到另一个城市去担任相应的职务，问共有多少种不同的干部调配方案？

解实质上此题即为8个不同元素的错排问题，一种干部调配方法对应于8个不同元素的一个错排，故由公式eq\o\ac(○,*)可求得不同的干部调配方案数为

〔种〕