《离散数学 第2版 教学课件 ppt 作者 王元元 离散第5讲 容斥原理与排列组合》由会员分享，可在线阅读，更多相关《离散数学 第2版 教学课件 ppt 作者 王元元 离散第5讲 容斥原理与排列组合（45页珍藏版）》请在金锄头文库上搜索。
1、,计算机专业基础课程,授课人：宋丽华 单位：计算机理论教研室,指挥自动化学院计算机系,PowerPoint Template_Sub,鸽笼原理 N+1只鸽子飞进N只笼子，至少有2只鸽子飞进同一笼子 N个对象放入k个盒子，有一个盒子至少放入 个对象 计数问题 重新排列单词SUCCESS中的字母能得到多少不同的字符串？ 排列、组合 组合数学 研究给定模式下可能的配置、配置的存在性、配置的数目、配置的性质等 鸽笼原理讨论可能配置的存在性，计数则解决配置数目的计算问题，广泛应用于事件概率的计算以及计算机算法的复杂性研究,PowerPoint Template_Sub,计数基本原理,排列与组合,重集的排
2、列与组合,计数基本原理与排列组合,Page 82 to 87,离散数学第5讲,-5-,第5讲 计数基本原理与排列组合,内容提要,6.1 计数基本原理 加法原理、乘法原理 包含排斥原理（容斥原理） 6.2 排列与组合 线排列、圆排列、组合 在回顾中学知识的基础上适度提高,-6-,第5讲 计数基本原理与排列组合,加法原理与乘法原理,加法原理 若有限集合S=S1S2 Sn，且S1, S2 , , Sn两两不相交，那么|S| = |S1| + |S2| + + |Sn| 分类计数：完成一件事有n类办法，在第1类办法中有a1 种 不同的方式，在第n类办法中有an 种不同的方式，那么完成这件事共有a1 +
3、 + an 种不同的方式 乘法原理 对有限集合S1, S2 , , Sn，|S1S2 Sn| = |S1|S2| |Sn| 分步计数：完成一个任务需要分成个步骤，做第1步有 a1 种不同的方式，做第步有an 种不同的方式，那么 完成整个任务共有a1a2 an种方式,-7-,第5讲 计数基本原理与排列组合,应用,例1 一家服装厂用4种式样，5种颜色，8种尺寸生产男式服装；用6种式样，5种颜色，6种尺寸生产女式服装，问这家服装厂共计生产男女服装多少种？ 解：男式服装种类：458 = 160（种） 女式服装种类：656 = 180 （种） 共计：160 + 180 = 340 （种）,加法原理,-8
4、-,第5讲 计数基本原理与排列组合,应用,例2 从上海直达天津可以乘坐汽车、火车和飞机旅行，已知汽车有3个班次，火车有4个班次，飞机有2个班次。从天津直达大连可以乘坐轮船和飞机旅行，已知轮船有2个班次，飞机有3个班次。问从上海经天津到大连有多少种旅行安排？ 解：从上海到天津有 3+4+2 = 9 种旅行安排 从天津到大连有 2+3 = 5 种旅行安排 从上海经天津到大连共有 95 = 45 种旅行安排,乘法原理,-9-,第5讲 计数基本原理与排列组合,加法原理与乘法原理注意点,都是把一个事件分解成若干个分事件来完成 加法原理（分类计数原理） 如果分事件相互独立，分类完备，就用分类计数原理 注意
5、：分类时要做到不重不漏 乘法原理（分步计数原理） 如果分事件相互关联，缺一 不可，就用分步计数原理 注意：分步时做到不缺 经常结合使用,-10-,第5讲 计数基本原理与排列组合,相交集合的计数,加法原理中，S1, S2 , , Sn两两不相交，|S| = |S1| + |S2| + + |Sn| 若取消两两不相交的限制，该如何计算？ 考虑两个集合的情况,-11-,第5讲 计数基本原理与排列组合,相交集合的计数,加法原理中，S1, S2 , , Sn两两不相交，|S| = |S1| + |S2| + + |Sn| 若取消两两不相交的限制，该如何计算？ 考虑两个集合的情况,|A| + |B|, |
6、AB|,-12-,第5讲 计数基本原理与排列组合,相交集合的计数,加法原理中，S1, S2 , , Sn两两不相交，|S| = |S1| + |S2| + + |Sn| 若取消两两不相交的限制，该如何计算？ 考虑两个集合的情况,|A| + |B| |AB|,1,1,1,|AB| = |A| + |B| |AB|,-13-,第5讲 计数基本原理与排列组合,三个相交集合的计数,三个集合的情况,|A| + |B| + |C|,-14-,第5讲 计数基本原理与排列组合,三个相交集合的计数,三个集合的情况,A,B,C,|A| + |B| + |C|,1,1,1,3,|AB| |AC| |BC|,-15-
7、,第5讲 计数基本原理与排列组合,三个相交集合的计数,三个集合的情况,|A| + |B| + |C|,|AB| |AC| |BC|,+ |ABC|,A,B,C,1,1,1,3,0,-16-,第5讲 计数基本原理与排列组合,三个相交集合的计数,三个集合的情况,|A U B U C | = |A| + |B| + |C|AB|AC|BC| + |AB C |,|A| + |B| + |C|,|AB| |AC| |BC|,+ |ABC|,A,B,C,1,1,1,1,-17-,第5讲 计数基本原理与排列组合,n个相交集合的计数,定理6.2 考虑集合S1, S2 , , Sn, S = S1S2Sn ，
8、那么 |S| = | S1S2Sn | 验证： n=1 n=2 n=3,-18-,第5讲 计数基本原理与排列组合,定理6.2的证明,用数学归纳法证明 | S1S2Sn | 对n进行归纳 基础步：n=1、2时，根据上面的验证，等式成立； 归纳步：假设n=k (k1)时等式成立，则n=k+1时 等式依然成立 综上，对任意自然数n 1，均有等式成立,-19-,第5讲 计数基本原理与排列组合,另一种证明思路,从集合| S1S2Sn |中每个元素被计数的次数来考虑 设元素a S1S2Sn ，它恰在Sa1, Sa2, , Sar中出现(1a1a2arn) 则元素a被 因为 所以 元素a恰被计数1次,计数了
9、 次,计数了 次,计数了 次,计数了 次,-20-,第5讲 计数基本原理与排列组合,应用,试计算在集合1，2，3，1000中有多少元素至少能被5，6，8这三个数中的一个整除 用A、B、C分别表示1000以内能被5、6、8整除的正整数集合，题意为求| ABC |,一个数能被若干个数同时整除当且仅当这个数能被它们的 最小公倍数整除,|AB | = = 33 |AC | = = 25 |BC | = = 41 | ABC | = = 8, |ABC|= |A| + |B| + |C| |AB| |AC| |BC| + |ABC| = 400（个）,|A| = = 200 |B| = = 166 |C
10、| = = 125,-21-,第5讲 计数基本原理与排列组合,应用,学校1807个新生中有453人选了计算机科学课，567人选了数学 课，299人同时选了计算机科学课和数学课。问有多少学生既没 选计算机科学课又没选数学课？ 用S表示全体新生，用A、B分别表示选了计算机科学课和数学课的新生集合。 A S， B S 。可把S看作全集。 A 为没选计算机科学课的新生集合， B 为没选数学课的新 生集合，目标是求| A B | A B = S(AB) | A B | = | S(AB)| =|S| |AB| = |S| (|A| +|B| |AB|) = 1807 (453 + 567 299) =
11、1086 因此，共有1086人既没选计算机科学课又没选数学课,-22-,第5讲 计数基本原理与排列组合,容斥原理,容斥原理 用S1, S2 , , Sn分别表示集合S中具有性质P1, P2 , , Pn元素集合，则S中同时不具有这些性质的元素个数为 | S1 S2 Sn |,-23-,第5讲 计数基本原理与排列组合,应用,已知：密钥是长度为L的0，1序列，为安全起见，须对密钥进 行变换。变换方式是：对于被p整除和被q整除的各位改变其奇 偶性。问：作此改变后，未改变奇偶性的有多少位？为了使未 改变奇偶性的位尽可能地少，p,q 应满足什么性质？ L=50，p=4，q=6 用S表示密钥各位的集合（全
12、集），用A、B分别表示被4整除和被6整除 的各位组成的集合 一次未改的密钥位集合为A B ；改变两次，最终与原奇偶性相同的密钥位集合为AB 根据容斥原理， | A B | + |AB | = |S| |A| |B| + |AB| + |AB| 最终有38个密钥位未改变奇偶性,= 38,-24-,第5讲 计数基本原理与排列组合,应用,已知：密钥是长度为L的0，1序列，为安全起见，须对密钥进行变换。变换方式是：对于被p整除和被q整除的各位改变其奇偶性。问：作此改变后，未改变奇偶性的有多少位？为了使未改变奇偶性的位尽可能地少，p,q 应满足什么性质？,为使未改变奇偶性的位尽可能地少，p,q 应互质,
13、-25-,第5讲 计数基本原理与排列组合,应用,一次会议有2005位数学家参加，每人至少有1337位合作者，求证：可以找到4位数学家，他们中每两人都合作过。 记数学家们为a，b，与其合作过的数学家集合分别记作A，B, 。 任取一数学家a，并取b A（a与b合作过） |A|1337，|B|1337，|AB|2005 |AB|=|A|+|B|AB|1337220050 取c AB（c与a、b均合作过） 因为|ABC|=|AB|+|C|(AB)C|(133722005)+13372005=1 因而存在数学家d ABC，d与a、b、c均合作过 找到四位数学家a、b、c、d，他们两两合作过,-26-,第
14、5讲 计数基本原理与排列组合,线排列的计数,定义：用Pnr或P(n,r)表示“从n个不同元素的集合中每次取出r个元素进行有序排列时可得到的排列的总数”。Pnr或P(n,r)简称为r-排列数， P(n,n)简称为n-全排列数 定理：对任意正整数n , r , rn , r-排列数是,-27-,第5讲 计数基本原理与排列组合,排列组合求解方法例1：,班里照相，12人站一排。8个男学员，4个女学员，要求女学员要排在一起，共有多少种不同的排法？ 将4个女学员看成是一个人,与8个男学员作全排列，共P(9,9)种，4个女学员内部排列方式有P(4,4)种，所以共P(9,9) P(4,4)种 捆绑法：要求某几
15、个元素必须排在一起的问题,可以用捆绑法来解决。即将需要相邻的元素合并为一个元素,再与其它元素一起作排列，同时要注意合并元素内部也可以作排列。,-28-,第5讲 计数基本原理与排列组合,排列组合求解方法例2：,班里照相，12人站一排。8个男学员，4个女学员，要求女学员在男学员中间，且女学员互不相邻，共有多少种不同的排法？ 先排男学员共有P(8,8) 种排法。然后把女学员插入男学员之间的空档，共有7个空档可插，选其中的4个空档,共有P(7,4) 种选法。根据乘法原理，共有不同排法P(8,8) P(7,4) 种 插空法：对于某两个元素或者几个元素要求不相邻的问题,可以用插空法。即先排好没有限制条件的元素,然后将有限制条件的元素按要求插到排好元素的空档之中即可。,-29-,第5讲 计数基本原理与排列组合,排列组合求解方法例3：,期终安排考试科目7门，英语要在离散数学之前考,有多少种不同的安排顺序? 不加任何限制条件，整个排法有
