[工学]离散数学-第02章-计数问题.ppt

《[工学]离散数学-第02章-计数问题.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学02九月20212021/9/2第一篇预备知识第2章计数问题2021/9/22.0内容提要容斥原理与鸽笼原理3乘法原理和加法原理1排列与组合22021/9/22.1本章学习要求重点掌握一般掌握了解11计算排列组合2利用容斥原理计算集合基数3计数问题的应用2鸽笼原理的简单应用2021/9/22.2.1乘法原理如果一些工作需要t步完成，第一步有n1种不同的选择，第二步有n2种不同的选择，…，第t步有nt种不同的选择，那么完成这项工作所有可能的选择种数为：2021/9/22.2.2加法原理假定X1,X2,…,Xt均为集合，第I个集合Xi有ni个元素。如{X1,X

2、2,…,Xt}为两两不相交的集合，则可以从X1,X2,…,Xt中选出的元素总数为：n1+n2+…+nt。即集合X1∪X2∪…∪Xt含有n1+n2+…+nt个元素。2021/9/22.3排列与组合从某个集合中有序的选取若干个元素的问题，称为排列问题。2021/9/22.3.1排列问题定义2.3.1从含n个不同元素的集合S中有序选取的r个元素叫做S的一个r-排列，不同的r-排列总数记为P(n,r)。如果r=n，则称这个排列为S的一个全排列，简称为S的排列。显然，当r>n时，P(n,r)=0。2021/9/2例2.3.1解从含3个元素的不同集合S中有序选取2个元素的排列

3、总数为6种。如果将这3个元素记为A、B和C，则6个排列为AB,AC,BA,BC,CB,CA。从含3个不同元素的集合S中有序选取2个元素的排列总数。2021/9/2定理2.3.1对满足r≤n的正整数n和r有第r位第r-1位第3位第2位第1位nn-1n-2……n-(r-2)图2.3.1n-(r-1)2021/9/2推论2.3.2n个不同元素的排列共有n！种，其中2021/9/2练习:P443,4,63.一枚硬币抛4次并且每次抛掷结果被记录下来。问可能有多少种不同的正面和反面的序列?答:24=16种。4.某人有8件衬衫、4条裤子、5双鞋，全套衣服用有多少种可能的选择？答

4、：8×4×5＝160种。6.P(4,4)=4×3×2×1=24P(6,5)=6×5×4×3×2=720，P(7,2)=7×6=42。2021/9/2环形r-排列例2.3.36个人围坐在圆桌上，有多少种不同的坐法？通过转圈得到的坐法视为同一种坐法。解:6个人围坐在圆桌上，有6!/6=120种不同的坐法。图2.3.2AEFBDCn个人围坐圆桌上，有(n-1)！种不同的坐法，我们称这种排列为环排列;从n个人中选出r个人围圆桌而坐，称为环形r-排列。2021/9/2定理2.3.3含n个不同元素的集合的环形r-排列数Pc(n,r)是(2.3.3)2021/9/2例2.3.4

5、求满足下列条件的排列数。(1)10个男孩和5个女孩站成一排，无两个女孩相邻。(2)10个男孩和5个女孩站成一圆圈,无两个女孩相邻.解(1)10个男孩的全排列为10!，5个女孩插入到10个男孩形成的11个空格中的插入方法数为P(11,5)。根据乘法原理，10个男孩和5个女孩站成一排，没有两个女孩相邻的排列数为：10!×P(11,5)=（10!×11!)/6!。2021/9/2例2.3.4解（续）(2)根据定理2.3.3，10个男孩站成一个圆圈的环排列数为9!，5个女孩插入到10男孩形成的10个空中的插入方法数为P(10,5)。根据乘法原理，10个男孩和5个女孩站成一

6、个圆圈，没有两个女孩相邻的排列法为：9!×P(10,5)=（9!×10!)/5!。2021/9/22.3.2组合问题定义2.3.2从含有n个不同元素的集合S中无序选取的r个元素叫做S的一个r-组合，不同的组合总数记为C(n,r)。当n≥r=0时，规定C(n,r)=1。显然，当r>n时，C(n,r)=0。2021/9/2定理2.3.4对满足0

7、少种可能的组合？解:有C(52,5)种可能的组合。2021/9/2（2）一手牌中的5张都是同一花色，共有多少种可能的组合？解：分两步进行：一选花色，有C(4,1)种，二在选定的花色中选5张牌，有C(13,5)种。据乘法原理，有C(4,1)×C(13,5)种。2021/9/2（3）一手牌中有3张牌点数相同，另外两张牌点数相同，共有多少种可能的组合？解：该组合问题需四步完成：一选第一个点数，有C(13,1)种；二选第二个点数，有C(12,1)种：三选第一点数的3张牌，有C(4,3)种；四选第二点数的2张牌，有C(4,2)种。根据乘法原理，共有C(13,1)×C(12,

8、1)×C(