“装错信封问题”数学模型的求解及推广.pdf

第 2 5卷第 3期 2 0 0 5年 9月 数 学理论 与应用 M ATHEM ATI CAL THEO RY AND APPLI CATI ONS Vo 1 2 5 No 3 Se p 2 0 0 5 装错信封问题 数学模型的求解及推广 郑 翔 浙 江丽水 职业技 术 学院 丽水 3 2 3 0 0 0 摘 要 本 文给 出 了全错位排 列问题数 学模 型的通解 全错位排 列推 广问题的通解 关键词 排 列 全错位排 列 数学模 型 Th e Ex p a n di n g An d S o l u t i o n On Th e M a t h e ma t i c a l M o d e l of Pe r mut a t i o n f o r Er r o r Po s i t i o nNu m b e r s Zhe ng Xi a n g Li S h u i Te c h n i c a l Co l l e g e L i S hu i 3 2 3 0 0 0 Ab s t r a c t Thi s pa p er di s c us s t he g e ne r a l s ol ut i on o f p e r mu t a t i o n f or er r or p os i t i on nu mbe r s a nd ex pa nd on t he ma t he ma t i c al mo de l o f mi s t a ke i n f i l l i ng e nv el o pe Ke y wor ds p e r mu t a t i o n e r r o r p o s i t i o n n u mb e r s ma t h e ma t i c a l mo d e l 1 问题提 出 1 某省决定对所辖 8个城市的党政一把手进行任职交流 要求把每个干部都调到另一个 城 市 去担任 相应 的职务 问共 有 多少种 不同 的干部 调配方 案 2 有 5个客人参加宴会 他们把衣帽寄放在室内 宴会后每人戴 了一顶帽子 回家 回家 后 他们 的妻子都发现他们戴 了别人的帽子 问 6 个客人都不戴 自己帽子的戴法有多少种 上述两个问题 实质上是完全一样的 被著名数学家欧拉 L e n h a r d E u l e r 1 7 0 7 1 7 8 3 称 为 组合数学论 的一个妙题的 装错信封问题 的两个特例 装错信封问题 是由当时最有名 的数 学 家 约翰 伯努 利 J o h a n n B e r n o u l l i 1 6 6 7 1 7 4 8 的 儿子 丹 尼尔 伯 努 利 D a n i d B e r n o u l l i 1 7 O O 一1 7 8 2 提出来的 大意如下 一个人写了几封不同的信及相应的n个不同的信 封 他把这 封信都装错了信封 问都装错了信封的装法有几种 2 建立数学模 型 装错信封问题 及两个特例 其实就是 个不 同元素的一类特殊排列问题 本文试就给出 这类问题 的数学模型及求解公式 并对这类问题的数学模型进一步的推广 为说明方便 我们 武俊德教授推荐 收稿 日期 2 0 0 5年 3月 1 0日 维普资讯 第 3期 装错信封问题 数学模 型的求解及推广 9 5 先把 个不同的元素及相应的位置都标上序号 1 2 3 并且约定 在 个不同元素的排列 中 1 若编号为a i 一 1 2 3 的元素排在第 个位置 则称元素 在原位 否则称元素n 不在 原位 2 若所有的元素都不在原位 则 称这种排列为 个不同元素的一个全错位排列 若每个 元素都在原位则称为序排 按照上面的约定 装错信封问题 的数学模型为 在 n 个不同元素的全排列 中 共有多少种 不同的错排 即全错位排列问题 3 数学模 型求解 当 一 1时 这时位置只有一个 而该元素不能排在该位置 所 以 这种排法只有 0种 即 D 1 0 当 一 2时 这时 n 不能排在第一个位置 n 不能排在第二个位置的排法只有 1 种 即 n 排在第二个位置 n 排在第一个位置 故 D 一 1 当 3时 设 日 一 1 2 不排在第 i i 一 1 2 位分别填人下面的 个方框中 第一步 考虑第 1 个位置 O a 不能排在第一个位置 第 1 个位置的排法共有 一 1 种 下 面假 定 日 2 排 在第 1个位 置 第二步 考虑第 i 个位置 根据第 个位置是否排 n 可分成两种情况 1 当 n 排在第 个位置 此时 n 已排在第 1 个位置 则还剩下 一 2 个元素和与之对 应的 一 2 个位置 则问题变为 一 2 个元素的错位排列 因此不同的排法有 D 一 种 2 当 n 不排在第 个位置 此时 n 仍排在第 1个位置 因为 n 和 n 均不能排在第 个 位置 所以 当 日 排在第 1 个位置后 剩下的 一 1 个人 日 日 t2 3 o o o 日 日 日 和 一 1 个位置 2 3 其中 日 七一 2 3 一 1 1 不排在第 k位 日 不排在第 位 故此 时也 相 当于 一 1 个元 素 的错位 排列 则不 同 的排法是 D 一 种 由乘法和加法原理知 D 一 一 1 D 一 l D 一 2 1 其中D 一 0 D 一 1 下面用递归迭代法得出 D 的计算公式 由 1 得 即 即 一 一 一 一 一 2 1 D z 一 D1 OD 0 D 2 1 一 一 c D 一 n D 一 l 一 一 1 D 一 舢 毒 维普资讯 9 6 数学理论与应 用 第 2 5卷 即在 个不同元素的全排列 中 错排数为 其 中 且 m 耋 4 装错信封问题 数学模型的推广 上面我们讨论 了 个元素的全错位排列问题 如果我们换一个角度来看 把 个元素看成 组人 则为每一组只有 1 人的全错位排列 为此 我们 自然会想到每组有 2 人 3 人甚至 个人 时的情况又会如何 呢 为此我们将此模型进一步推广 推广 1 k n个人 每组 k个人 共 组 坐到 行 k列共 个位置中 但若第 一 1 2 以 k 组不能坐到第 i i 一 1 2 A k 行中 组 内成员可换位置 问 共有几种不同的坐法 为了解决这类 问题 我们再来给出定理 1 定理 1 k n个人 每组 k个人 共 组 坐到 行 k列共 2 个位置 但若第 一 1 2 A k 组不能坐到第 一 1 2 以 矗 行中 组 内成员可换位置 不同的坐法有 a h P 一 1 口 一 1 Na 一 2 其中 n 一 0 a k z 一 且 n h D 户 D 为 个元素的错排列数 证明 当 一 1时 第一组成员不能坐在第一行中 a 一 0 当 一 2 时 第 1 线人坐到第 2 组位置构成全排 第 2 组人坐到第 1 组位置又构成全排 a 一 户 种 当 三 三 3 时 首先考虑第 1 行 的位置 可能坐此位置的人共有 一 1 组 但无论哪一组人 坐 不同的坐法有 户 一 1 种 下面假定第 1 行被第 i 组坐了 接着 再考虑第 行 同样可分 两种情况讨论 1 若第 行被第 1 组坐 了 此时第 1 行被第 i 组人坐了 此时还剩下 一 2 组人和与之 对应的 2 组位置 则共有 户 如 一 种不同的坐法 2 若第 行不被第 1 组人坐 此时第 1 行仍被第 组人坐 则剩下 一 1 组人和 一 1 组位置 则不同的坐法共有 n 种 再 由乘 法和 加法 原理 d P 6 1 d 一 1 户 n I 一 2 从上面这个通项公式中我们可以看出 k l时正好是错位排列的通解 推广 2 矗 个人 每组 k 个人 共 r l 组 坐到 行 k 列共 矗 个位置中 但若第 i 一 1 2 A k 组不能坐到第 一 1 2 A k 行中 组 内成员可换位置 但每组内第 J人不能坐到第 列 问 共有几种不同的坐法 为了解决这些问题 我们再来给出定理 2 定理 2 矗 个 人 每 组 k 个 人 共 2 组 坐 到 行 k列共 五 个 位置 中 但若 第 一 1 2 A k 组不能坐到第 o一 1 2 A k 行中 组内成员可换位置 但每组纳第 人不能坐到第 J列 共有 坐法 为 一 引 一 一 引 一 一 D l 一 一 一 2 1 州 一 一 一 维普资讯 第 3期 装错信封问题 数学模型的求解及推广 9 7 E k D 1 1 i ffi I f I 推广 3 编号为 n n n n a n 2 a 的 志个人 每组 k个人 共 组 坐到编号 为 b b z b b b b 的 愚 个位置 共 行 k 列 但编号为 n 的人不能坐到编号为 b j 的位置中 问 共有几种不同的坐法 为了解决这类问 我们再来给出定理 3 定理 3 编号为 n n n n a n 2 a 的 志个人 每组 k个人 共 组 坐到编号 为 b b b b b b 的 志 个位置 共 行 k 列 但编号为 n