组合数学PPT第一章排列与组合

1、第第1章章排列与组合排列与组合2022-7-82组合数学组合数学n组合数学是研究离散结构的存在、计数、分析和组合数学是研究离散结构的存在、计数、分析和优化的一门学科。优化的一门学科。n应用领域应用领域: 计算机科学、概率论、社会科学、生计算机科学、概率论、社会科学、生物科学、信息论等。物科学、信息论等。n参考书：参考书： 1. R.A.Rrualdi. Introductory Combinatorics 组合数学组合数学 机械工业出版社机械工业出版社 2. 孙淑玲孙淑玲 许胤龙许胤龙. 组合数学引论组合数学引论 中国科学技术大中国科学技术大学出版社学出版社2022-7-831.1基本计数法则

2、基本计数法则n1.1 基本计数法则基本计数法则n加法法则：设事件加法法则：设事件A有有m种产生方式，事件种产生方式，事件B有有n种产生方式，则种产生方式，则“事件事件A或事件或事件B”有有m+n种种产生方式。产生方式。n例例. 一位学生想选修一门数学课程或一门生物一位学生想选修一门数学课程或一门生物课程。若有课程。若有4门数学课程和门数学课程和3门生物课程，则该门生物课程，则该学生有学生有4+3=7种不同的选课方式。种不同的选课方式。2022-7-841.1基本计数法则基本计数法则n乘法法则：设事件乘法法则：设事件A有有m种产生方式，事件种产生方式，事件B有有n种产生方式，则种产生方式，则“事

3、件事件A与事件与事件B”有有mn种产种产生方式。生方式。n例例1.1 设一个符号由两个字符组成，第设一个符号由两个字符组成，第1个字符个字符由由a,b,c,d,e组成，第组成，第2个字符由个字符由1,2,3组成，则由组成，则由乘法法则，该符号有乘法法则，该符号有 种方式种方式。1535 2022-7-85 例例1.3 求求比比10000小的正整数中含有数字小的正整数中含有数字1的数的的数的个数。个数。 解解 比比10000小的正整数可以写为小的正整数可以写为 的形式。的形式。l 共有共有104-1=9999个个l 其中不含其中不含1的正整数有的正整数有 94-1=6560个个l 所求正整数的个

4、数为所求正整数的个数为 9999-6560=3439个。个。1.1 基本计数法则基本计数法则90 ,4321 iaaaaa2022-7-86例例1.4 求长度为求长度为n的二元码的数目。的二元码的数目。 解解 长度为长度为n的二元码的形式为的二元码的形式为 由乘法法则，长度为由乘法法则，长度为n的二元码的数目为的二元码的数目为 1.1 基本计数法则基本计数法则niaaaain, 2 , 1,1 , 0,21 n22222 2022-7-87例例1.6 求布尔函数求布尔函数 的数目。的数目。 解解 自变量自变量 可能取值的个数为可能取值的个数为 设取值为设取值为 则则n n个变元的布尔函数有个变

5、元的布尔函数有 个。个。 1.1 基本计数法则基本计数法则),(21nxxxf),(21nxxxn2naa21,，naa21 n222 2 f2022-7-881.1 基本计数法则基本计数法则n例例 1.8 ，求能整除，求能整除n的正整数的正整数的个数。的个数。 解解 能整除能整除n的正整数可以写为如下形式：的正整数可以写为如下形式： 故能整除故能整除n的正整数的个数为的正整数的个数为 42313117 n40 , 20 , 30 aaaaaa60534 2022-7-89例例1.9 求从求从a,b,c,d,e这这5个字母中取个字母中取6个所组成的字符个所组成的字符串

6、个数。要求串个数。要求(1)第第1 1个和第个和第6个字符必为子音字符；个字符必为子音字符；(2)每一字符串必有两个母音字符，且两个母音字母每一字符串必有两个母音字符，且两个母音字母不相邻；不相邻；(3) 相邻的两个子音字符必不相同。相邻的两个子音字符必不相同。 解解 符合要求的字符串有以下几种模式：符合要求的字符串有以下几种模式： 所求的字符串个数为：所求的字符串个数为： 个。个。 1.1 基本计数法则基本计数法则 64832333 2022-7-810例例 设某地的街道把城市分割成矩形方格，每个设某地的街道把城市分割成矩形方格，每个方格叫做它的块。某甲从家中出发上班，向东要方格叫做它的块。

7、某甲从家中出发上班，向东要走过走过m块，向北要走过块，向北要走过n块，问某甲上班的路径有块，问某甲上班的路径有多少条？多少条？ 解解 问题可划为求右图从点问题可划为求右图从点 (0,0)到到(m,n)的路径数的路径数: : 每一条从点每一条从点(0,0)到到(m,n)的路径与的路径与 一个由一个由m个个x和和n个个y的排列相对应的排列相对应 所求路所求路径数为：径数为： 1.2 一一对应一一对应 (0 0,0 0) (m,n)xy),(mnmC 2022-7-811定理定理（Cayley）n个有标号的顶点的树的数目等个有标号的顶点的树的数目等于于 。 例例1.12 给定下列树给定下列树 可得序

8、列可得序列: 3,1,5,5,1。反之从序列。反之从序列3,1,5,5,1也可以也可以构造出上述树。构造出上述树。 1.2 1.2 一一对应一一对应2 nn23754612022-7-812n定义：从定义：从n个不同的元素中，取出个不同的元素中，取出r个按次序排成个按次序排成一列，称为从这一列，称为从这n个元素中取个元素中取r个的一个排列，其个的一个排列，其排列数记为排列数记为 . . n由定义显然有由定义显然有 (1) (2) 当当r=n时有时有, , 1.3 排列排列),(rnP10! ,)!(!)1()1(),( rnnrnnnrnP)( , 0),(nrrnP )1( ,)1 ,( n

9、nnP!12)1(),(nnnnnP 2022-7-813例例1.13 由由5种颜色的星状物，种颜色的星状物，20种不同的花排成种不同的花排成如下的图案：两边是星状物，中间是如下的图案：两边是星状物，中间是3朵花，问朵花，问共有多少种这样的图案？共有多少种这样的图案？ 解解 图案的形状为图案的形状为 共有共有 种图案。种图案。 1.3 排列排列136800)3 ,20()2 , 5()181920()45( PP2022-7-814例例1.14 A单位有单位有7位代表，位代表，B单位有单位有3位代表，排在位代表，排在一列合影，要求一列合影，要求B单位的人排在一起，问有多少单位的人排在一起，问有

10、多少种不同的排列方案？种不同的排列方案？解解 B单位的某一排列作为一个元素参加单位单位的某一排列作为一个元素参加单位A进进行排列，可得行排列，可得 种排列。种排列。 B单位的单位的3人共有人共有 个排列，个排列， 故共有故共有 排列方案。排列方案。1.3 排列排列! 8! 3! 38 2022-7-815例例1.15 若例若例1.14中中A单位的两人排在两端，单位的两人排在两端，B单位单位的的3人不能相邻，问有多少种不同的排列方案？人不能相邻，问有多少种不同的排列方案？解解 共有共有 种方案。种方案。 1.3 排列排列604800)456(!7 2022-7-816例例1.16 求求20000

11、到到70000之间的偶数中由不同的数之间的偶数中由不同的数字所组成的字所组成的5位数的个数。位数的个数。 解解 设所求的数的形式为设所求的数的形式为 其中其中 (1)若若 ，这时，这时e有有4种选择，有种选择，有 (2)若若 ，这时，这时e有有5种选择，有种选择，有 共有共有 个。个。 1.3 排列排列abcde8 , 6 , 4 , 2 , 0, 62 ea 6 , 4 , 2 a4032)3 , 8(43 P5 , 3 a3360)3 , 8(52 P739233604032 2022-7-817从从n个对象中取个对象中取r个沿一圆周排列的排列数用个沿一圆周排列的排列数用 表示，则有表示，

12、则有 abcd, dabc, cdab, bcda特别地特别地， 1.4 圆周排列圆周排列),(rnQrrnPrnQ),(),( )!1(!),(),( nnnnnnPnnQabcd2022-7-818例例1.19 5颗红色的珠子，颗红色的珠子，3颗蓝色的珠子装在圆板颗蓝色的珠子装在圆板的四周，试问有多少种排列方案？若蓝色的珠子的四周，试问有多少种排列方案？若蓝色的珠子不相邻又有多少种排列方案？蓝色珠子在一起又不相邻又有多少种排列方案？蓝色珠子在一起又如何？如何？ 解解 (1)有有 种；种； (2)有有 种；种； (3)有有 种。种。1.4 圆周排列圆周排列! 71440)345(! 4 !

13、35 2022-7-819例例1.20 5对夫妻出席一宴会，围一圆桌坐下，问对夫妻出席一宴会，围一圆桌坐下，问有几种方案？若要求每对夫妻相邻又有多少种方有几种方案？若要求每对夫妻相邻又有多少种方案？案？ 解解 (1) 种方案；种方案； (2) 种方案。种方案。1.4 圆周排列圆周排列! 97683224245 !2022-7-820定义定义 从从n个不同的元素中，取出个不同的元素中，取出r个而不考虑其个而不考虑其次序，称为从这次序，称为从这n个元素中取个元素中取r个组合，其组合数个组合，其组合数记为记为 。 1.5 组合组合),(rnC!),(),(rrnCrnP !),(),(rrnPrnC

14、 2022-7-821例例1.21 从从1300之间任取之间任取3个不同的数，使得这个不同的数，使得这3个数个数的和正好被的和正好被3除尽，问共有几种方案？除尽，问共有几种方案？ 解解 将这将这300个数按照其被个数按照其被3除所得的余数分为三组：除所得的余数分为三组： A=1,4,298，B=2,5,299，C=3,6,300 三个数取自集合三个数取自集合A：有：有C(100,3)种方案；种方案； 三个数取自集合三个数取自集合B：有：有C(100,3)种方案；种方案； 三个数取自集合三个数取自集合C：有：有C(100,3)种方案；种方案； 三个数分别取自集合三个数分别取自集合A、B、C：有：

15、有1003种方案；种方案； 所求的方案数为：所求的方案数为：3C(100,3)+1003=1485100 1.5 组合组合2022-7-822例例1.22 甲和乙两单位共甲和乙两单位共11个成员，其中甲单位个成员，其中甲单位7人，乙单位人，乙单位4人，拟从中组成一个人，拟从中组成一个5人小组；人小组； (1) 若要求必须包含乙单位若要求必须包含乙单位2人；人； (2) 若要求至少包含乙单位若要求至少包含乙单位2人；人； (3) 若要求乙单位某一人与甲单位某一人不能同时若要求乙单位某一人与甲单位某一人不能同时在这个小组；在这个小组； 试分别求各有多少种方案。试分别求各有多少种方案。 解解 (1)

16、 (2) (3) 1.5 组合组合)3 , 7()2 , 4(CC)1 , 7()4 , 4()2 , 7()3 , 4()3 , 7()2 , 4(CCCCCC 37884462)3 , 9()5 ,11( CC2022-7-823例例1.23 假定有假定有8位成员，两两配对分成位成员，两两配对分成4组，问有组，问有多少种分配方案？多少种分配方案？解解 方法方法1： 将将8位成员排列，共有位成员排列，共有8!个排列，每个排列两个排列，每个排列两两划分，分成两划分，分成4组，其重复数为组，其重复数为24.4!，所求分配方，所求分配方案数为案数为 1.5 组合组合 105! 42! 84 202

17、2-7-824 方法方法2 2： 将将8 8个人分为个人分为4 4组，第组，第1 1组有组有 种选择，第种选择，第2 2组有组有 种选择，第种选择，第3 3组有组有 种选择，第种选择，第4 4组有组有 种选择，但由于各组与顺序无关，种选择，但由于各组与顺序无关，故所求分配方案数为：故所求分配方案数为：1.51.5 组合组合 4 3 2 1 ,)2 , 8(C),( 26C)2 , 4(C),( 22C! 42! 8! 4)2 , 2()2 , 4()2 , 6()2 , 8(4 CCCC2022-7-825例例1.24某广场有某广场有6个入口处，每个入口处每次只能个入口处，每个入口处每次只能通

18、过一辆汽车，有通过一辆汽车，有9辆汽车要开进广场，问有多辆汽车要开进广场，问有多少种入场方案？少种入场方案？解解 方法方法1： 9辆汽车和辆汽车和5个标志的一个排列可表示一种入场方个标志的一个排列可表示一种入场方案，其重复数为案，其重复数为5!，所求方案数为，所求方案数为 1.5 组合组合9 8 7 6 5 4 3 2 1 ! 5!142022-7-826方法方法2： 在在9辆汽车和辆汽车和5个标志共个标志共14个位置中，首先选择个位置中，首先选择5个个作为标志的位置，这有作为标志的位置，这有 种选择，对每一种选择，对每一种选择，将种选择，将9辆汽车依次填入剩余的位置，这有辆汽车依次填入剩余的

19、位置，这有 种填入方式，故所求方案数为种填入方式，故所求方案数为 1.5 组合组合)5 ,14(C! 9! 5!14! 9)5 ,14( C2022-7-827例例1.25 求求5位数中至少出现一个位数中至少出现一个6，而被，而被3整除的整除的数的个数。数的个数。 正整数正整数n能够被能够被3整除的的充要条件是整除的的充要条件是n的各个数的各个数字之和能够被字之和能够被3整除。整除。 设设 因为因为 ，所以，所以 于是于是 iff 1.5 组合组合0111101010aaaankkkk )3(mod 110 3) (mod 1010100110111aaaaaaaankkkkkk 3) 0(m

20、od n3) (mod 0011 aaaakk2022-7-828l5位数位数 共有共有90000个个l被被3整除的有整除的有30000个个l在这在这30000个数中不包含个数中不包含6的数有的数有 个个l所求个数为所求个数为 30000-17496=125041.5 组合组合174963983 54321aaaaa2022-7-829定理定理 在在n!中，质数中，质数p的最高幂的最高幂 其中其中 。 1.5 组合组合 mpnpnpnnp2) !(1 mmpnp2022-7-830例例6求求1000!的末尾有几个的末尾有几个0 解解 1000!的末尾所含的末尾所含0的个数为的个数为1000!的

21、因子分解的因子分解中中2和和5的幂的最小者的幂的最小者 1000!因子分解中因子分解中5的幂为：的幂为： 故故1000!的末尾有的末尾有249个个01.5 组合组合249184020051000510005100051000432 2022-7-831习题习题n1.2n1.4n1.5n1.8n1.92022-7-832允许重复的排列允许重复的排列n定理定理 多重集合多重集合 的的r排列数为排列数为n例例 用用26个英文字母可以构造出多少个个英文字母可以构造出多少个4个元音字母长个元音字母长度为度为8的字符串的字符串? 解解 该问题是要求该问题是要求 的包含的包含4个元个元音字母的音字母的8排列

22、数排列数. 在长度为在长度为8的字符串中的字符串中, 4个元音字母出现的位置有个元音字母出现的位置有 种种 每种元音出现的位置有每种元音出现的位置有 个排列个排列 所求字符串的个数为所求字符串的个数为,21kaaaS rk,zbaM )4 , 8(C44215)4 , 8( C44215 2022-7-833n定理定理 多重集合多重集合 的全排列数为的全排列数为 其中其中n证证 排列的个数为排列的个数为允许重复的排列允许重复的排列,2211kkanananS nnnnk 21!21knnnn),(),(),(121211kknnnnnCnnnCnnC !21knnnn 2022-7-834n例

23、例1.24某广场有某广场有6个入口处，每个入口处每次只能个入口处，每个入口处每次只能通过一辆汽车，有通过一辆汽车，有9辆汽车要开进广场，问有多少辆汽车要开进广场，问有多少种入场方案？种入场方案？n解解 方法方法1： 9辆汽车和辆汽车和5个标志的一个排列可表示一种入场方个标志的一个排列可表示一种入场方案，所求方案数为案，所求方案数为 允许重复的排列允许重复的排列9 8 7 6 5 4 3 2 1 ! 5!142022-7-835n 例例 从从1,2,3中取中取2个允许重复的组合为个允许重复的组合为 1,1, 1,2, 1,3, 2,2, 2,3, 3,3n定理定理1.2 在在n个不同的元素中取个

24、不同的元素中取r个进行组合，若允个进行组合，若允许重复，则组合数为许重复，则组合数为 证证 设设n个不同的元素为个不同的元素为1,2,3,n 若若 是一个允许重复的是一个允许重复的r组合，不妨设组合，不妨设 ，可构造一个可构造一个 上的不上的不 允许重复的允许重复的r组合组合1.8.1 允许重复的组合允许重复的组合),(rrnC1 ,raaa21raaa 21,121 rn,1121 raaar2022-7-8361.8 1.8 允许重复的组合允许重复的组合n反之给定一个反之给定一个 上的不允许重复的上的不允许重复的r组组合合 ，我们可以如下得到一个我们可以如下得到一个1,2,n上的上的一个允

25、许重复的一个允许重复的r组合组合 。 故故n个元素的允许重复的个元素的允许重复的r组合与组合与n+r-1个元素的不允个元素的不允许重复的组合之间有一一对应关系，故它们的组合数许重复的组合之间有一一对应关系，故它们的组合数相同，于是定理得证。相同，于是定理得证。,121 rn,rbbb21,1121 rbbbr2022-7-837n定理定理1.3 r个无区别的球放进个无区别的球放进n个有标志的盒子，而每个有标志的盒子，而每盒放的球可多于一个，则共有盒放的球可多于一个，则共有 种方案种方案n例例1.28 试问试问 有多少项？有多少项？ 解解 这相当于将这相当于将4个无区别的球放进个无区别的球放进3

26、个有标志的盒子，个有标志的盒子，而每盒放的球可多于一个，故共有而每盒放的球可多于一个，故共有 项项: :1.8 允许重复的组合允许重复的组合),(rrnC1 4)(zyx )4 , 134( C)4 , 6(C 15)2 , 6( C322222334,xyzxyxyzxzxyxx44322223,zyzyzyxyzzxyxz2022-7-838n例例 从从 1,2,3,4,5,6 中取中取 3 个作不相邻的组合有：个作不相邻的组合有：1,3,5, 1,3,6, 1,4,6, 2,4,6n定理定理1.4 从从A=1,2,n中取中取r个作不相邻的的组合，个作不相邻的的组合，其组合数为其组合数为1

27、.8.2 不相邻组合不相邻组合 rrn12022-7-839n证证 若若 是一个不相邻的是一个不相邻的r组合，不妨设组合，不妨设 ，可构造一个可构造一个 上的上的r组组合合 。 反之，给定一个反之，给定一个 上的上的r组合组合 可以如下得到一个可以如下得到一个1,2,n上的一个上的一个不相邻不相邻 的的r组合组合1.8.2 1.8.2 不相邻组合不相邻组合,21raaaraaa 211, 2 , 1 rn1, 1,21 raaar1, 2 , 1 rn,21rbbb1, 1,21 rbbbr2022-7-840n例例 证明证明k个连续的正整数的乘积能被个连续的正整数的乘积能被k!整除整除 。

28、证证 不妨设不妨设k个连续的正整数为个连续的正整数为n，n+1，n+k-1。 考虑从考虑从n+k-1个元素中取个元素中取k个的组合，其组合数为：个的组合，其组合数为： 由于由于 是一个正整数，所以有是一个正整数，所以有 1.9 组合的解释组合的解释!)(),(knknknkknC211 nknknk)( | !21 ),(kknC1 2022-7-841n(1) 组合意义：组合意义：n个个元素的元素的r- -子集与子集与n-r子集一一对应，子集一一对应，n个元素的个元素的r- -子集的个数为子集的个数为 ，n-r子集的个数子集的个数为为 ，故等式成立。，故等式成立。n例例 3个元素个元素1,2

29、,3的的2- -子集与子集与1- -子集一一对应。子集一一对应。 1.9 组合的解释组合的解释),(),(rnnCrnC ,132231321),(rnC),(rnnC 2022-7-842(2) n组合意义：从这组合意义：从这n个元素中任取一个元素个元素中任取一个元素a， 个个组合可以如下分为两类：组合可以如下分为两类：l不含有元素不含有元素a的的r组合，其组合数为组合，其组合数为 l含元素含元素a的的r组合，其组合数为组合，其组合数为 1.91.9 组合的解释组合的解释),(),(),(111 rnCrnCrnC),(rnC1 ),(11 rnC),(rnC2022-7-8431.9 组合

30、的解释组合的解释(3) 组合意义组合意义1：任取任取r个元素个元素 l 不包含不包含 ，其组合数为，其组合数为 l 包含包含 ，但不包含，但不包含 ，其组合数为，其组合数为l 包含包含 ，其组合数为，其组合数为 0111nrrnrrnrrnraaa,211a),(rrnC 1a2a),(11 rrnCraaa,21),(),(001nCnC 2022-7-844n组合意义组合意义2：1.91.9 组合的解释组合的解释(0,0)(0,0)(n+1,r)(n,0)(n,0)(n,r)2022-7-8451.9 组合的解释组合的解释n由等式由等式(3)我们可以得到若干有用的公式：我们可以得到若干有用

31、的公式：nS 21121)n(n ),(),(),(),(1231201 nnCCCC),(),(2111 nCnnC),(),(),(),(1131211nCCCC 2022-7-8461.9 组合的解释组合的解释)(14332212 nnS),11C(C(4,2)C(3,1)2C(2,0) nn321312(2)(!)( nnnnnn),(),(),(),(212242232222 nCCCC),(),(322122 nCnnC2022-7-8471.9 组合的解释组合的解释(4)n代数证明：代数证明： )!( !)!(!)!( !)!( !rlrlnnrlrllnlnrlln nlrrl

32、rnrnrlln ,)!()!( !)!()!()!()!( !lnrlrnlnrlrnrnrnrlrnrn 2022-7-848组合意义：等式的左端可以看作是先从组合意义：等式的左端可以看作是先从n个元素中个元素中取取 个组合，然后对每一个个组合，然后对每一个 组合，从中再取组合，从中再取r个个元素的组合。这相当于直接从元素的组合。这相当于直接从n个元素中取个元素中取r个元素个元素的组合，但每个的组合，但每个r组合重复了组合重复了 次。次。1.9 组合的解释组合的解释 lnrnll2022-7-8491.9 组合的解释组合的解释n(5) n组合意义：用两种不同的方式计算组合意义：用两种不同的

33、方式计算n个元素的集合个元素的集合S的子集的个数的子集的个数 S 的所有子集的个数为的所有子集的个数为 另一方面，另一方面，S有有n个元素，在构成个元素，在构成S的子集时，的子集时，S的每的每个元素都有两种选择，或在该子集中，或不在该子个元素都有两种选择，或在该子集中，或不在该子集中，由乘法法则知，集中，由乘法法则知，S有有 个子集。个子集。),(),(),(),(nnCnCnCnC 210nnnCnCnCnC2210 ),(),(),(),(n22022-7-850n(6) n代数证明：在等式代数证明：在等式 中令中令x=1, y=- -1便得便得n组合意义：在组合意义：在n个元素的集合个元

34、素的集合S中取中取r组合，组合，r为奇数为奇数的组合数目等于的组合数目等于r为偶数的组合数目为偶数的组合数目。 取定取定S中的一个元素中的一个元素a，对，对S的任一个奇组合的任一个奇组合 若若 则则 对应于偶组合对应于偶组合 若若 则则 对应于偶组合对应于偶组合 1.9 组合的解释组合的解释0210 ),(),(),(),(nnCnCnCnCnnnnynnCyxnCxnCyx),(),(),()( 110S ,Sa aS S ,Sa aS S 2022-7-851n反之，对反之，对S的任一个偶组合的任一个偶组合 若若 则则 应于奇组合应于奇组合 若若 ，则，则 对应于奇组合对应于奇组合 。 显

35、然这是奇组合与偶组合之间的一一对应关系。故显然这是奇组合与偶组合之间的一一对应关系。故等式成立。等式成立。1.91.9 组合的解释组合的解释S ,Sa S aS Sa S aS 2022-7-852n例例 考虑四个元素的集合考虑四个元素的集合a,b,c,d，其所有的奇数组其所有的奇数组合为合为 a, b, c, d, a,b,c, a,b,d, a,c,d, b,c,d 取元素取元素a，其相应的偶数组合有：其相应的偶数组合有： ，a,b, a,c, a,d, b,c, b,d, c,d, a,b,c,d。1.9 组合的解释组合的解释2022-7-853n(7)n代数证明：考虑等式代数证明：考虑

36、等式两边的系数便得两边的系数便得1.9 组合的解释组合的解释 0110nrmrnmrnmrnmnmnmxxx)()()( 1112022-7-854n组合意义组合意义1：从：从m+n个有标志的球中取个有标志的球中取r个，这个，这m+n个球中有个球中有m个是红的，有个是红的，有n个是蓝的，所有的个是蓝的，所有的r组合组合不外乎以下几种可能：不外乎以下几种可能：l 0个红球，个红球，r个篮球个篮球: :l 1个红球，个红球，r-1个篮球个篮球: : l r个红球，个红球，0个篮球个篮球: :1.9 组合的解释组合的解释 rnm0 11rnm 0nrm2022-7-855n(8) 证证 在等式在等式

37、(7)中取中取r=m便得便得1.91.9 组合的解释组合的解释nmmnmmnmnmmnm 1100, 0011nmmnmmmnmm 0110nmmmnmmnmmnm2022-7-856n当当m=n时有时有1.9 组合的解释组合的解释22222102 nnnnnnn2022-7-857n例例 (a)用组合方法证明用组合方法证明 和和 都是整数都是整数. 证证 考虑将考虑将2n个有标志的球放入个有标志的球放入n个有区别的盒子个有区别的盒子中，每盒中，每盒2个球，其放法数为：个球，其放法数为： 1.9 组合的解释组合的解释nn22 )!(nnn323 )!(nnnnnnnn)()!() !()!(!

38、)(!)(2222212 23222 2122 2212222222222)(nnnnn2022-7-858n类似地考虑将类似地考虑将3n个有标志的球放入个有标志的球放入n个有区别的盒个有区别的盒子中，每盒子中，每盒3个球，可得其放法数为：个球，可得其放法数为： 故故 为整数为整数1.9 组合的解释组合的解释nnnnn32333)!() !()!( nnn323 )!(2022-7-859n(b)(b)证明证明 是整数。是整数。 n证考虑将证考虑将n2个有标志的球放入个有标志的球放入n个有区别的盒子中，个有区别的盒子中，每盒每盒n个球，其放法数为：个球，其放法数为： 当当n个盒子无区别时，其方

39、法数为：个盒子无区别时，其方法数为： 1.9 组合的解释组合的解释12 nnn) !()!(nnnnnnnnnnnnnnn) !()!()(2222212 122 nnnnnnn) !()!() !( !)!(2022-7-8601.9 组合的解释组合的解释n例例 证明：证明： 其中其中k, n为非负整数。为非负整数。 证证 11110 knknknkk knknkkknknkkkknknknknknkn110 11010 111 1112022-7-861 1.16 1.20 1.22 1.27习题习题2022-7-862 例例1.30 7位科学家从事一项机密研究，实验室装有位科学家从事一项

40、机密研究，实验室装有“电子锁电子锁”，每位科学家都有一把打开，每位科学家都有一把打开“电子锁电子锁”的钥匙。为了安全起见，必须有的钥匙。为了安全起见，必须有4 4位到场方可打开位到场方可打开“电子锁电子锁”。试问该。试问该“电子锁电子锁”必须具备多少特征？必须具备多少特征？每位科学家的每位科学家的“钥匙钥匙” ” 应具有多少这些特征？应具有多少这些特征？ 解解 因为任意三个人在一起，至少缺少电子锁的因为任意三个人在一起，至少缺少电子锁的 一种特征，而且对于两个不同的三人组，必至少缺一种特征，而且对于两个不同的三人组，必至少缺少两种特征，故电子锁至少应具备少两种特征，故电子锁至少应具备 特征。特

41、征。1.10 应用举例应用举例352356737 ),(C2022-7-863 对于任一位科学家，其余对于任一位科学家，其余6个人中任意三个人在场，个人中任意三个人在场，至少缺少一个他所具有的特征而无法打开大门，且至少缺少一个他所具有的特征而无法打开大门，且对于两个不同三人组，必至少缺少两种特征，所以对于两个不同三人组，必至少缺少两种特征，所以每个人的每个人的“钥匙钥匙” 至少应有至少应有 种特征。种特征。1.10 应用举例应用举例202345636 ),(C2022-7-864n例例1.31 4个全同的质点，总能量为个全同的质点，总能量为4E0，其中，其中E0是常数。是常数。每个质点的能级可

42、能为每个质点的能级可能为kE0，k=0,1,2,3,4。 (a) 若质点服从若质点服从Bose-Einstein分布，即能级为分布，即能级为kE0的的质点可以有质点可以有k2+1种状态，而且同能级的质点可以处于种状态，而且同能级的质点可以处于相同的状态，问有多少种不同的分布图象？相同的状态，问有多少种不同的分布图象？ (b) 若质点服从若质点服从Fermi-Dirac分布，即能级为分布，即能级为kE0的的质点可以有质点可以有2(k2+1)种状态，而且不允许同能级的两种状态，而且不允许同能级的两个质点有相同的状态，问有多少种不同的分布图象？个质点有相同的状态，问有多少种不同的分布图象？1.10

43、应用举例应用举例2022-7-865n解解 总能量为总能量为4E0的四个质点有以下的四个质点有以下5种可能的分布：种可能的分布： (0,0,0,4),(0,0,1,3),(0,0,2,2)，(0,1,1,2)，(1,1,1,1) (a) 根据根据kE0能级的质点可以有能级的质点可以有1+k2种不同的状态，种不同的状态，故各能级的状态为故各能级的状态为1.10 应用举例应用举例k012342状态数状态数1710512022-7-866 对应于对应于(0, 0, 0, 4)有有 种图象。种图象。 对应于对应于(0, 0, 1, 3)有有 种图象。种图象。 对应于对应于(0, 0, 2, 2)有有

44、对应于对应于(0, 1, 1, 2)有有 对应于对应于(1, 1, 1, 1)有有 所求图象数为：所求图象数为：N=17+20+15+15+5=72 1.10 应用举例应用举例17171 201021 154621251 ),(),(CC151521221 ),(),(CC5454142 ),(),(CC2022-7-867n(2) 根据根据kE0能级的质点可以有能级的质点可以有2(1+k2)种不同的状种不同的状态，故各能级的状态为态，故各能级的状态为 对应于对应于(0,0,0,4)有有 0 种图象。种图象。 对应于对应于(0,0,1,3)有有 种图象。种图象。 1.10 应用举例应用举例k0

45、12344状态数状态数3420102801201422 ),(),(),(CCC2022-7-868 对应于对应于(0, 0, 2, 2)有有 对应于对应于(0, 1, 1, 2)有有 对应于对应于(1, 1, 1, 1)有有 种图象。种图象。 故所求的图象数为故所求的图象数为 N=0+80+45+120+1=246 1.10 应用举例应用举例4521022 ),(),(CC1201102412 ),(),(),(CCC144 ),(C2022-7-869n例例1.33从从(0,0)点到达点到达(m,n)点点(ma，问有多少条路径？，问有多少条路径？n解解 路径的第一步必然是从路径的第一步必然

46、是从(0,0)点到达点到达(0,1)点，问题点，问题等价于求从等价于求从(0,1)点到达点到达(m,n)的满足条件的路径数。的满足条件的路径数。所求路径数为所求路径数为1.10 应用举例应用举例)(!)!(!)!()!()!( !)!(mnnmnmnmnmnmnm 11111 111mnmmnm2022-7-8701.10 1.10 应用举例应用举例(0,0)(0,0)(1,0)(1,0)(0,1)(0,1)y=xy=x(m,n(m,n) )2022-7-871n例例1.34 一场音乐会的票价为一场音乐会的票价为50元一张，排队买票的元一张，排队买票的顾客中有顾客中有m位持有位持有50元的钞票

47、，元的钞票，n位持有位持有100元的钞票。元的钞票。售票处没有准备售票处没有准备50元的零钱，试问有多少种排队的办元的零钱，试问有多少种排队的办法使购票能顺利进行，不出现找不出零钱的状态。假法使购票能顺利进行，不出现找不出零钱的状态。假定每位顾客只限买一张，而且定每位顾客只限买一张，而且 。n解如图所示，所求排队的方法数为从点解如图所示，所求排队的方法数为从点 到到点点 ，且不越过直线，且不越过直线OC的路径数。而这等于的路径数。而这等于从点从点 到到 的路径数减去从点的路径数减去从点 到到 的到达的到达直线直线OC的路径数。的路径数。 1.10 应用举例应用举例nm ),( 00O),(nm

48、M),( 01A), 1( nmM )1 , 0(B), 1( nmM 2022-7-872n而后者等于从点而后者等于从点 到点到点 的路径数，的路径数，故所求的排队方法数为故所求的排队方法数为 1.10 应用举例应用举例),( 10B),( nmM1 1mnmmnm 11)!()!()!(!)!( nmnmnmnm 11)!(!)!()(nmnmnm 2022-7-8731.10 应用举例应用举例C(n,n)O(0,0)A(1,0)B(0,1)M(m+1,n)M(m,n)2022-7-8741.10 应用举例应用举例n证证 2: 将将50元和元和100元的钞票分别记为元的钞票分别记为1和和-

49、1. .则问则问题成为证明由题成为证明由m个个1和和n个个-1构成的构成的m+n项项 其部分和满足其部分和满足 的数列的个数等于的数列的个数等于nmaaa ,21), 2 , 1( , 021nmkaaak 1mnmmnm2022-7-8751.10 应用举例应用举例n由由m个个1和和n个个-1构成的构成的m+n项的数列的个数等于项的数列的个数等于n考虑考虑m个个1和和n个个-1的不可接受的序列的不可接受的序列n因为序列是不可接受的因为序列是不可接受的, ,所以存在一个最小的所以存在一个最小的k使得部分和使得部分和 mnmnmaaa ,21021 kaaa2022-7-8761.10 1.10

50、 应用举例应用举例n将前将前k个字符中的个字符中的1，- -1互换，则得到一个有互换，则得到一个有m+1个个1和和n-1个个- -1的序列。的序列。n反之，任给一个有反之，任给一个有m+1个个1和和n-1个个- -1组成的字符组成的字符串，则存在最小的串，则存在最小的k，使得，使得 将将前前k个字符中的个字符中的1，- -1互换，则得到一个有互换，则得到一个有m个个1和和n个个- -1的字符串，且该的字符串，且该字符串不合乎要求字符串不合乎要求。n故不可接受序列的个数为故不可接受序列的个数为 1mnm021 kaaa2022-7-877n数字通讯中的一个重要问题是设计信道的编码器数字通讯中的一

51、个重要问题是设计信道的编码器译码器对。而在设计编码器译码器时的一个关键译码器对。而在设计编码器译码器时的一个关键问题是考虑所设计码的纠错能力。问题是考虑所设计码的纠错能力。n例例 编码编码00, 01, 10, 11无法查错。无法查错。 编码编码00, 11可以查单错，但无法纠错。可以查单错，但无法纠错。 编码编码001, 110不但可以查单错，也可以纠单错。不但可以查单错，也可以纠单错。1.10 应用举例应用举例2022-7-878n定义定义 若若 ， 是两个用是两个用n位二进制数表示的码，位二进制数表示的码， 设设 ， ，若，若 个数为个数为 ，则记为则记为 ，称之为，称之为 ， 码的码的 Hamming距离。距离。 定理定理 对任意的码对任意的码 下列三角不等式成立：下列三角不等式成立： 证证 设设 若若 ，则，则 ， 中至少有一个成立，故不等式成立。中至少有一个成立，故不等式成立。 1.10 应用举例应用举例naaaa21 nbbbb21 abiiba llabdbad ),(),(ab,cba),(),(),(cadcbdbad ,21ncccc iica iiba iicb 2022-7-879n最小距离译码准则：给定码最小距离译码准则：给定码C，设接受字为，设接受字为 ，将，将 译为译为C中与中与 有最小有最小Ham