7-错排问题.pptVIP

第六讲 错排问题 * * 考虑如下问题:某人写了5份信与5个信封,将信随便乱装入信封(每个信封装一封信),问无一匹配的装法是多少? 这个问题实质上就是一个错排问题． 6.1 错排问题 当 时, 的全排列只有一个 ,它不是错位. 所以 当 时, 的全排列有2个 和 前者不是错位,后者是错位.所以 当 时, 的全排列有6个, 前4个不是错位,后2个是错位.所以 6.1 错排问题 n个元素依次给以标号1，2，…，n。n个元素的全排列中，求每个元素都不在自己原来位置上的排列数。 设 为数 在第 位上的全体排列，=1，2，…，n。因数字 不能动，因而有： 同理 6.1 错排问题 每个元素都不在原来位置的排列数为 又记为 6.1 错排问题 　例 在一次聚会上，７位男士将他们的帽子寄存衣帽 间．有多少种方法使得这些帽子被返还时分别满足下 列条件？ （１）没有男士收到自己的帽子； （２）至少一位男士收到自己的帽子； （３）至少两位男士收到自己的帽子． 答： （１） （２） （３） 6.1 错排问题 例 数1，2，…，9的全排列中，求偶数在原来位置上，其余都不在原来位置的错排数目。 解：实际上是1，3，5，7，9五个数的错排问题，总数为： 6.1 错排问题 例　在8个字母A,B,C,D,E,F,G,H的全排列中,求使A,C,E,G四个字母不在原来上的错排数目。 解: 8个字母的全排列中,令 分别表A,C,E,G在原来位置上的排列，则错排数为： 6.1 错排问题 例 求8个字母A,B,C,D,E,F,G,H的全排列中只有4个 不在原来位置的排列数。 解：8个字母中只有4个不在原来位置上，其余4个字母保持不动，相当于4个元素的错排，其数目为 故8个字母的全排列中有4个不在原来位置上的排列数应为：C(8,4)·9=630 6.1 错排问题 考虑极限 它表明的是我们随机地选择 的一个全排列是一个错排列的概率. 6.1 错排问题 例 设有n册书分给n个学生，之后又将书收回重新分 给学生．问有多少种方式分配这些书使得没有一个学 生两次得到同一本书． 解： 第一次分有 种方法． 第二次分配，由题义知就是一个错排， 所以有 种方法． 所求方式为 6.1 错排问题 定理 证明: 的错排 可以分为互不 相容的两种类型; (1) 对于 令 由于 故选取 的方法共有 种. 又由于 的值已定,故将剩下的 进行错排列, 个数由 故这样的错排列个数为 6.1 错排问题 由乘法法则知,此类型包含的错排列数为 (2) 对于 令 由于 故选取 的方法共有 种. 但这时只有 的值已定,且 故将剩下的 个数由 作错排, 其错排数为 由乘法法则知,此类型包含的错排列数为 由于这两种类型互不相容,由加法法则即证． 6.1 错排问题 1. 有限制排列 解设出现xxxx的排列的集合记A1， |A1|= =60; 设出现yyy的排列的集合记A2， | A2|= =105； 1!3!2! ６! 4!·1!·2! 7! 例　4个x ，3个y，2个z的全排列中，求不出现xxxx，yyy，zz图象的排列。 6.2 有限制排列和棋盘多项式 设出现zz的排列的集合记为A3,| A3|= =280； 4!·3! 8! |A1∩A2|= =12； |A1∩A3|= =20； |A2∩A3|= =30； |A1∩A2∩A3|=3!=6； 全排列的个数为： =1260； 所以： |A1∩A2∩A3|=1260－(60+105+280) +(12+20+30)－6 =871 4! 2! 5! 3! 6! 4! 9! 2!·3!·4! 6.2 有限制排列和棋盘多项式 例 在整数 的无重全排列 中, 要求 试求全体排列数 解: 问题等价于在排列中,数 不能排在数 之前, 即不允许出现 中任何一种形式. 用 表示所有无重全排列的集合,并设性质 表示 在全排列中具有 形式的这一性质, 令 6.2 有限制排列和棋盘多项式 令 则 6.2 有限制排列和棋盘多项式 例 8个小孩围坐在旋转木马上,问有多