第04讲 计数问题-容斥原理与鸽笼原理

1、离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程离离 散散 数数 学学电子科技大学电子科技大学计算机科学与工程学院计算机科学与工程学院信息与软件工程学院信息与软件工程学院20212021年年11 11月月3 3日星期三日星期三24-24-2 2离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-32.42.4 容斥原理与鸽笼原理容斥原理与鸽笼原理容斥原理容斥原理是研究若干有限集合交与并的计数问题是研究若干有限集合交与并的计数问题鸽笼原理鸽笼原理则是研究某些特定对

2、象的存在性问题。则是研究某些特定对象的存在性问题。 24-24-3 3离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-32.4.1 2.4.1 容斥原理容斥原理定义定义2.4.12.4.1 所谓所谓容斥容斥，是指我们计算某类物体的，是指我们计算某类物体的数目时，要排斥那些不应包含在这个计数中的数目，数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补但同时要包容那些被错误地排斥了的数目，以此补偿。这种原理称为偿。这种原理称为容斥原理容斥原理(The Principle o

3、f (The Principle of Inclusion-exclusion)Inclusion-exclusion)，又称为，又称为包含排斥原理包含排斥原理。24-24-4 4离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3定理定理2.4.12.4.1 设设A A和和B B是任意有限集合，有是任意有限集合，有|AB| = |A|AB| = |A|B|B|AB|AB|。分析分析 由图容易看出，由图容易看出，AB = (A - B)(AB)(B - A)AB = (A - B)(AB)(B - A)，A =

4、 ( A - B)(AB)A = ( A - B)(AB)B = (AB)(B - A)B = (AB)(B - A)UA BABABA-BA-BB-AB-A|A| = |A-B|+|AB|B| = |AB|+|B-A|AB| = |A-B|+|AB|+|B-A| 推论推论2.4.22.4.2 设设U U为全集，为全集，A A和和B B是任意有限集合，则是任意有限集合，则ABU(AB)AB24-24-5 5离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3例例2.4.12.4.1对所给的集合验证定理对所给的集

5、合验证定理2.4.12.4.1。（1 1）A = 1,2,3,4A = 1,2,3,4，B = 2,3,5,6,8B = 2,3,5,6,8；（2 2）A = 1,2,3,4A = 1,2,3,4，B = 5,6,7,8B = 5,6,7,8。 根据定理根据定理2.4.12.4.1，需先计算需先计算A AB B和和A AB B，再计算再计算|A|,|B|A|,|B|和和|A|AB|B|，然后代入公式然后代入公式(2.4.1)(2.4.1)两端，验证两端，验证等式即可。等式即可。分析分析解解 (1)(1) A AB=1,2,3,4,5,6,8B=1,2,3,4,5,6,8，A AB=2,3B=2

6、,3 | A| A B | = 7 , | AB | = 7 , | A B | = 2B | = 2 。 又又 |A|=4, |B|=5|A|=4, |B|=5， |A|A|B|B|AB|=4|AB|=45 52=7= |A2=7= |AB|B|即即定理定理2.4.12.4.1成立；成立； (2) (2)略。略。24-24-6 6离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3三个集合的情形三个集合的情形 定理定理2.4.32.4.3 设设A A，B B和和C C是任意三个有限集合，有是任意三个有限集合，

7、有推论推论2.4.42.4.4 设设U U为全集，为全集， A A，B B和和C C是任意有限集合，是任意有限集合，则则AABBC =( A + B + C)-( AC =( A + B + C)-( AB + AB + AC + BC + BC)+ AC)+ ABBC CAABBC = U -( A + B + C)C = U -( A + B + C)+( A+( AB + AB + AC + BC + BC)- AC)- ABBC C24-24-7 7离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3例

8、例2.4.22.4.2 调查调查260260个大学生，获得如下数据：个大学生，获得如下数据：6464人选修人选修数学课程，数学课程，9494人选修计算机课程，人选修计算机课程，5858人选修商贸课人选修商贸课程，程，2828人同时选修数学课程和商贸课程，人同时选修数学课程和商贸课程，2626人同时人同时选修数学课程和计算机课程，选修数学课程和计算机课程，2222人同时选修计算机人同时选修计算机课程和商贸课程，课程和商贸课程，1414人对三种课程都选修。问人对三种课程都选修。问（1 1）调查中）调查中三种课程都不选的学生三种课程都不选的学生有多少？有多少？（2 2）调查中）调查中只选修计算机科学

9、课程的学生只选修计算机科学课程的学生有多少？有多少？24-24-8 8离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3例例2.4.2 2.4.2 解解 设设A A、B B、C C分别表示选修数学课程，计算机课程分别表示选修数学课程，计算机课程和商贸课程的人构成的集合，和商贸课程的人构成的集合，则三种课程都不选的学生集合为则三种课程都不选的学生集合为 ，只选修计算机科学课程学生的集合为只选修计算机科学课程学生的集合为 。 UABCAABBC CAABBC C24-24-9 9离散数学课程组离散数学课程组国家级

10、精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3例例2.4.2 2.4.2 解（续）解（续）（1 1）|U|=260, |A|=64, |B|=94, |C|=58,|U|=260, |A|=64, |B|=94, |C|=58,| A AC|=28 ,|AC|=28 ,|AB|=26 ,|BB|=26 ,|BC|=22,C|=22, |A |AB B C|=14 C|=14，所以利用，所以利用容斥原理容斥原理得得 =106=106（2 2）A A B BC C = = U U- -( (A A + +B B+ + C C) )+ +( (

11、A A B B+ + A AC C+ +B BC C) )- -A A B BC CAABBC = B - AC = B - AB - BB - BC + AC + ABBC C= 94 -26-22+14= 60= 94 -26-22+14= 6024-24-1010离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3容斥原理的推广容斥原理的推广定理定理2.4.52.4.5 设设A A1 1, A, A2 2, , , A, An n是任意是任意n n个有限集合，个有限集合，则则推论推论2.4.62.4.6

12、设设U U为全集，为全集，A A1 1, A, A2 2, , , A, An n是任意是任意n n个个有限集合，则有限集合，则n n12niijijk12niijijki=1ii=1ijijijjk kn+1n+112n12nA A A A A=A -A A=A -A A +A A +A A A A A+(-1)A +(-1)A A A LLA 。A 。m m12niijijk12niijijki=1ii=1ijijijjk kn n12n12nA A A A A= U -A +A A= U -A +A A -A A -A A A A A+(-1) A +(-1) A A A A 。A 。2

13、4-24-1111离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3例例2.4.32.4.3 对对2424名科技人员进行掌握外语情况的调查，其名科技人员进行掌握外语情况的调查，其统计资料如下：会英、日、德、法语的人数分别为统计资料如下：会英、日、德、法语的人数分别为1313、5 5、1010和和9 9。其中同时会英语、日语的人数为。其中同时会英语、日语的人数为2 2；同时会英语和德语、同时会英语和法语、同时会德同时会英语和德语、同时会英语和法语、同时会德语和法语两种语言的人数均为语和法语两种语言的人数均为4

14、4；会日语的人既不；会日语的人既不会法语也不会德语。试求会法语也不会德语。试求(1)(1)只会一种语言的人数各为多少？只会一种语言的人数各为多少？(2)(2)同时会英、德、法语的人数为多少？同时会英、德、法语的人数为多少？24-24-1212离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3解解设设A A、B B、C C、D D分别为会英、日、德、法语的人的集分别为会英、日、德、法语的人的集合，由已知条件可知：合，由已知条件可知：|A|A|1313，|B|B|5 5，|C|C|1010，|D|D|9 9，|A

15、B|AB|2 2，|AC|AC|AD|AD|CD|CD|4 4，|BC|BC|BD|BD|0,0,|ABC|ABC|ABD|ABD|BCD|BCD|0 0，|ABCD|ABCD|0 0，|ABCD|ABCD|2424，24-24-1313离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3解（续）解（续） 利用利用容斥原理容斥原理，并代入已知条件得，并代入已知条件得 24 2413135 510109 92 24 44 44 40 00 0 0 00 00 0|ACD|ACD|0 0。得：得：|ACD|ACD|

16、1 1，即同时会英、德、法语的只有，即同时会英、德、法语的只有1 1人。人。24-24-1414离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3例例2.4.3 2.4.3 解（续）解（续）设设只会英、日、德、法语的人数分别为只会英、日、德、法语的人数分别为x x1 1,x,x2 2,x,x3 3,x,x4 4，则则 x x1 1|A|A|(BCD)A|(BCD)A| |A|A|(BA)(CA)(DA)|(BA)(CA)(DA)|对对BABA、CACA、DADA应用应用容斥原理容斥原理，得，得 |(BA)(C

17、A)(DA)| |(BA)(CA)(DA)| 2 24 44 40 00 01 10 09 9故，故，x x1 113-913-94 4。类似地类似地可求出：可求出：x x2 23 3，x x3 33 3，x x4 42 2。24-24-1515离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-32.4.2 2.4.2 鸽笼原理鸽笼原理 鸽笼原理（鸽笼原理（Pigeonhole PrinciplePigeonhole Principle）又称为抽屉）又称为抽屉原理、鸽舍原理，是指如下定理。原理、鸽舍原理，是指如

18、下定理。定理定理2.4.7(2.4.7(鸽笼原理鸽笼原理) ) 若有若有n+1n+1只鸽子住进只鸽子住进n n个鸽笼，个鸽笼，则则鸽笼鸽笼2 2只鸽子。只鸽子。证明证明( (反证法反证法) ) 假设每个鸽笼至多住进假设每个鸽笼至多住进1 1只鸽子，则只鸽子，则n n个鸽笼至多住进个鸽笼至多住进n n只鸽子，这与有只鸽子，这与有n+1n+1只鸽子矛盾。只鸽子矛盾。故存在一个鸽笼至少住进故存在一个鸽笼至少住进2 2只鸽子。只鸽子。 注意：注意：（1 1）鸽笼原理仅提供了）鸽笼原理仅提供了存在性证明存在性证明；（2 2）使用鸽笼原理，必须能够）使用鸽笼原理，必须能够正确识别鸽子正确识别鸽子( (对象

19、对象) )和和鸽巢鸽巢( (某类要求的特征某类要求的特征) )，并且能够计算出鸽子数和，并且能够计算出鸽子数和鸽巢数。鸽巢数。24-24-1616离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3例例2.4.42.4.4抽屉里有抽屉里有3 3双手套，问从中至少取多少只，双手套，问从中至少取多少只，才能保证配成一双？才能保证配成一双？分析：分析：将手套看成是鸽子，将手套看成是鸽子，3 3双手套的数量双手套的数量3 3看成是看成是3 3个鸽巢，按照同型手套飞入同一个个鸽巢，按照同型手套飞入同一个笼子的原则，根据鸽

20、笼原理，需要笼子的原则，根据鸽笼原理，需要4 4只手套只手套即可。即可。答：答：4 4只。只。24-24-1717离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3例例2.4.52.4.5 设设1 1到到1010中任意选出六个数，那么其中有两个数中任意选出六个数，那么其中有两个数的和是的和是1111。证明证明 (1)(1)构造构造5 5个鸽笼：个鸽笼： A A1 1=1,10=1,10，A A2 2=2,9=2,9，A A3 3=3,8=3,8， A A4 4=4,7=4,7，A A5 5=5,6=5,6 (

21、2)(2)选出的选出的6 6个数为鸽子个数为鸽子. . 根据根据鸽笼原理鸽笼原理，所选出的，所选出的6 6个数中一定有两个个数中一定有两个数属于同一个集合，这两个数的和为数属于同一个集合，这两个数的和为1111。24-24-1818离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3定理定理2.4.52.4.5若有若有n n只鸽子住进只鸽子住进m m（m mn n）个鸽笼，则）个鸽笼，则存在一个存在一个鸽笼鸽笼至少住至少住进进 只鸽子。这里，只鸽子。这里， 表示小于等于表示小于等于x x的最大整数。的最大整数。

22、n -1n -1+1+1m mx x24-24-1919离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-3例例2.4.62.4.6如果一个图书馆里如果一个图书馆里3030本离散数学书共有本离散数学书共有12031203页，那页，那么必然有一本离散数学书至少有么必然有一本离散数学书至少有4141页。页。证明证明 设页是鸽子，离散数学书是鸽笼，把每页分设页是鸽子，离散数学书是鸽笼，把每页分配到它所出现的离散数学书中，根据定理配到它所出现的离散数学书中，根据定理2.4.52.4.5，则存在一个鸽笼至少住进则存在一个鸽笼至少住进 = 41= 41，即结论得证。即结论得证。(1203 -1)/30 +1(1203 -1)/30 +124-24-2020离散数学课程组离散数学课程组国家级精品课程，国家双语教学示范课程国家级精品课程，国家双语教学示范课程2021-11-32021-11-32.52.5 离散概率简介离散概率简介 概率概率(Probability)(Probability)是是1717世纪为分析博弈游戏世纪为分析博弈游戏而发展起来的学科，最初计算概率仅有计数一种方而发展起来的学科，最初计算概率仅有计数一种方法。法。 本节主要介绍离散概率的基本概率、基本性质本节主要介绍离散概率的基本概率、基本性