维普资讯 http://www.cqvip.com 第２５卷第３期 ２００５年９月 数学理论与应用 ＭＡＴＨＥＭＡＴＩＣＡＬ ＴＨＥＯＲＹ ＡＮＤ ＡＰＰＬＩＣＡＴＩＯＮＳ Ｖｏ１．２５ Ｎｏ．３ Ｓｅｐ．２００５ “装错信封问题’’数学模型的求解及推广 郑 翔 （浙江丽水职业技术学院，丽水，３２３０００） 摘 要 本文给出了全错位排列问题数学模型的通解，全错位排列推广问题的通解 关键词 排列 全错位排列 数学模型 Ｔｈｅ Ｅｘｐａｎｄｉｎｇ Ａｎｄ Ｓｏｌｕｔｉｏｎ Ｏｎ Ｔｈｅ Ｍａｔｈｅｍａｔｉｃａｌ Ｍｏｄｅｌ ｏｆ Ｐｅｒｍｕｔａｔｉｏｎ ｆｏｒ Ｅｒｒｏｒ ＰｏｓｉｔｉｏｎＮｕｍｂｅｒｓ Ｚｈｅｎｇ Ｘｉａｎｇ （Ｌｉ Ｓｈｕｉ Ｔｅｃｈｎｉｃａｌ Ｃｏｌｌｅｇｅ，ＬｉＳｈｕｉ．３２３０００） Ａｂｓｔｒａｃｔ Ｔｈｉｓ ｐａｐｅｒ ｄｉｓｃｕｓｓ ｔｈｅ ｇｅｎｅｒａｌ ｓｏｌｕｔｉｏｎ ｏｆ ｐｅｒｍｕｔａｔｉｏｎ ｆｏｒ ｅｒｒｏｒ ｐｏｓｉｔｉｏｎ ｎｕｍｂｅｒｓ ａｎｄ ｅｘｐａｎｄ ｏｎ ｔｈｅ ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌ ｏｆ ｍｉｓｔａｋｅ ｉｎ ｆｉｌｌｉｎｇ ｅｎｖｅｌｏｐｅ． Ｋｅｙｗｏｒｄｓ ｐｅｒｍｕｔａｔｉｏｎ ｅｒｒｏｒ ｐｏｓｉｔｉｏｎ ｎｕｍｂｅｒｓ ｍａｔｈｅｍａｔｉｃａｌ ｍｏｄｅｌ １ 问题提出 （１）某省决定对所辖８个城市的党政一把手进行任职交流，要求把每个干部都调到另一个 城市去担任相应的职务，问共有多少种不同的干部调配方案？ （２）有５个客人参加宴会，他们把衣帽寄放在室内，宴会后每人戴了一顶帽子回家，回家 后，他们的妻子都发现他们戴了别人的帽子，问６个客人都不戴自己帽子的戴法有多少种？ 上述两个问题，实质上是完全一样的，被著名数学家欧拉（Ｌｅｎｈａｒｄ Ｅｕｌｅｒ，１７０７—１７８３）称 为“组合数学论”的一个妙题的“装错信封问题”的两个特例．“装错信封问题”是由当时最有名 的数学家约翰·伯努利（Ｊｏｈａｎｎ Ｂｅｒｎｏｕｌｌｉ，１６６７—１７４８）的儿子丹尼尔·伯努利（Ｄａｎｉｄ Ｂｅｒｎｏｕｌｌｉ，１７ＯＯ一１７８２）提出来的，大意如下：一个人写了几封不同的信及相应的ｎ个不同的信 封，他把这 封信都装错了信封．问都装错了信封的装法有几种？ ２建立数学模型 “装错信封问题”及两个特例，其实就是 个不同元素的一类特殊排列问题，本文试就给出 这类问题的数学模型及求解公式，并对这类问题的数学模型进一步的推广．为说明方便，我们 武俊德教授推荐 收稿日期：２００５年３月１０日 维普资讯 http://www.cqvip.com 第３期 “装错信封问题 数学模型的求解及推广 ９５ 先把 个不同的元素及相应的位置都标上序号１，２，３，… ，并且约定：在 个不同元素的排列 中： （１）若编号为ａｉ（ 一１，２，３，… ）的元素排在第 个位置，则称元素 在原位，否则称元素ｎ。 不在原位． （２）若所有的元素都不在原位，则称这种排列为 个不同元素的一个全错位排列（若每个 元素都在原位则称为序排） 按照上面的约定“装错信封问题”的数学模型为：在ｎ个不同元素的全排列中，共有多少种 不同的错排？（即全错位排列问题） ３ 数学模型求解 当 一１时，这时位置只有一个，而该元素不能排在该位置，所以，这种排法只有０种，即 Ｄ１—０． 当 一２时，这时ｎ。不能排在第一个位置，ｎ 不能排在第二个位置的排法只有１种（即ｎ 排在第二个位置，ｎ 排在第一个位置）．故Ｄ 一１． 当 ３时，设日。（ 一１，２，… ）不排在第ｉ（ｉ一１，２，… ）位分别填人下面的 个方框中 第一步 考虑第１个位置，Ｏａ。不能排在第一个位置 ．第１个位置的排法共有（ 一１） 种，下面假定日 （２ ）排在第１个位置． 第二步 考虑第ｉ个位置，根据第 个位置是否排ｎ 可分成两种情况： （１）当ｎ。排在第 个位置（此时ｎ 已排在第１个位置），则还剩下（ 一２）个元素和与之对 应的（ 一２）个位置，则问题变为（ 一２）个元素的错位排列，因此不同的排法有Ｄ 一 种． （２）当ｎ。不排在第 个位置（此时ｎ。仍排在第１个位置），因为ｎ 和ｎ。均不能排在第 个 位置，所以，当日 排在第１个位置后，剩下的（ 一１）个人：日。，日：，ｔ２ ３ ｏ ｏ ｏ日 ，日…，…日 和（ 一１） 个位置：２，３，…， ，其中日 （七一２，３，…， 一１， ＋１，… ）不排在第ｋ位，日。不排在第 位．故此 时也相当于（ 一１）个元素的错位排列，则不同的排法是Ｄ 一。种． 由乘法和加法原理知： Ｄ 一（ 一１）（Ｄ 一ｌ＋Ｄ 一２） （１） 其中Ｄ。一０，Ｄ 一１． 下面用递归迭代法得出Ｄ 的计算公式． 由（１）得： 即 ＋ · （一 ） 一２· · · · １ Ｄ ｚＤ１） ＯＤ：０，Ｄ２—１， ｃ · 即 Ｄ 一ｎＤ 一ｌ一（一１）” Ｄ 一舢＋毒 ） 维普资讯 http://www.cqvip.com ９６ 数学理论与应用 第２５卷 即在 个不同元素的全排列中，错排数为： 其中 且 ～ｍ＋耋 一 一 一 州 ４“装错信封问题”数学模型的推广 上面我们讨论了 个元素的全错位排列问题．如果我们换一个角度来看，把 个元素看成 一～ ２ １ 组人，则为每一组只有１人的全错位排列．为此，我们自然会想到每组有２人、３人甚至 个人 ＝ 一 时的情况又会如何呢？为此我们将此模型进一步推广：Ｄ ｌ－．一¨ ＋ 推广１＋ ｋｎ个人，每组ｋ个人，共 组，坐到 行ｋ列共 一 个位置中，但若第 （ 一１，２，以， ｋ）组不能坐到第ｉ（ｉ一１，２，Ａ，ｋ）行中（组内成员可换位置）．问：共有几种不同的坐法？一 为了解决这类问题，我们再来给出定理１ 一引 定理１ ｋｎ个人，每组ｋ个人，共 组，坐到 行ｋ列共 ，＋ ２个位置，但若第 （ 一１，２，Ａ，ｋ） 组不能坐到第 （¨ 一１．，２．以，矗）行中（组内成员可换位置）．不同的坐法有： ＋ ａｈ—Ｐ：（ 一１）（口 一１）＋Ｎａ 一２）， 其中 ｎ 。一０，一 ａｋｚ一（ ） 且ｎｈ—Ｄ ·（户：） ，（Ｄ 为 个元素的错排列数） 证明 当 一１时，‘；＾、 ．‘第一组成员不能坐在第一行中，．‘．ａ 一０ 当 一２时，’一引 ．．第１线人坐到第２组位置构成全排，第２组人坐到第１组位置又构成全排， ａ 一（户：） 种． 当 三三＝３时，首先考虑第１行的位置，可能坐此位置的人共有（ 一１）组，但无论哪一组人 坐，不同的坐法有户：（ 一１）种．下面假定第１行被第ｉ组坐了．接着，再考虑第 行，同样可分 两种情况讨论： （１）若第 行被第１组坐了（此时第１行被第ｉ组人坐了），此时还剩下（ 一２）组人和与之 对应的（”～２）组位置，则共有户如 一 种不同的坐法． （２）若第 行不被第１组人坐（此时第１行仍被第 组人坐），则剩下（ 一１）组人和（ 一１） 组位置，则不同的坐法共有ｎ 种． 再由乘法和加法原理： ｄ —Ｐ：（６—１）（ｄ （ 一１）＋户：ｎＩ（ 一２）） 从上面这个通项公式中我们可以看出ｋ—ｌ时正好是错位排列的通解． 推广２矗 个人，每组ｋ个人，共ｒｌ组，坐到 行ｋ列共矗 个位置中，但若第ｉ（ 一１，２Ａｋ） 组不能坐到第 （ 一１，２Ａｋ）行中（组内成员可换位置）．但每组内第Ｊ人不能坐到第 列． 问：共有几种不同的坐法： 为了解决这些问题，我们再来给出定理２． 定理２矗 个人，每组ｋ个人，共，２组，坐到 行ｋ列共 五个位置中，但若第 （ 一１，２Ａｋ） 组不能坐到第 （ｏ一１，２Ａｋ）行中，组内成员可换位置，但每组纳第 人不能坐到第Ｊ列． 共有坐法为： 维普资讯 http://www.cqvip.com 第３期 。装错信封问题”数学模型的求解及推广 ９７ Ｅｋ．Ｄ ＝ ！ ［１＋ ｉｆｉＩ ｆ。 ］．［１＋ ｆ＝Ｉ 。。 ］ 推广３ 编号为ｎ ｎ。 ，…，ｎ。－，…ｎ ａｎ２．．．ａ 的 志个人（每组ｋ个人，共 组），坐到编号 为ｂ ｂ。ｚ，…ｂ。－，…，ｂ ｂ …，ｂ 的 愚个位置（共 行ｋ列），但编号为ｎ 的人不能坐到编号为 ｂ ｊ的位置中，问：共有几种不同的坐法？ 为了解决这类问，我们再来给出定理３ 定理３ 编号为ｎ ｎ。 ，…，ｎ。。，…ｎ ａｎ２＂－＇ａ 的 志个人（每组ｋ个人，共 组），坐到编号 为ｂ ｂ。 ，…ｂ。。，…，ｂ ｂ …，ｂ 的 志个位置（共 行ｋ列），但编号为ｎ 的人不能坐到编号为 ｂ ｊ的位置中，则不同的坐法为： Ｆ＾ ＝Ｄ Ｉ （ 志）！·（１一 １＋ 击＋…＋（一１） 丽１） ｃ 十 丁（－Ｉ）ｉ 从上面这个通项公式中我们可以看出当 ＝１或ｋ＝１时正好为错位排列的通解． 参考文献 Ｅ１３骆祖曹．数学史数学导论ＥＭ３．杭州：浙江教育出版社，１９７６． Ｅ２３颜书．“装错信封问题”的数学模型与求解Ｅ３３．数学通报，２０００（６）
