离散数学 第2章 计数问题.ppt

* 2.4.1 容斥原理 ?定义2.4.1? 所谓容斥，是指我们计算某类物体的数目时，要排斥那些不应包含在这个计数中的数目，但同时要包容那些被错误地排斥了的数目，以此补偿。这种原理称为容斥原理(The Principle of Inclusion-exclusion)，又称为包含排斥原理。 * 定理2.4.1 ? 设A和B是任意有限集合，有 |A∪B| = |A|＋|B|－|A∩B|。 分析? 由图容易看出， A∪B = (A - B)∪(A∩B)∪(B - A)， A = ( A - B)∪(A∩B) B = (A∩B)∪(B - A) U A B A∩B A-B B-A |A| = |A-B|+|A∩B| |B| = |A∩B|+|B-A| |A∪B| = |A-B|+|A∩B|+|B-A| 推论2.4.2?设U为全集，A和B是任意有限集合，则 * 例2.4.1 对所给的集合验证定理2.4.1。 （1）A = {1,2,3,4}，B = {2,3,5,6,8}； （2）A = {1,2,3,4}，B = {5,6,7,8}。根据定理2.4.1， 需先计算A∪B和A∩B， 再计算|A|,|B|和|A∪B|， 然后代入公式(2.4.1)两端，验证等式即可。 分析 解 (1)∵ A∪B={1,2,3,4,5,6,8}，A∩B={2,3}∴ |A∪B| = 7,|A∩B|=2。又∵ |A|=4, |B|=5，∴ |A|＋|B|－|A∩B|=4＋5－2=7= |A∪B|即定理2.4.1成立； (2)略。 * 三个集合的情形 定理2.4.3 设A，B和C是任意三个有限集合，有 推论2.4.4?设U为全集， A，B和C是任意有限集合，则 * 例2.4.2调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人对三种课程都选修。问 （1）调查中三种课程都不选的学生有多少？ （2）调查中只选修计算机科学课程的学生有多少？ * 例2.4.2 解 ? 设A、B、C分别表示选修数学课程，计算机课程和商贸课程的人构成的集合， 则三种课程都不选的学生集合为， 只选修计算机科学课程学生的集合为。U A B C * 例2.4.2 解（续） （1）∵|U|=260, |A|=64, |B|=94, |C|=58,|A∩C|=28 ,|A∩B|=26 ,|B∩C|=22,|A∩B ∩ C|=14，所以利用容斥原理得 =106 （2） * 容斥原理的推广 定理2.4.5? 设A1, A2, …, An是任意n个有限集合，则 推论2.4.6? 设U为全集，A1, A2, …, An是任意n个有限集合，则 * 例2.4.3对24名科技人员进行掌握外语情况的调查，其统计资料如下：会英、日、德、法语的人数分别为13、5、10和9。其中同时会英语、日语的人数为2；同时会英语和德语、同时会英语和法语、同时会德语和法语两种语言的人数均为4；会日语的人既不会法语也不会德语。试求 (1)只会一种语言的人数各为多少？ (2)同时会英、德、法语的人数为多少？ * 解 设A、B、C、D分别为会英、日、德、法语的人的集合，由已知条件可知：? |A|＝13，|B|＝5，|C|＝10，|D|＝9， |A∩B|＝2，|A∩C|＝|A∩D|＝|C∩D|＝4，|B∩C|＝|B∩D|＝0, |A∩B∩C|＝|A∩B∩D|＝|B∩C∩D|＝0， |A∩B∩C∩D|＝0，|A∪B∪C∪D|＝24， * 解（续）利用容斥原理，并代入已知条件得24＝13＋5＋10＋9－2－4－4－4－0－0＋0＋0＋0＋|A∩C∩D|－0。 得：|A∩C∩D|＝1，即同时会英、德、法语的只有1人。 * 例2.4.3 解（续） 设只会英、日、德、法语的人数分别为x1,x2,x3,x4，则x1＝|A|－|(B∪C∪D)∩A|＝|A|－|(B∩A)∪(C∩A)∪(D∩A)| 对B∩A、C∩A、D∩A应用容斥原理，得|(B∩A)∪(C∩A)∪(D∩A)|＝2＋4＋4－0－0－1＋0＝9 故，x1＝13-9＝4。 类似地可求出：x2＝3，x3＝3，x4＝2。 * 2.4.2 鸽笼原理 ? 鸽笼原理（Pigeonhole Principle）又称为抽屉原理、鸽舍原理，是指如下定理。 定理2.4.7(鸽笼原理)? 若有n+1只鸽子住进n个鸽笼，则有一个鸽笼至少住进2只鸽子。 证明(反证法) 假设每个鸽笼至多住进1只鸽子，则n个鸽笼至多住进n只鸽子，这与有n+1只鸽子矛盾。故存在一个鸽笼至少住进2只鸽子。注意： （1）鸽笼原理仅提供了存在性证明