装错信封问题

考公务员 就上 591UP 公务员考试平台 591UP 公务员考试平台 装错信封问题装错信封问题 1 问题的提出问题的提出 1 同室四人各写一张贺年卡 先集中起来 然后每人从中拿一张别人送出的贺年 卡 则四张贺年卡的不同分配方式有 A 6 种 B 9 种 C 11 种 D 23 种 2 有 5 个客人参加宴会 他们把帽子放在衣帽寄放室内 宴会结束后每人戴了一 顶帽子回家 回家后 他们的妻子都发现他们戴了别人的帽子 问 5 个客人都不戴自 己帽子的戴法有多少种 上述两个问题 实质上是完全一样的 是被著名数学家欧拉 Leonhard Euler 1707 1783 称为 组合数论的一个妙题 的 装错信封问题 的两个特 例 装错信封问题 是由当时最有名的数学家约翰 伯努利 Johann Bernoulli 1667 1748 的儿子丹尼尔 伯努利 DanidBernoulli 1700 1782 提出来的 大意如下 一个人写了 n 封不同的信及相应的 n 个不同的信封 他把这 n 封信都装错了信封 问都装错信封的装法有多少种 2 建立数学模型建立数学模型 装错信封问题 及两个特例 其实就是 n 个不同元素的一类特殊排列问题 本 文试就给出这类问题的数学模型及求解公式 为方便 我们先把 n 个不同的元素及相 应的位置都编上序号 1 2 n 并且约定 在 n 个不同元素的排列中 1 若编号为 i i 1 2 n 的元素排在第 i 个位置 则称元素 i 在原位 否则 称元素 i 不在原位 2 若所有的元素都不在原位 则称这种排列为 n 个不同元素的一个错排错排 若每个 元素都在原位则称为序排 按照上面约定 装错信封问题 即为 n 个不同元素的错排问题 则可构建 装 错信封问题 的数学模型为 在 n 个不同元素的全排列中 有多少种不同的错排 3 模型求解模型求解 考公务员 就上 591UP 公务员考试平台 591UP 公务员考试平台 应用集合中的容斥原理 我们就可得到 装错信封问题 的数学模型的求解公 式 设 I 表示 n 个不同元素的全排列的集合 Ai i 1 2 n 为元素 i 在原位的排列的集合 Ai Aj 1 i j n 为元素 i 与 j 在原位的排列的集合 A1 A2 An为 n 个元素的序排的集合 则它们的排列数 即各个集合中元素的个数 分别为 I n Ai n 1 Ai Aj n 2 A1 A2 An n n 0 所以 根据容斥原理即得 装错信封问题 的数学模型的求解公式 即 n 个不同元 素的错排数 为 考公务员 就上 591UP 公务员考试平台 591UP 公务员考试平台 4 应用举例应用举例 一个元素的错排数显然为 0 二个不同元素的错排数为 1 三个不同元素的错排数 为 2 均可由公式验证 由公式还可求得四个不同元素的错排数为 五个不同元素的错排数为 则本文开头的问题 1 共有 9 种不同的分配方式 故选 B 问题 2 共有 44 种不同 的戴法 下面再举几例说明公式的应用 例例 1 设有编号为 1 2 3 4 5 的五个球和编号为 1 2 3 4 5 的五个盒子 现将这五个球投放入五个盒内 要求每个盒内投放一个球 并且恰好有两个球的编号 与盒子的编号相同 则这样的投放方法的总数为 A 20 种 B 30 种 C 60 种 D 120 种 解解 本题实质上是三个元素的错排问题 但由于题中未指明是哪三个元素进行的错 排 故本题可分两步求解 考公务员 就上 591UP 公务员考试平台 591UP 公务员考试平台 第二步 对已选出的三个元素进行错排 有 2 种 例例 2 某省决定对所辖 8 个城市的党政一把手进行任职交流 要求把每个干部都调 到另一个城市去担任相应的职务 问共