全错位排列数的求法.pdf

1 全错位排列数的求法 华南师范大学 朱信武 摘要 本文针对全错位排列这一问题 给出了几种不同的求解方法 分别是利 用容斥原理 概率方法以及数学归纳方法 关键词 全错位排列 容斥原理 配对问题 数学归纳法 一 问题引出 设有n个编号分别为 123 n a a aa 的球 同时有编号分别为 1 2 3 n 的盒子 现在我们将这些球放到这些盒子当中 要求 k a不在第k个盒子中 1kn 问这样的放法一共有多少种 这就是全错位的排列问题 下面我们就来求解一 下这种放法一共有多少种 二 几种求法 第一种方法 容斥原理 我们可以把盒子看是固定的已经排列好的 只让球移动就可以了 首先 n个编号分别为 123 n a a aa的球的总排列方法有 n n A种 我们记 把 k a放在第k个盒子时 排列的种数为 k B 记全错位排列数为 n D 从而我们就 可以得到 2 12 n nnn DABBB 绝对值 符号表示集合的元素个数 由于 1 1 2 2 3 3 0 120 n kn n jkn n ijkn n BA BBA BBBA BBBA 所以根据容斥原理 112 112 12 1 12 11 1 n n iiin iniin BBB BBBBBB 结合 式我们可以得到 12 1122331 123 12310 1 1 n nnnnnn n nnnnnnnn n nnnn nnnn BBB C AC AC AC A AAAA 由此我们就可以得到全错位排列数为 12 1230 1 n nnn nnnnn nnnnn DABBB AAAAA 这就求出了全排列数 而且还是一个很有规律的公式解来的 第二种方法 配对问题 在一个有n个人参加的晚会上 每个人都带了一件礼物 且每个人的礼物 都是不相同的 晚会期间各人从放在一起的n件礼物中随机抽取一件 问至少 有一个人抽到自己的礼物的概率是多少 这个问题看起来与全错位排列的问题有点像 但又有点不像 好像只是一 个概率的问题 接下来让我们来看看它们之间究竟有些什么关系 以 i B记事件 第i个人抽到自己的礼物 1 2 in 则所求的概率为 12 n P BBB 3 因为 12 12131 12312421 123 1 1 1 1 1 2 1 n nn nnn n P BP BP B n P B BP B BP BB n n P B B BP B B BP BBB n nn P B B BB n 从而由概率的加法公式 1 12 111 1 nn n iiijn iij ni PBP BP BBP BBB 可以得到 1 12 1111 1 1 2 3 4 n n P BBB n 其对立事件 没有一个人抽到自己的礼物 的概率为 12 1111 1 1 1 1 2 3 4 n n P BBB n 根据题意可以知道全错位的排列数为 12 2340 1 1111 1 1 1 2 3 4 1 n nnn nn n nnnnnn nnnnnn DAP BBB A n AAAAAA 注意到 1nn nn AA 所以有 12340 1 nnnnnn nnnnnnn DAAAAAA 可见用这种概率的方法与用容斥原理是殊途同归的 概率的加法公式是用数学 归纳法证明的 而没有用到容斥原理 所以这两种求全错位排列数的求解方法 是不同的 4 第三种方法 数学归纳方法 现在假设我们已经知道全错位排列的公式为 12340 1 nnnnnn nnnnnnn DAAAAAA 转而去证明上式是正确的 我们采用第二数学归纳法来证明之 证明证明 这里的记号与上文中的记号含义相同 球的编号分别为 123 n a a aa 盒子的编号分别为 1 2 3 n 第一步 当1n 时 显然全错位的排列是不存在的 即排列数为0 而 10 111 0DAA 所以当1n 时 命题成立 第二步 假设对任意的小于n的正整数 以上公式是成立的 则对正整数n 我们要证明上式也是成立的 要证明对正整数n命题成立 肯定会用到我们在第二步中的假设的 不然 的话就不是数学归纳法了 我们可以从这里下手去证明 先看看这里面有没有 什么联系 要对n个小球进行全错位排列 我们可以先排 1 a 由于它不能放在第1个盒 子里 所以它有1n 的位置可以选择 假设它被排在了第j个盒子中 现在我 们还有1n 个小球没有放 那要怎么放呢 我们分两种情况来讨论 第一种情况 小球 j a刚好排在了第1个盒子 那么就剩下2n 个小球了 把它们进行全错位排列 共有 2n D 种方法 第二种情况 小球 j a没有排在第1个盒子 这个时候可以把小球 j a看成小 球 1 a 从而问题变成1n 个小球的全错位的排列问题 共有 1n D 种排法 所以由分步计算原理 12 1 nnn DnDD 根据第二步的假设 右边 就等于 1231023420 11112222 1 1 1 nnnnnnnn nnnnnnnn nAAAAAAAA 化简上式 我们可以得到 5 1 2 1 2 1111 11 1 2 3 4 1 1111 2 1 2 3 4 2 1111 1 1 1 2 3 4 1 1111 1 2 3 4 2 11 1 2 3 n n n n nn n n n nn n n nn 上式 11 2 11 111111 1 1 4 1 2 3 4 1 1111 1 2 3 4 2 11111 1 1 1 2 3 4 1 1 111 1 2 3 4 nn n nn nn n nn nn n n 1 12340 111 1 1 1 1 1111 1 2 3 4 1 nn n nnnnnn nnnnnn nnn n n AAAAAA 刚好等于 12340 1 nnnnnn nnnnnnn DAAAAAA 所以对正整数n 命题 也成立 所以由第二数学归纳法知 全错位排列数的公式为 12340 1 nnn