第2章计数问题北极熊校园

1、1广东工业大学计算机学院广东工业大学计算机学院-离散数学离散数学离离 散散 数数 学学蔡瑞初蔡瑞初20222022年年2 2月月2626日星期六日星期六22022-2-262022-2-26第一篇第一篇 预备知识预备知识第第2 2章章 计数问题计数问题32022-2-262022-2-262.0 2.0 内容提要内容提要容斥原理与鸽笼原理容斥原理与鸽笼原理3离散概率离散概率4乘法原理和加法原理乘法原理和加法原理1排列与组合排列与组合2递归关系递归关系542022-2-262022-2-262.1 2.1 本章学习要求本章学习要求重点掌握重点掌握一般掌握一般掌握了解了解11 1乘法原理和加乘法原

2、理和加法原理法原理2 2排列组合的计排列组合的计算算 3 3利用容斥原理利用容斥原理计算有限集合的计算有限集合的交与并交与并 31 1 离散概率离散概率2 2 离散概念的计离散概念的计 算公式及性质算公式及性质 21 1 鸽笼原理鸽笼原理2 2 鸽笼原理的简鸽笼原理的简单应用单应用3 3 递归关系递归关系4 4 递归关系的建递归关系的建立和计算立和计算 52022-2-262022-2-262.2.1 2.2.1 乘法原理乘法原理 如果一些工作需要如果一些工作需要t t步完成步完成，第一步有，第一步有n n1 1种种不同的选择，第二步有不同的选择，第二步有n n2 2种不同的选择，种不同的选择

3、， ，第第t t步有步有n nt t种不同的选择，那么完成这项工作所种不同的选择，那么完成这项工作所有可能的选择种数为：有可能的选择种数为：tnnn2162022-2-262022-2-26例例2.2.32.2.3在一幅数字图像中，若在一幅数字图像中，若每个像素点用每个像素点用8 8位进行编码位进行编码，问问每个点有多少种不同的取值。每个点有多少种不同的取值。分析分析 用用8 8位进行编码可分为位进行编码可分为8 8个步骤：选择第一位，个步骤：选择第一位，选择第二位，选择第二位， ，选择第八位。每一个位有两种，选择第八位。每一个位有两种选择，故根据乘法原理，选择，故根据乘法原理，8 8位编码共

4、有位编码共有2 22 22 22 22 22 22 22 = 22 = 28 8 = 256 = 256种取值。种取值。解解 每个点有每个点有256( = 2256( = 28 8) ) 种不同的取值。种不同的取值。 72022-2-262022-2-262.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, ,

5、 , X, Xt t中选出的元素总数为：中选出的元素总数为：n n1 1 + n + n2 2 + + + n + nt t。82022-2-262022-2-26例例2.2.42.2.4由由AliceAlice、BenBen、ConnieConnie、DolphDolph、EgbertEgbert和和FranciscoFrancisco六个人组成的委员会六个人组成的委员会，要，要选出一个主席、选出一个主席、一个秘书和一个出纳员。一个秘书和一个出纳员。若若主席必须从主席必须从AliceAlice和和BenBen种选出种选出，共有多少种选法？，共有多少种选法？92022-2-262022-2-2

6、6例例2.2.4 2.2.4 解解 若若AliceAlice被选为主席，共有被选为主席，共有5 54 = 204 = 20种方法确定其种方法确定其他职位；若他职位；若BenBen为主席，同样有为主席，同样有2020种方法确定其他种方法确定其他职位。由于两种选法得到的集合不相交，所以根据职位。由于两种选法得到的集合不相交，所以根据加法原理加法原理，共有，共有202020 = 4020 = 40种选法；种选法；102022-2-262022-2-262.3.1 2.3.1 排列问题排列问题定义定义2.3.12.3.1 从含从含n n个不同元素个不同元素的集合的集合S S中中有序有序选取选取的的r

7、r个元素叫做个元素叫做S S的一个的一个，不同的排列总数，不同的排列总数记为记为P(n, r)P(n, r)。如果。如果r = nr = n，则称这个排列为，则称这个排列为S S的一的一个个，简称为，简称为S S的排列。的排列。显然显然， 112022-2-262022-2-26定理定理2.3.12.3.1对满足对满足rnrn的正整数的正整数n n和和r r有有P(n,r)n (n1)(n(r1)第r位第第r-1r-1位位第第3 3位位第第2 2位位第第1 1位位nn-1n-2 n-(r-2)图2.3.1n-(r-1)n-(r-1)122022-2-262022-2-26例例2.3.22.3.

8、2 A,B,C,D,E,F A,B,C,D,E,F组成的排列中，组成的排列中， （1 1）有多少含有）有多少含有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三个字母的全排列三个

9、字母的全排列，有，有3 3！种排列，第二步！种排列，第二步将将已排序的已排序的D, ED, 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。132022-2-262022-2-262.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)。142022-2-262022-2-26