1、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1 1第第2 2章章 计数问题计数问题 计数问题是组合数学研究的主要问题之一。西计数问题是组合数学研究的主要问题之一。西班牙数学家班牙数学家Abraham ben Meir ibn Ezra(1092Abraham ben Meir ibn Ezra(10921167)1167)和法国数学家、哲学家、天文学家和法国数学家、哲学家、天文学家Levi ben Levi ben Gerson(1288Gerson(12881344)1344)是排列与组合领域的两位早期是排列与组合领域的两位早期研究者。另外，法国数
2、学家研究者。另外，法国数学家Blaise PascalBlaise Pascal还发明还发明了一种机械计算器，这种计算器非常类似于了一种机械计算器，这种计算器非常类似于2020世纪世纪4040年代在数字电子计算机发明之前使用的一种机械年代在数字电子计算机发明之前使用的一种机械计算器。同时，计数技术在数学和计算机科学中是计算器。同时，计数技术在数学和计算机科学中是很重要的，特别是在很重要的，特别是在数据结构数据结构、算法分析与算法分析与设计设计等后续课程中有非常重要的应用。等后续课程中有非常重要的应用。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-2
3、22.0 2.0 内容提要内容提要容斥原理与鸽笼原理容斥原理与鸽笼原理3离散概率离散概率4乘法原理和加法原理乘法原理和加法原理1排列与组合排列与组合2递归关系递归关系5电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-3 31.1 1.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1乘法原理和加乘法原理和加法原理法原理2 2排列组合的计排列组合的计算算 3 3利用容斥原理利用容斥原理计算有限集合的计算有限集合的交与并交与并 31 1 离散概率离散概率2 2 离散概念的计离散概念的计 算公式及性质算公式及性质 21 1 鸽笼原理鸽
4、笼原理2 2 鸽笼原理的简鸽笼原理的简单应用单应用3 3 递归关系递归关系4 4 递归关系的建递归关系的建立和计算立和计算 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-4 4表表2.2.12.2.1开胃食品开胃食品主食主食饮料饮料种类种类价格价格(元元)种类种类价格价格种类种类价格价格玉米片玉米片(Co)2.15汉堡汉堡(H)3.25 茶水茶水(T) 0.70色拉色拉(Sa)1.90三明治三明治(S)3.65牛奶牛奶(M)0.85鱼排鱼排(F)3.15 可乐可乐(C) 0.75啤酒啤酒(B) 0.75电子科技大学离散数学课程组电子科技大学离散数学课程
5、组国家精品课程国家精品课程67-67-5 52.2.1 2.2.1 乘法原理乘法原理 如果一些工作需要如果一些工作需要t t步完成步完成，第一步有，第一步有n n1 1种种不同的选择，第二步有不同的选择，第二步有n n2 2种不同的选择，种不同的选择， ，第第t t步有步有n nt t种不同的选择，那么完成这项工作所种不同的选择，那么完成这项工作所有可能的选择种数为：有可能的选择种数为：12t12tn n n n n n电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6 6例例2.2.2 Melissa2.2.2 Melissa病毒病毒19901990年
6、，一种名叫年，一种名叫MelissaMelissa的病毒利用侵吞系统资源的的病毒利用侵吞系统资源的方法来破坏计算机系统，通过以含恶意宏的字处理文方法来破坏计算机系统，通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址本中找出前宏从用户的地址本中找出前5050个地址个地址，并将病毒转发，并将病毒转发给他们。用户接收到这些被转发的附件并将字处理文给他们。用户接收到这些被转发的附件并将字处理文档打开后，病毒会自动继续转发，不断往复扩散。病档打开后，病毒会自动继续转发，不断往复扩散。病毒非常快速地转发邮件，将被转发的邮件临
7、时存储在毒非常快速地转发邮件，将被转发的邮件临时存储在某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。某个磁盘上，当磁盘占满后，系统将会死锁甚至崩溃。问经过四次转发，共有多少个接收者？问经过四次转发，共有多少个接收者？解解 根据根据MelissaMelissa病毒的扩散原理，经过四次转发，病毒的扩散原理，经过四次转发，共有共有50505050505050+5050+50505050+5050+5050+ 50 +150+ 50 +1= 6377551= 6377551个接收者。个接收者。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-7 7例例2.2.3
8、2.2.3在一幅数字图像中，若在一幅数字图像中，若每个像素点用每个像素点用8 8位进行编码位进行编码，问问每个点有多少种不同的取值。每个点有多少种不同的取值。分析分析 用用8 8位进行编码可分为位进行编码可分为8 8个步骤：选择第一位，个步骤：选择第一位，选择第二位，选择第二位， ，选择第八位。每一个位有两种，选择第八位。每一个位有两种选 择 ， 故 根 据 乘 法 原 理 ，选 择 ， 故 根 据 乘 法 原 理 ， 8 8 位 编 码 共 有位 编 码 共 有2 22 22 22 22 22 22 22 = 22 = 28 8 = 256 = 256种取值。种取值。解解 每个点有每个点有2
9、56( = 2256( = 28 8) ) 种不同的取值。种不同的取值。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-8 82.2.2 2.2.2 加法原理加法原理 假定假定X X1 1, X, X2 2, , , X, Xt t均为集合，第均为集合，第i i个集合个集合X Xi i有有n ni i个元素。如个元素。如XX1 1, X, X2 2, , , X, Xt t 为为两两不相交两两不相交的集的集合，则可以从合，则可以从X X1 1, X, X2 2, , , X, Xt t中选出的元素总数为：中选出的元素总数为：n n1 1 + n + n
10、2 2 + + + n + nt t。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-9 9例例2.2.42.2.4由由AliceAlice、BenBen、ConnieConnie、DolphDolph、EgbertEgbert和和FranciscoFrancisco六个人组成的委员会六个人组成的委员会，要，要选出一个主席、选出一个主席、一个秘书和一个出纳员。一个秘书和一个出纳员。（1 1）共有多少种选法？）共有多少种选法？（2 2）若）若主席必须从主席必须从AliceAlice和和BenBen种选出种选出，共有多少，共有多少种选法？种选法？（3 3）若
11、）若EgbertEgbert必须有职位必须有职位，共有多少种选法？，共有多少种选法？（4 4）若）若DolphDolph和和FranciscoFrancisco都有职位都有职位，共有多少种，共有多少种选法？选法？电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1010例例2.2.4 2.2.4 解解（1 1）根据）根据乘法原理乘法原理，可能的选法种数为，可能的选法种数为6 65 54= 4= 120120；（2 2） 法一法一 根据题意，确定职位可分为根据题意，确定职位可分为3 3个步骤：个步骤：确定主席有确定主席有2 2种选择；主席选定后，秘书有种选择
12、；主席选定后，秘书有5 5个人选；个人选；主席和秘书都选定后，出纳有主席和秘书都选定后，出纳有4 4个人选。根据个人选。根据乘法乘法原理原理，可能的选法种数为，可能的选法种数为2 25 54 = 404 = 40； 法二法二 若若AliceAlice被选为主席，共有被选为主席，共有5 54 = 204 = 20种方法种方法确定其他职位；若确定其他职位；若BenBen为主席，同样有为主席，同样有2020种方法确种方法确定其他职位。由于两种选法得到的集合不相交，所定其他职位。由于两种选法得到的集合不相交，所以根据以根据加法原理加法原理，共有，共有202020 = 4020 = 40种选法；种选法；
13、电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1111例例2.2.4 2.2.4 解解( (续续) )(3)(3)法一法一 将确定职位分为将确定职位分为3 3步：步：确定确定EgbertEgbert的职的职位位, ,有有3 3种方法；种方法；确定余下的较高职位人选确定余下的较高职位人选, , 有有5 5个个人选；人选；确定最后一个职位的人选确定最后一个职位的人选, , 有有4 4个人选。根个人选。根据据乘法原理乘法原理，共有，共有3 35 54 = 604 = 60种选法；种选法； 法二法二 根据根据(1)(1)的结论，的结论，如果如果EgbertEg
14、bert为主席为主席，有，有2020种方法确定余下的职位；种方法确定余下的职位；若若EgbertEgbert为秘书，为秘书，有有2020种种方法确定余下的职位；方法确定余下的职位；若若EgbertEgbert为出纳员为出纳员，也有，也有2020种方法确定余下的职位。由于三种选法得到的集合种方法确定余下的职位。由于三种选法得到的集合不相交，根据不相交，根据加法原理加法原理，共有，共有2020202020 = 6020 = 60种选法；种选法； 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1212例例2.2.4 2.2.4 解解( (续续) )（4 4）
15、将给）将给DolphDolph、FranciscoFrancisco和另一个人指定职位和另一个人指定职位分为分为3 3步：步： 给给DolphDolph指定职位，指定职位，有有3 3个职位可选；个职位可选； 给给FranciscoFrancisco指定职位，指定职位，有有2 2个职位可选；个职位可选； 确定最后一个职位的人选确定最后一个职位的人选，有，有4 4个人选。个人选。 根据根据乘法原理乘法原理，共有，共有3 32 24 = 244 = 24种选法。种选法。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-13132.3 2.3 排列与组合排列与组合
16、 Zeke Zeke、YungYung、XenoXeno和和WilmaWilma四个候选人竞选同一四个候选人竞选同一职位。为了使选票上人名的次序不对投票者产生影职位。为了使选票上人名的次序不对投票者产生影响，有必要将每一种可能的人名次序打印在选票上。响，有必要将每一种可能的人名次序打印在选票上。会有多少种不同的选票呢？会有多少种不同的选票呢？ 从某个集合中有序的选取若干个元素的问题，称为从某个集合中有序的选取若干个元素的问题，称为排列问题排列问题。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-14142.3.1 2.3.1 排列问题排列问题定义定义2.
17、3.12.3.1 从含从含n n个不同元素个不同元素的集合的集合S S中中有序有序选取选取的的r r个元素叫做个元素叫做S S的一个的一个，不同的排列总数，不同的排列总数记为记为P(n, r)P(n, r)。如果。如果r = nr = n，则称这个排列为，则称这个排列为S S的一的一个个，简称为，简称为S S的排列。的排列。显然显然， 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1515例例2.3.12.3.1从含从含3 3个不同元素的集合个不同元素的集合S S中有序选取中有序选取2 2个元素的排个元素的排列总数。列总数。解解 从含从含3 3个元素的
18、不同集合个元素的不同集合S S中有序选取中有序选取2 2个元素个元素的排列总数为的排列总数为6 6种。种。如果将这如果将这3 3个元素记为个元素记为A A、B B和和C C，则，则6 6个排列为个排列为AB, AC, BA, BC, CB, CAAB, AC, BA, BC, CB, CA。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1616定理定理2.3.12.3.1对满足对满足rnrn的正整数的正整数n n和和r r有有P(n, r)= nP(n, r)= n(n -1) (n -(r-1)(n -1) (n -(r-1)第第r r位位第第r-1
19、r-1位位第第3 3位位第第2 2位位第第1 1位位n nn-1n-1n-2n-2 n-(r-2)n-(r-2)n-(r-1)n-(r-1)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1717推论推论2.3.22.3.2n n个不同元素的排列共有个不同元素的排列共有n n！种，其中！种，其中 n!= nn!= n(n -1)(n -1)221 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1818例例2.3.22.3.2 A,B,C,D,E,F A,B,C,D,E,F组成的排列中，组成的排列中， （1 1）
20、有多少含有）有多少含有DEFDEF的子串？的子串？（2 2）三个字母）三个字母D D、E E和和F F相连的有多少种？相连的有多少种？解解 (1)(1)将将DEFDEF看成一个对象看成一个对象，根据推论，根据推论2.3.22.3.2，满足条件，满足条件的排列为的排列为A,B,C,DEFA,B,C,DEF的全排列，共有的全排列，共有4 4！=24=24种；种；（2 2）根据题意，满足该条件的排列分为两步：第一步）根据题意，满足该条件的排列分为两步：第一步确定确定D, ED, E和和F F三个字母的全排列三个字母的全排列，有，有3 3！种排列，第二步！种排列，第二步将将已排序的已排序的D, ED,
21、 E和和F F看成一个整体看成一个整体，与，与A, BA, B和和C C共共4 4个元个元素构造出素构造出A, B, C, D, E, FA, B, C, D, E, F的全排列，有的全排列，有4 4！种排列。！种排列。又根据乘法原理，满足条件的排列总数有又根据乘法原理，满足条件的排列总数有3 3！4 4！=144=144。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-1919例例2.3.32.3.36 6个人围坐在圆桌上，有多少种不同的坐法？通过个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。转圈得到的坐法视为同一种坐法。解解
22、 6 6个人围坐在圆桌上，个人围坐在圆桌上，有有120120种不同的坐法。种不同的坐法。A AE EF FB BD DC C电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-2020定理定理2.3.32.3.3含含n n个不同元素的集合的个不同元素的集合的环形环形r-r-排列数排列数P Pc c(n,r)(n,r)是是c cP(n, r)n!P(n, r)n!P(n, r)=P(n, r)=rrrr(n -r)!(n -r)!电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-2121例例2.3.42.3.4求满足下列条
23、件的排列数。求满足下列条件的排列数。( (1)101)10个男孩和个男孩和5 5个女孩个女孩站成一排站成一排，无两个女孩相邻无两个女孩相邻。(2)10(2)10个男孩和个男孩和5 5个女孩个女孩站成一圆圈站成一圆圈，无两个女孩相邻无两个女孩相邻. .解解 (1)(1)根据推论根据推论2.3.22.3.2，1010个男孩的全排列为个男孩的全排列为10!10!，5 5个女孩插入到个女孩插入到1010个男孩形成的个男孩形成的1111个空格中的插入方法个空格中的插入方法数为数为P(11, 5)P(11, 5)。根据乘法原理，。根据乘法原理，1010个男孩和个男孩和5 5个女孩个女孩站成一排，没有两个女
24、孩相邻的排列数为：站成一排，没有两个女孩相邻的排列数为：10!10! P(11, 5) = P(11, 5) =（10!10!11!)/6! 11!)/6! 。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-2222例例2.3.4 2.3.4 解（续）解（续）（2 2） 根据定理根据定理2.3.32.3.3，1010个男孩站成一个圆圈的个男孩站成一个圆圈的环排列数为环排列数为9 9！，！，5 5个女孩插入到个女孩插入到1010男孩形成的男孩形成的1010个个空中的插入方法数为空中的插入方法数为P(10, 5)P(10, 5)。根据乘法原理，。根据乘法原理
25、，1010个男孩和个男孩和5 5个女孩站成一个圆圈，没有两个女孩相个女孩站成一个圆圈，没有两个女孩相邻的排列法为：邻的排列法为：电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-23232.3.2 2.3.2 组合问题组合问题定义定义2.3.22.3.2 从含有从含有n n个不同元素的集合个不同元素的集合S S中无序选中无序选取的取的r r个元素叫做个元素叫做S S的一个的一个r -r -组合组合，不同的组合总，不同的组合总数记为数记为C(n, r)C(n, r)。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-24
26、24定理定理2.3.42.3.4对满足对满足0 r n0n)m(mn)个鸽笼，则个鸽笼，则存在一个存在一个鸽鸽笼笼至少住至少住进进 只鸽子。这里，只鸽子。这里， 表表示小于等于示小于等于x x的最大整数。的最大整数。n -1n -1+1+1m mx x电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-4646例例2.4.62.4.6如果一个图书馆里如果一个图书馆里3030本离散数学书共有本离散数学书共有12031203页，那页，那么必然有一本离散数学书至少有么必然有一本离散数学书至少有4141页。页。证明证明 设页是鸽子，离散数学书是鸽笼，把每页分设页是鸽
27、子，离散数学书是鸽笼，把每页分配到它所出现的离散数学书中，根据定理配到它所出现的离散数学书中，根据定理2.4.52.4.5，则存在一个鸽笼至少住进则存在一个鸽笼至少住进 = 41= 41，即结论得证。即结论得证。( (1 12 20 03 3- -1 1) )/ /3 30 0 + +1 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-47472.52.5 离散概率简介离散概率简介 概率概率(Probability)(Probability)是是1717世纪为分析博弈游戏世纪为分析博弈游戏而发展起来的学科，最初计算概率仅有计数一种方而发展起来的学科，最
28、初计算概率仅有计数一种方法。法。 本节主要介绍离散概率的基本概率、基本性质本节主要介绍离散概率的基本概率、基本性质和概率计算的简单例子。和概率计算的简单例子。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-48482.5.1 2.5.1 基本概念基本概念问题问题：掷出一个各面同性的骰子，求掷出偶数的概掷出一个各面同性的骰子，求掷出偶数的概率。率。其中其中“各面同性各面同性”是指当骰子掷出时，各个面是指当骰子掷出时，各个面出现的机会均等。出现的机会均等。定义定义2.5.12.5.1 能生成结果的过程称为能生成结果的过程称为实验实验(experiment)(
29、experiment)；实验的结果或结果的组合称为实验的结果或结果的组合称为事件事件(event)(event)，包含所有可能结果的事件称为包含所有可能结果的事件称为样本空间样本空间(sample (sample space)space)。 假如骰子的六个面分别标记为假如骰子的六个面分别标记为1, 2, 3, 4, 5, 61, 2, 3, 4, 5, 6，当掷出一个骰子时，一定能掷出当掷出一个骰子时，一定能掷出6 6种结果中的一种，种结果中的一种，我们称我们称掷出骰子的过程为掷出骰子的过程为，掷出的结果掷出的结果( (假如假如掷出掷出2)2)或或结果的组合结果的组合( (假如掷出两个骰子，一
30、个掷假如掷出两个骰子，一个掷出出1 1，一个掷出，一个掷出3)3)称为称为，当掷出一个骰子时得当掷出一个骰子时得到的到的6 6种可能种可能1, 2, 3, 4, 5, 61, 2, 3, 4, 5, 6称为称为。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-4949例例2.5.12.5.1请举例说明下列实验可能发生的事件，并列出其样请举例说明下列实验可能发生的事件，并列出其样本空间。本空间。（1 1）掷出一个六个面的骰子；）掷出一个六个面的骰子；（2 2）从）从10001000个微处理器中随机抽取个微处理器中随机抽取5 5个；个；（3 3）在北京人民
31、医院选取一个婴儿。）在北京人民医院选取一个婴儿。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5050例例2.5.1 2.5.1 可能发生的事件举例如下：可能发生的事件举例如下：（1 1）掷出一个六个面的骰子，得到的点数是）掷出一个六个面的骰子，得到的点数是4 4；（2 2）从）从10001000个微处理器中随机抽取个微处理器中随机抽取5 5个，没有发现个，没有发现次品；次品；（3 3）在北京人民医院选取了一个女婴。）在北京人民医院选取了一个女婴。各实验的样本空间为：各实验的样本空间为：（1 1）1, 2, 3, 4, 5, 61, 2, 3, 4,
32、 5, 6；（2 2）从）从10001000个微处理器中选取个微处理器中选取5 5个的所有组合；个的所有组合；（3 3）北京人民医院的所有婴儿。）北京人民医院的所有婴儿。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5151定义定义2.5.22.5.2有限样本空间有限样本空间S S中的事件中的事件E E的概率的概率P(E)P(E)定义为：定义为：其中其中|E|, |S|E|, |S|分别表示集合分别表示集合E E和和S S的基数。的基数。E EP(E)=P(E)=S S电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-6
33、7-5252例例2.5.22.5.2掷出一个各面同性的骰子，求掷出偶数的概率。掷出一个各面同性的骰子，求掷出偶数的概率。解解 设掷出偶数这个事件为设掷出偶数这个事件为E E，样本空间为，样本空间为S S，则根，则根据题意据题意|E| = 3, |S| = 6|E| = 3, |S| = 6。代入式。代入式(2.5.1)(2.5.1)，得，得P(E) = 3/6 = 1/2P(E) = 3/6 = 1/2。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5353例例2.5.32.5.3掷出两个各面同性的骰子，求点数之和为掷出两个各面同性的骰子，求点数之和为
34、1010的概率。的概率。解解 设点数之和为设点数之和为1010这个事件为这个事件为E E，样本空间为，样本空间为S S，则根据题意则根据题意|E| = 3, |S| = 36|E| = 3, |S| = 36。代入式。代入式(2.5.1)(2.5.1)，得得P(E) = 3/36 = 1/12 P(E) = 3/36 = 1/12 。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5454例例2.5.42.5.4在福利彩票中，若彩民从在福利彩票中，若彩民从1 15252个数中选取的个数中选取的6 6个数个数与随机生成的中奖数字相同与随机生成的中奖数字相同
35、( (不计顺序不计顺序) )，则可以赢，则可以赢得大奖。求一张彩票赢得大奖的概率。得大奖。求一张彩票赢得大奖的概率。解解 从从5252个数字中选取个数字中选取6 6个共有个共有C(52, 6)C(52, 6)种选法，即种选法，即|S| = C(52, 6)|S| = C(52, 6)，而得大奖的组合只有一种，即，而得大奖的组合只有一种，即|E| = 1|E| = 1，根据概率的定义，得：，根据概率的定义，得：P(E) = 1/ C(52, 6) = 0.00000004P(E) = 1/ C(52, 6) = 0.00000004。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课
36、程国家精品课程67-67-55552.5.2 2.5.2 离散概率函数离散概率函数定义定义2.5.32.5.3 如果函数如果函数P P将样本空间将样本空间S S的每一个结果的每一个结果x x映射为实数映射为实数P(x)P(x)，且对任意的，且对任意的xSxS，满足，满足（1 1）0P(x)10P(x)1； （2 2） 。则称函数则称函数P P是概率函数是概率函数。x x S SP P( (x x) )= =1 1说明说明 条件条件(1)(1)保证一个结果的概率为非负数且不超过保证一个结果的概率为非负数且不超过1 1；条件条件(2)(2)保证所有结果的概率之和为保证所有结果的概率之和为1 1，即
37、进行实验，即进行实验后，必出现某个结果。后，必出现某个结果。 电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5656例例2.5.52.5.5一个一面较重的骰子，一个一面较重的骰子，2 26 6以相同的机会出现，以相同的机会出现，1 1出现的机会是其他数字的出现的机会是其他数字的3 3倍。试求出倍。试求出1 16 6的概率的概率函数值。函数值。解解 设设P(2) = P(3) = P(4) = P(5) = P(6) = aP(2) = P(3) = P(4) = P(5) = P(6) = a，则则P(6) = 3aP(6) = 3a。又因为。又因为P
38、(1)+ P(2)+ P(3)+ P(4)+ P(1)+ P(2)+ P(3)+ P(4)+ P(5)+ P(6) = 1P(5)+ P(6) = 1，所以有，所以有5a5a3a = 13a = 1，即，即a = 1/8a = 1/8。从而从而P(2) = P(3) = P(4) = P(5) = P(6) =1/8 P(2) = P(3) = P(4) = P(5) = P(6) =1/8 ，P(6) =3/8P(6) =3/8。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5757概率函数概率函数定义定义2.5.42.5.4 设设E E是一个事件，
39、是一个事件，E E的概率函数的概率函数P(E)P(E)定定义为义为 。在例在例2.5.52.5.5中，出现奇数点的概率则为中，出现奇数点的概率则为P(1)+ P(3)+ P(5) =5/8 P(1)+ P(3)+ P(5) =5/8 。定理定理2.5.12.5.1 设设E E是一个事件，是一个事件，E E的补的概率满足的补的概率满足x Ex EP(E)=P(x)P(E)=P(x) P P( (E E) )+ + P P E E = =1 1电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5858例例2.2.6 2.2.6 生日问题生日问题n n个人中，个
40、人中，求至少有两个人生日相同求至少有两个人生日相同( (同月同日不计同月同日不计年年) )的概率。的概率。假定出生在某天的概率均等，忽略假定出生在某天的概率均等，忽略2 2月月2929日。日。解解 设设E E表示表示“至少两个人生日相同至少两个人生日相同”，则表示，则表示“没有两个人生日相同没有两个人生日相同”，则，则 从而从而 n n3 3 6 6 5 5 3 3 6 6 4 4 ( ( 3 3 6 6 5 5 - - n n + + 1 1 ) )P PE E= =3 3 6 6 5 5n n3 36 65 5 3 36 64 4( (3 36 65 5 - - n n + + 1 1)
41、)P P( (E E) )= = 1 1- -3 36 65 5事实上，事实上，随着天数随着天数n n的增加，至少两个人的增加，至少两个人生日相同的概率也随着增加生日相同的概率也随着增加，当，当n23n23时，时，至少有两个人生日相同的概率大于至少有两个人生日相同的概率大于1/21/2。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-5959两个事件并的概率两个事件并的概率定理定理2.5.22.5.2 设设E E1 1和和E E2 2是两个事件，则是两个事件，则 P(EP(E1 1EE2 2)=P(E)=P(E1 1) )P(EP(E2 2) )P(EP
42、(E1 1EE2 2) ) (2.5.3)(2.5.3)如果如果E E1 1EE2 2= =，即，即E E1 1与与E E2 2为不相交的事件，则有下为不相交的事件，则有下面的推论。面的推论。推论推论2.5.32.5.3 设设E E1 1和和E E2 2是两个不相交的事件，则是两个不相交的事件，则 P(EP(E1 1EE2 2) = P(E) = P(E1 1) )P(EP(E2 2) ) (2.5.4)(2.5.4)电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6060例例2.5.72.5.7掷出两个各面同性的骰子，得到掷出两个各面同性的骰子，得到“
43、一对一对”( (两个骰两个骰子点数相同子点数相同) )或点数和为或点数和为6 6的概率是多少？的概率是多少？解解 设设E E1 1表示事件表示事件“一对一对”，E E2 2表示事件表示事件“点数和点数和为为6”6”，则样本空间大小是，则样本空间大小是3636，事件事件E E1 1的种数为的种数为6,6,即即(1,1),(2, 2),(3,3),(4,4),(5,5),(6,6),(1,1),(2, 2),(3,3),(4,4),(5,5),(6,6),事件事件E2E2的种数为的种数为5 5，即即(1,5),(2,4),(3,3),(4,2),(5, 1)(1,5),(2,4),(3,3),(4
44、,2),(5, 1)。 E1E2E1E2的种数为的种数为1 1。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6161例例2.5.7 2.5.7 解（续）解（续）从而从而 P(EP(E1 1) =1/6 , P(E) =1/6 , P(E2 2) = 5/36, P(E) = 5/36, P(E1 1EE2 2) = ) = 1/36 1/36 。根据式根据式(2.5.3)(2.5.3)，有，有 P(EP(E1 1EE2 2)=1/6)=1/65/365/361/36=5/181/36=5/18 。即得到即得到“一对一对”或点数和为或点数和为6 6的概
45、率是的概率是5/18 5/18 。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-62622.62.6 递归关系递归关系递归关系递归关系可用于解决一些特定的计数问题。可用于解决一些特定的计数问题。递归关系是序列中递归关系是序列中第第n n个元素与它相邻前若干个元个元素与它相邻前若干个元素之间的关系素之间的关系。例如例如1 1、第一个数是、第一个数是5 5；2 2、将前一项加、将前一项加3 3得到后一项。得到后一项。 5, 8, 11, 14, 5, 8, 11, 14, 递归关系递归关系电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家
46、精品课程67-67-6363定义定义2.6.12.6.1对序列对序列a a0 0, a, a1 1, a, a2 2, , ,a,an - 1n - 1, , ，用用a a0 0,a,a1 1,a,a2 2, , ,a,an - 1n - 1中的中的某些项某些项表示表示a an n的等式称为的等式称为递归关系递归关系(recurrence relation)(recurrence relation)。显示地给出序。显示地给出序列列a a0 0, a, a1 1, a, a2 2, , 的有限项的值，称为的有限项的值，称为初始条件初始条件(initial condition)(initial c
47、ondition)。显然，递归关系和确定的初始条件一起，才能确定显然，递归关系和确定的初始条件一起，才能确定一个序列。一个序列。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6464例例2.6.12.6.1某人投资某人投资10001000元，每年可收益元，每年可收益1212。A An n表示他在第表示他在第n n年末的总资产年末的总资产。求出定义序列。求出定义序列AAn n 的递归关系和的递归关系和初始条件。初始条件。解解 序列序列AAn n 的的递归关系和初始条件递归关系和初始条件分别为：分别为： A An n = A= An - 1n - 10.1
48、20.12A An n -1-1= 1.12 A= 1.12 An n -1-1, n1 , , n1 , A A0 0 = 1000= 1000电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6565例例2.6.22.6.2S Sn n表示表示不含子串不含子串“111”111”的的n n位字符串的个数。求出位字符串的个数。求出序列序列SSn n 的递归关系和初始条件。的递归关系和初始条件。解解 序列序列SSn n 的的递归关系和初始条件递归关系和初始条件分别为：分别为： S Sn n = S = Sn-1n-1S Sn-2n-2 S Sn-3n-3，n
49、4, n4, S S1 1 = 2, S = 2, S2 2 = 4, S = 4, S3 3 = 7= 7。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-66662.7 2.7 计数问题的应用计数问题的应用例例2.7.12.7.1 7 7个科学工作者从事一项机密的技术研究，个科学工作者从事一项机密的技术研究，他们的工作室装有电子锁，每位科学工作者都有打开他们的工作室装有电子锁，每位科学工作者都有打开电子锁用的电子锁用的“钥匙钥匙”。为了安全起见，。为了安全起见，必须有必须有4 4位在场位在场时才能打开大门时才能打开大门。试问该电子锁。试问该电子锁至少
50、应具备多少个特至少应具备多少个特征征？每位科学工作者的？每位科学工作者的“钥匙钥匙”至少应有多少种特征？至少应有多少种特征？解解 为了使任意为了使任意3 3个人在场时至少缺少一个特征而打不个人在场时至少缺少一个特征而打不开门，该电子锁应具备开门，该电子锁应具备C(7,3)=35C(7,3)=35种特征；每个科学工种特征；每个科学工作者的作者的“钥匙钥匙”至少要有至少要有C(6,3)= 20C(6,3)= 20种特征。种特征。电子科技大学离散数学课程组电子科技大学离散数学课程组国家精品课程国家精品课程67-67-6767例例2.7.22.7.2某一制造铁盘的工厂，由于设备和技术的原因只能某一制造
