离散容斥原理与排列组合

离散容斥原理与排列组合演示文稿当前1页，总共41页。（优选）离散容斥原理与排列组合当前2页，总共41页。PowerPointTemplate_Sub1计数基本原理2排列与组合3重集的排列与组合第3章组合论基础计数4递归关系3第5讲计数基本原理与排列组合当前3页，总共41页。计数基本原理与排列组合TextbookPage30to36《离散数学》第5讲当前4页，总共41页。内容提要6.1计数基本原理加法原理、乘法原理包含排斥原理（容斥原理）6.2排列与组合线排列、圆排列、组合在回顾中学知识的基础上适度提高5第5讲计数基本原理与排列组合当前5页，总共41页。加法原理与乘法原理加法原理分类计数：完成一件事有n类办法，在第1类办法中有a1

种不同的方式，…，在第n类办法中有an

种不同的方式，那么完成这件事共有a1+…+an种不同的方式若有限集合S=S1∪S2∪…∪Sn，且S1,S2,…,Sn两两不相交，那么|S|=|S1|+|S2|+…+|Sn|乘法原理分步计数：完成一个任务需要分成ｎ个步骤，做第1步有a1种不同的方式，…，做第ｎ步有an种不同的方式，那么完成整个任务共有a1×a2×…×an种方式对有限集合S1,S2,…,Sn，|S1×S2×

…×Sn|=|S1|×|S2|×…×|Sn|6第5讲计数基本原理与排列组合当前6页，总共41页。应用例1(例3.2)一家服装厂用4种式样，5种颜色，8种尺寸生产男式服装；用6种式样，5种颜色，6种尺寸生产女式服装，问这家服装厂共计生产男女服装多少种？解：男式服装种类：4×5×8=160（种）

女式服装种类：6×5×6=180（种）

共计：160+180=340（种）加法原理乘法原理乘法原理7第5讲计数基本原理与排列组合当前7页，总共41页。应用例2(例3.1)从上海直达天津可以乘坐汽车、火车和飞机旅行，已知汽车有3个班次，火车有4个班次，飞机有2个班次。从天津直达大连可以乘坐轮船和飞机旅行，已知轮船有2个班次，飞机有3个班次。问从上海经天津到大连有多少种旅行安排？解：从上海到天津有3+4+2=9种旅行安排从天津到大连有2+3=5种旅行安排

从上海经天津到大连共有9×5=45种旅行安排乘法原理加法原理加法原理8第5讲计数基本原理与排列组合当前8页，总共41页。加法原理与乘法原理注意点都是把一个事件分解成若干个分事件来完成加法原理（分类计数原理）如果分事件相互独立，分类完备，就用分类计数原理注意：分类时要做到不重不漏乘法原理（分步计数原理）如果分事件相互关联，缺一不可，就用分步计数原理注意：分步时做到不缺经常结合使用9第5讲计数基本原理与排列组合当前9页，总共41页。相交集合的计数加法原理中，S1,S2,…,Sn两两不相交，|S|=|S1|+|S2|+…+|Sn|若取消两两不相交的限制，该如何计算？考虑两个集合的情况AB10第5讲计数基本原理与排列组合当前10页，总共41页。AB相交集合的计数加法原理中，S1,S2,…,Sn两两不相交，|S|=|S1|+|S2|+…+|Sn|若取消两两不相交的限制，该如何计算？考虑两个集合的情况|A|+|B|112－

|A∩B|11第5讲计数基本原理与排列组合当前11页，总共41页。AB相交集合的计数加法原理中，S1,S2,…,Sn两两不相交，|S|=|S1|+|S2|+…+|Sn|若取消两两不相交的限制，该如何计算？考虑两个集合的情况|A|+|B|－

|A∩B|111|A∪B|=|A|+|B|－

|A∩B|12第5讲计数基本原理与排列组合当前12页，总共41页。三个相交集合的计数三个集合的情况ABC|A|+|B|+|C|13第5讲计数基本原理与排列组合当前13页，总共41页。三个相交集合的计数三个集合的情况ABC|A|+|B|+|C|1112223－|A∩B|－

|A∩C|－

|B∩C|14第5讲计数基本原理与排列组合当前14页，总共41页。三个相交集合的计数三个集合的情况|A|+|B|+|C|－|A∩B|－

|A∩C|－

|B∩C|+|A∩B∩C|ABC1111113015第5讲计数基本原理与排列组合当前15页，总共41页。三个相交集合的计数三个集合的情况|AUBUC

|=|A|+|B|+|C|－|A∩B|－|A∩C|－|B∩C|+|A∩B∩C||A|+|B|+|C|－|A∩B|－

|A∩C|－

|B∩C|+|A∩B∩C|ABC111111116第5讲计数基本原理与排列组合当前16页，总共41页。n个相交集合的计数定理3.2考虑集合S1,S2,…,Sn,S=S1∪S2∪…∪Sn

，那么|S|=|S1∪S2∪…∪Sn|验证：n=1n=2n=317第5讲计数基本原理与排列组合当前17页，总共41页。定理3.2的证明用数学归纳法证明|S1∪S2∪…∪Sn|对n进行归纳基础步：n=1,2时，根据上面的验证，等式成立；归纳步：假设n=k(k≥1)时等式成立，则n=k+1时…………等式依然成立综上，对任意自然数n≥1，均有等式成立

课后自己看书18第5讲计数基本原理与排列组合当前18页，总共41页。另一种证明思路从集合|S1∪S2∪…∪Sn|中每个元素被计数的次数来考虑设元素aS1∪S2∪…∪Sn

，它恰在Sa1,Sa2,…,Sar中出现(1≤a1<a2<…<ar≤n)则元素a被因为所以元素a恰被计数1次计数了

次计数了

次计数了

次计数了

次……19第5讲计数基本原理与排列组合当前19页，总共41页。应用(例3.3)试计算在集合{1，2，3，…，1000}中有多少元素至少能被5，6，8这三个数中的一个整除。解.用A、B、C分别表示1000以内能被5、6、8整除的正整数集合，题意为求|A∪B∪C|

∵一个数能被若干个数同时整除当且仅当这个数能被它们的最小公倍数整除

∴|A∩B|==33|A∩C|==25|B∩C|==41|A∩B∩C|==8∴|A∪B∪C|=|A|+|B|+|C|−|A∩B|−|A∩C|−|B∩C|+|A∩B∩C|=400（个）|A|==200|B|==166|C|==12520第5讲计数基本原理与排列组合当前20页，总共41页。应用学校1807个新生中有453人选了计算机科学课，567人选了数学课，299人同时选了计算机科学课和数学课。问有多少学生既没选计算机科学课又没选数学课？用S表示全体新生，用A、B分别表示选了计算机科学课和数学课的新生集合。AS，BS。可把S看作全集。A¯为没选计算机科学课的新生集合，B¯为没选数学课的新生集合，目标是求|A¯∩B¯|∵A¯∩B¯=S－(A∪B)∴|A¯∩B¯|=|S－(A∪B)|=|S|－|A∪B|=|S|－(|A|+|B|－|A∩B|)=1807–(453+567–299)

=1086因此，共有1086人既没选计算机科学课又没选数学课21第5讲计数基本原理与排列组合当前21页，总共41页。容斥原理容斥原理(定理3.4)用S1,S2,…,Sn分别表示集合S中具有性质P1,P2,…,Pn元素集合，则S中同时不具有这些性质的元素个数为

|S1¯∩S2¯∩…∩Sn¯|

22第5讲计数基本原理与排列组合当前22页，总共41页。应用例3.3（2）试计算在集合{1，2，3，…，1000}中有多少元素不能被5，6，8这三个数中的一个整除。解.用A、B、C分别表示1000以内不能被5、6、8整除的正整数集合，题意为求|A¯∩B¯∩C¯|

∵一个数能被若干个数同时整除当且仅当这个数能被它们的最小公倍数整除

∴|A∩B|==33|A∩C|==25|B∩C|==41|A∩B∩C|==8∴|A¯∩B¯∩C¯|=1000-|A|-|B|-|C|+|A∩B|+|A∩C|+|B∩C|-|A∩B∩C|=1000–400=600（个）|A|==200|B|==166|C|==12523第5讲计数基本原理与排列组合当前23页，总共41页。应用已知：密钥是长度为L的0，1序列，为安全起见，须对密钥进行变换。变换方式是：对于被p整除和被q整除的各位改变其奇偶性。问：作此改变后，最终未改变奇偶性的有多少位？为了使未改变奇偶性的位尽可能地少，p,q应满足什么性质？

L=50，p=4，q=6用S表示密钥各位的集合（全集），用A、B分别表示被4整除和被6整除的各位组成的集合一次未改的密钥位集合为A¯∩B¯；改变两次，最终与原奇偶性相同的密钥位集合为A∩B

∵根据容斥原理，|A¯∩B¯|+|A∩B|=|S|−|A|−|B|+|A∩B|+|A∩B|∴最终有38个密钥位未改变奇偶性=3824第5讲计数基本原理与排列组合当前24页，总共41页。应用已知：密钥是长度为L的0，1序列，为安全起见，须对密钥进行变换。变换方式是：对于被p整除和被q整除的各位改变其奇偶性。问：作此改变后，最终未改变奇偶性的有多少位？为了使未改变奇偶性的位尽可能地少，p,q应满足什么性质？

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950为使未改变奇偶性的位尽可能地少，p,q应互质25第5讲计数基本原理与排列组合当前25页，总共41页。应用一次会议有2005位数学家参加，每人至少有1337位合作者，求证：可以找到4位数学家，他们中每两人都合作过。记数学家们为a，b，…，与其合作过的数学家集合分别记作A，B,…。任取一数学家a，并取bA（a与b合作过）∵|A|≥1337，|B|≥1337，|A∪B|≤2005∴|A∩B|=|A|+|B|－|A∪B|≥1337×2－2005＞0取cA∩B（c与a、b均合作过）因为|A∩B∩C|=|A∩B|+|C|－|(A∩B)∪C|≥(1337×2－2005)+1337－2005=1因而存在数学家dA∩B∩C，d与a、b、c均合作过找到四位数学家a、b、c、d，他们两两合作过

26第5讲计数基本原理与排列组合当前26页，总共41页。线排列的计数定义3.1：用Pnr或P(n,r)表示“从n个不同元素的集合中每次取出r个元素进行有序排列时可得到的排列的总数”。Pnr或P(n,r)简称为r-排列数，P(n,n)简称为n-全排列数定理3.5：对任意正整数n,r,r≤n,r-排列数是特别地，Pn1=n，Pnn=n！27第5讲计数基本原理与排列组合当前27页，总共41页。排列组合求解方法例1：班里照相，12人站一排。8个男学员，4个女学员，要求女学员要排在一起，共有多少种不同的排法？将4个女学员看成是一个人,与8个男学员作全排列，共P(9,9)种，4个女学员内部排列方式有P(4,4)种，所以共P(9,9)·P(4,4)种捆绑法：要求某几个元素必须排在一起的问题,可以用捆绑法来解决。即将需要相邻的元素合并为一个元素,再与其它元素一起作排列，同时要注意合并元素内部也可以作排列。28第5讲计数基本原理与排列组合当前28页，总共41页。排列组合求解方法例2：班里照相，12人站一排。8个男学员，4个女学员，要求女学员在男学员中间，且女学员互不相邻，共有多少种不同的排法？先排男学员共有P(8,8)种排法。然后把女学员插入男学员之间的空档，共有7个空档可插，选其中的4个空档,共有P(7,4)种选法。根据乘法原理，共有不同排法P(8,8)·P(7,4)种。插空法：对于某两个元素或者几个元素要求不相邻的问题,可以用插空法。即先排好没有限制条件的元素,然后将有限制条件的元素按要求插到排好元素的空档之中即可。29第5讲计数基本原理与排列组合当前29页，总共41页。排列组合求解方法例3：期末安排考试科目7门，英语要在离散数学之前考,有多少种不同的安排顺序?不加任何限制条件，整个排法有P(7,7)种。“英语安排在离散数学之前考”

与“离散数学安排在英语之前考”的排法是相等的，所以英语安排在离散数学之前考的排法共有P(7,7)/2种。对等法：在有些题目中，限制条件的肯定与否定是对等的，各占全体的二分之一。在求解中只要求出全体,就可以得到所求。30第5讲计数基本原理与排列组合当前30页，总共41页。例3.4有多少个大于5400，又同时满足下列两个性质的整数：（1）各位数字均不相同；（2）不出现数字2和7解：不能出现数字2和7，且各位数字均不相同，所以只能是四、五、六、七、八位数1)对五、六、七、八位数来说，第一位只能从1、3、4、5、6、8、9中选取，即共有7种可能，其他各位可从剩余的7个数字中选择进行排列，共有P(7,i)种（i=4,5,6,7）所以：五、六、七、八位数共有7P(7,4)+7P(7,5)+7P(7,6)+7P(7,7)=

94080

个满足条件。2)对于四位数来说，2.1)若第一位大于5（共有3种可能），则其余3位可从剩余的7个数字选取3个排列，即共有3*P(7,3)=630个。2.2)若第一位为5，则第二位只能从4、6、8、9种选择，其余2位可从剩余的6个数字选取2个排列，即共有1*4*P(6,2)=120个。综上，根据加法原理，共有94080+630+120=94830个31第5讲计数基本原理与排列组合当前31页，总共41页。圆排列的计数定义(圆排列)：从n个不同元素的集合中每次取出r个元素，围绕一个圆周进行有序排列的排列总数（可旋转，但不可翻转）对于圆排列(1,2,3,4,5)12345(1,2,3,4,5)(2,3,4,5,1)(3,4,5,1,2)(4,5,1,2,3)(5,1,2,3,4)一个圆排列对应r个线排列线排列数是圆排列数的r倍32第5讲计数基本原理与排列组合当前32页，总共41页。圆排列的计数定理3.6：对任意正整数n,r,r≤n,从n个不同元素的集合中每次取出r个元素，围绕一个圆周进行有序排列时可得到的排列的总数是：33第5讲计数基本原理与排列组合当前33页，总共41页。例3.5六位女士和六位先生围着一张圆桌聚餐，要求安排女士和先生交替就座。问有多少可能的安排方案？解：可分为两个步骤来分配座位：先安排女士就座，两人之间留一个空位，然后再安排先生就座。安排女士就座的方案共有 种（圆排列）安排好女士后，再安排先生就座时，是线排列而非圆排列问题，因为此时已经有了女士作参照，相同的圆排列与女士圆排列对齐方式不同将导致不同的就座方案。因此，对每一种女士就座方式，可有P(6,6)=720种男士就座方式。根据乘法原理，共有120720=86400种就座方案。34第5讲计数基本原理与排列组合当前34页，总共41页。例五对夫妇围着一张圆桌聚餐，试问每对夫妻相邻而坐的方式有多少种？解：分为两步：第一步先安排五对夫妇的位置，第二步再具体安排每对夫妻两人的相对位置。第一步共有圆排列 种；第二步每对夫妻都有两种相对坐法，因此共有25=32种坐法（乘法原理）。根据乘法原理，共有2432=768种就座方式。35第5讲计数基本原理与排列组合当前35页，总共41页。例A、B、C、D、E、F六人围圆桌而坐，若A、B、C三人相邻，共有多少种坐法？解：第一步将A、B、C看成一个整体，将其与D、E、F一起分配座位，共有 就座方式；第二步规定A、B、C的座位，此时为线排列问题，共有P(3,3)=6种安排方式。根据乘法原理，一共有66=36种坐法。36第5讲计数基本原理与排列组合当前36页，总共41页。组合的计数定义3.2：用Cnr或C(n,r)表示“从n个元素的集合中每次取出r个元素（不进行有序排列）组成子集合的总数”。Cnr或C(n,r)简称为r-组合数定理3.7：

对任意正整数n,r,r≤n,r