组合数学第一张排列与组合精选PPT.ppt

《组合数学第一张排列与组合精选PPT.ppt》由会员分享，可在线阅读，更多相关《组合数学第一张排列与组合精选PPT.ppt（92页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、关于组合数学第一张排列与组合关于组合数学第一张排列与组合04.04.20231第1页，讲稿共92张，创作于星期二第第1章章排列与组合排列与组合第2页，讲稿共92张，创作于星期二04.04.20233组合数学组合数学n组合数学是研究离散结构的存在、计数、分析和组合数学是研究离散结构的存在、计数、分析和优化的一门学科。优化的一门学科。n应用领域应用领域:计算机科学、概率论、社会科学、生计算机科学、概率论、社会科学、生物科学、信息论等。物科学、信息论等。n参考书：参考书：1.R.A.Rrualdi.Introductory Combinatorics 组合数学组合数学 机械工业出版社机械工业出版社

2、2.孙淑玲孙淑玲 许胤龙许胤龙.组合数学引论组合数学引论 中国科学技术大中国科学技术大学出版社学出版社第3页，讲稿共92张，创作于星期二04.04.202341.1基本计数法则基本计数法则n1.1 基本计数法则基本计数法则n加法法则：设事件加法法则：设事件A有有m种产生方式，事件种产生方式，事件B有有n种产生方式，则种产生方式，则“事件事件A或事件或事件B”有有m+n种产种产生方式。生方式。n例例.一位学生想选修一门数学课程或一门生物一位学生想选修一门数学课程或一门生物课程。若有课程。若有4门数学课程和门数学课程和3门生物课程，则该门生物课程，则该学生有学生有4+3=7种不同的选课方式。种不同

3、的选课方式。第4页，讲稿共92张，创作于星期二04.04.202351.1基本计数法则基本计数法则n乘法法则：设事件乘法法则：设事件A有有m种产生方式，事件种产生方式，事件B有有n种产生方式，则种产生方式，则“事件事件A与事件与事件B”有有mn种产种产生方式。生方式。n例例1.1 设一个符号由两个字符组成，第设一个符号由两个字符组成，第1个字符个字符由由a,b,c,d,e组成，第组成，第2个字符由个字符由1,2,3组成，则由组成，则由乘法法则，该符号有乘法法则，该符号有 种产生方式种产生方式。第5页，讲稿共92张，创作于星期二04.04.20236 例例1.3 求求比比10000小小的的正正整

4、整数数中中含含有有数数字字1的的数数的的个数。个数。解解 比比10000小的正整数可以写为小的正整数可以写为 的形式。的形式。l 共有共有104-1=9999个个l 其中不含其中不含1的正整数有的正整数有 94-1=6560个个l 所求正整数的个数为所求正整数的个数为 9999-6560=3439个。个。1.1 基本计数法则基本计数法则第6页，讲稿共92张，创作于星期二04.04.20237例例1.4 求长度为求长度为n的二元码的数目。的二元码的数目。解解 长度为长度为n的二元码的形式为的二元码的形式为 由乘法法则，长度为由乘法法则，长度为n的二元码的数目为的二元码的数目为 1.1 基本计数法

5、则基本计数法则第7页，讲稿共92张，创作于星期二04.04.20238例例1.6 求布尔函数求布尔函数 的数目。的数目。解解 自变量自变量 可能取值的个数为可能取值的个数为 设取值为设取值为 则则n n个变元的布尔函数有个变元的布尔函数有 个。个。1.1 基本计数法则基本计数法则第8页，讲稿共92张，创作于星期二04.04.202391.1 基本计数法则基本计数法则n例例 1.8 ，求能整除，求能整除n的正整数的正整数的个数。的个数。解解 能整除能整除n的正整数可以写为如下形式：的正整数可以写为如下形式：故能整除故能整除n的正整数的个数为的正整数的个数为 第9页，讲稿共92张，创作于星期二04

6、.04.202310例例1.9 求求从从a,b,c,d,e这这5个个字字母母中中取取6个个所所组组成成的的字字符符串串个个数数。要要求求(1)第第1 1个个和和第第6个个字字符符必必为为子子音音字字符符；(2)每每一一字字符符串串必必有有两两个个母母音音字字符符，且且两两个个母母音音字字母母不相邻；不相邻；(3)相邻的两个子音字符必不相同。相邻的两个子音字符必不相同。解解 符合要求的字符串有以下几种模式：符合要求的字符串有以下几种模式：所求的字符串个数为：所求的字符串个数为：个。个。1.1 基本计数法则基本计数法则第10页，讲稿共92张，创作于星期二04.04.202311例例 设设某某地地的

7、的街街道道把把城城市市分分割割成成矩矩形形方方格格，每每个个方方格格叫叫做做它它的的块块。某某甲甲从从家家中中出出发发上上班班，向向东东要要走走过过m块块，向向北北要要走走过过n块块，问问某某甲甲上上班班的的路路径径有有多多少条？少条？解解 问题可划为求右图从点问题可划为求右图从点 (0,0)到到(m,n)的路径数的路径数:每一条从点每一条从点(0,0)到到(m,n)的路径与的路径与 一个由一个由m个个x和和n个个y的排列相对应的排列相对应 所求路所求路径数为：径数为：1.2 一一对应一一对应(0 0,0 0)(m,n)xy第11页，讲稿共92张，创作于星期二04.04.202312定定理理（

8、Cayley）n个个有有标标号号的的顶顶点点的的树树的的数数目目等等于于 。例例1.12 给定下列树给定下列树 可可得得序序列列:3,1,5,5,1。反反之之从从序序列列3,1,5,5,1也也可可以以构构造出上述树。造出上述树。1.2 1.2 一一对应一一对应2375461第12页，讲稿共92张，创作于星期二04.04.202313n定定义义：从从n个个不不同同的的元元素素中中，取取出出r个个按按次次序序排排成成一一列列，称称为为从从这这n个个元元素素中中取取r个个的的一一个个排排列列，其其排列数记为排列数记为 .n由定义显然有由定义显然有 (1)(2)当当r=n时有时有,1.3 排列排列第1

9、3页，讲稿共92张，创作于星期二04.04.202314例例1.13 由由5种种颜颜色色的的星星状状物物，20种种不不同同的的花花排排成成如如下下的的图图案案：两两边边是是星星状状物物，中中间间是是3朵朵花花，问问共共有多少种这样的图案？有多少种这样的图案？解解 图案的形状为图案的形状为 共有共有 种图案。种图案。1.3 排列排列第14页，讲稿共92张，创作于星期二04.04.202315例例1.14 A单单位位有有7位位代代表表，B单单位位有有3位位代代表表，排排在在一一列列合合影影，要要求求B单单位位的的人人排排在在一一起起，问问有有多多少少种不同的排列方案？种不同的排列方案？解解 B单单

10、位位的的某某一一排排列列作作为为一一个个元元素素参参加加单单位位A进进行排列，可得行排列，可得 种排列。种排列。B单位的单位的3人共有人共有 个排列，个排列，故共有故共有 排列方案。排列方案。1.3 排列排列第15页，讲稿共92张，创作于星期二04.04.202316例例1.15 若若例例1.14中中A单单位位的的两两人人排排在在两两端端，B单单位位的的3人不能相邻，问有多少种不同的排列方案？人不能相邻，问有多少种不同的排列方案？解解 共有共有 种方案。种方案。1.3 排列排列第16页，讲稿共92张，创作于星期二04.04.202317例例1.16 求求20000到到70000之之间间的的偶偶

11、数数中中由由不不同同的的数数字所组成的字所组成的5位数的个数。位数的个数。解解 设所求的数的形式为设所求的数的形式为 其中其中 (1)若若 ，这时，这时e有有4种选择，有种选择，有 (2)若若 ，这时，这时e有有5种选择，有种选择，有 共有共有 个。个。1.3 排列排列第17页，讲稿共92张，创作于星期二04.04.202318从从n个对象中取个对象中取r个沿一圆周排列的排列数用个沿一圆周排列的排列数用 表示，则有表示，则有 abcd,dabc,cdab,bcda特别地特别地，1.4 圆周排列圆周排列abcd第18页，讲稿共92张，创作于星期二04.04.202319例例1.19 5颗颗红红色

12、色的的珠珠子子，3颗颗蓝蓝色色的的珠珠子子装装在在圆圆板板的的四四周周，试试问问有有多多少少种种排排列列方方案案？若若蓝蓝色色的的珠珠子子不不相相邻邻又又有有多多少少种种排排列列方方案案？蓝蓝色色珠珠子子在在一一起起又又如何？如何？解解 (1)有有 种；种；(2)有有 种；种；(3)有有 种。种。1.4 圆周排列圆周排列第19页，讲稿共92张，创作于星期二04.04.202320例例1.20 5对对夫夫妻妻出出席席一一宴宴会会，围围一一圆圆桌桌坐坐下下，问问有有几几种种方方案案？若若要要求求每每对对夫夫妻妻相相邻邻又又有有多多少少种种方方案案？解解 (1)种方案；种方案；(2)种方案。种方案。

13、1.4 圆周排列圆周排列第20页，讲稿共92张，创作于星期二04.04.202321定定义义 从从n个个不不同同的的元元素素中中，取取出出r个个而而不不考考虑虑其其次次序序，称称为为从从这这n个个元元素素中中取取r个个组组合合，其其组组合合数数记记为为 。1.5 组合组合第21页，讲稿共92张，创作于星期二04.04.202322例例1.21 从从1300之之间间任任取取3个个不不同同的的数数，使使得得这这3个个数数的和正好被的和正好被3除尽，问共有几种方案？除尽，问共有几种方案？解解 将这将这300个数按照其被个数按照其被3除所得的余数分为三组：除所得的余数分为三组：A=1,4,298，B=

14、2,5,299，C=3,6,300 三个数取自集合三个数取自集合A：有：有C(100,3)种方案；种方案；三个数取自集合三个数取自集合B：有：有C(100,3)种方案；种方案；三个数取自集合三个数取自集合C：有：有C(100,3)种方案；种方案；三个数分别取自集合三个数分别取自集合A、B、C：有：有1003种方案；种方案；所求的方案数为：所求的方案数为：3C(100,3)+1003=1485100 1.5 组合组合第22页，讲稿共92张，创作于星期二04.04.202323例例1.22 甲甲和和乙乙两两单单位位共共11个个成成员员，其其中中甲甲单单位位7人，乙单位人，乙单位4人，拟从中组成一个

15、人，拟从中组成一个5人小组；人小组；(1)若要求必须包含乙单位若要求必须包含乙单位2人；人；(2)若要求至少包含乙单位若要求至少包含乙单位2人；人；(3)若若要要求求乙乙单单位位某某一一人人与与甲甲单单位位某某一一人人不不能能同同时时在这个小组；在这个小组；试分别求各有多少种方案。试分别求各有多少种方案。解解 (1)(2)(3)1.5 组合组合第23页，讲稿共92张，创作于星期二04.04.202324例例1.23 假假定定有有8位位成成员员，两两两两配配对对分分成成4组组，问问有有多少种分配方案？多少种分配方案？解解 方法方法1：将将8位位成成员员排排列列，共共有有8!个个排排列列，每每个个

16、排排列列两两两两划划分分，分分成成4组组，其其重重复复数数为为24.4!，所所求求分分配配方方案数为案数为 1.5 组合组合第24页，讲稿共92张，创作于星期二04.04.202325 方法方法2 2：将将8 8个个人人分分为为4 4组组，第第1 1组组有有 种种选选择择，第第2 2组组有有 种种选选择择，第第3 3组组有有 种种选选择择，第第4 4组组有有 种种选选择择，但但由由于于各各组组与与顺顺序序无无关关，故故所求分配方案数为：所求分配方案数为：1.51.5 组合组合第25页，讲稿共92张，创作于星期二04.04.202326例例1.24某某广广场场有有6个个入入口口处处，每每个个入入

17、口口处处每每次次只只能能通通过过一一辆辆汽汽车车，有有9辆辆汽汽车车要要开开进进广广场场，问问有有多多少少种入场方案？种入场方案？解解 方法方法1：9辆辆汽汽车车和和5个个标标志志的的一一个个排排列列可可表表示示一一种种入入场场方方案，其重复数为案，其重复数为5!，所求方案数为，所求方案数为 1.5 组合组合第26页，讲稿共92张，创作于星期二04.04.202327方法方法2：在在9辆辆汽汽车车和和5个个标标志志共共14个个位位置置中中，首首先先选选择择5个个作作为为标标志志的的位位置置，这这有有 种种选选择择，对对每每一一种种选择，将选择，将9辆汽车依次填入剩余的位置，这有辆汽车依次填入剩

18、余的位置，这有 种填入方式，故所求方案数为种填入方式，故所求方案数为 1.5 组合组合第27页，讲稿共92张，创作于星期二04.04.202328例例1.25 求求5位位数数中中至至少少出出现现一一个个6，而而被被3整整除除的的数的个数。数的个数。正正整整数数n能能够够被被3整整除除的的的的充充要要条条件件是是n的的各各个个数数字字之和能够被之和能够被3整除。整除。设设 因为因为 ，所以，所以 于是于是 iff 1.5 组合组合第28页，讲稿共92张，创作于星期二04.04.202329l5位数位数 共有共有90000个个l被被3整除的有整除的有30000个个l在这在这30000个数中不包含个

19、数中不包含6的数有的数有 个个l所求个数为所求个数为 30000-17496=125041.5 组合组合第29页，讲稿共92张，创作于星期二04.04.202330定理定理 在在n!中，质数中，质数p的最高幂的最高幂 其中其中 。1.5 组合组合第30页，讲稿共92张，创作于星期二04.04.202331例例6求求1000!的末尾有几个的末尾有几个0 解解 1000!的的末末尾尾所所含含0的的个个数数为为1000!的的因因子子分分解解中中2和和5的幂的最小者的幂的最小者 1000!因子分解中因子分解中5的幂为：的幂为：故故1000!的末尾有的末尾有249个个01.5 组合组合第31页，讲稿共9

20、2张，创作于星期二04.04.202332习题习题n1.2n1.4n1.5n1.8n1.9第32页，讲稿共92张，创作于星期二04.04.202333允许重复的排列允许重复的排列n定理定理 多重集合多重集合 的的r排列数为排列数为n例例 用用26个英文字母可以构造出多少个个英文字母可以构造出多少个4个元音字母长个元音字母长度为度为8的字符串的字符串?解解 该问题是要求该问题是要求 的包含的包含4个元个元音字母的音字母的8排列数排列数.在长度为在长度为8的字符串中的字符串中,4个元音字母出现的位置有个元音字母出现的位置有 种种 每种元音出现的位置有每种元音出现的位置有 个排列个排列 所求字符串的

21、个数为所求字符串的个数为第33页，讲稿共92张，创作于星期二04.04.202334n定理定理 多重集合多重集合 的全排列数为的全排列数为 其中其中n证证 排列的个数为排列的个数为允许重复的排列允许重复的排列第34页，讲稿共92张，创作于星期二04.04.202335n例例1.24某某广广场场有有6个个入入口口处处，每每个个入入口口处处每每次次只只能能通通过过一一辆辆汽汽车车，有有9辆辆汽汽车车要要开开进进广广场场，问问有有多多少少种入场方案？种入场方案？n解解 方法方法1：9辆辆汽汽车车和和5个个标标志志的的一一个个排排列列可可表表示示一一种种入入场场方方案，所求方案数为案，所求方案数为 允

22、许重复的排列允许重复的排列第35页，讲稿共92张，创作于星期二04.04.202336n 例例 从从1,2,3中取中取2个允许重复的组合为个允许重复的组合为 1,1,1,2,1,3,2,2,2,3,3,3n定理定理1.2 在在n个不同的元素中取个不同的元素中取r个进行组合，若允许个进行组合，若允许重复，则组合数为重复，则组合数为 证证 设设n个不同的元素为个不同的元素为1,2,3,n 若若 是一个允许重复的是一个允许重复的r组合，不妨设组合，不妨设 ，可构造一个可构造一个 上的不上的不 允许重复的允许重复的r组合组合1.8.1 允许重复的组合允许重复的组合第36页，讲稿共92张，创作于星期二0

23、4.04.2023371.8 1.8 允许重复的组合允许重复的组合n反反之之给给定定一一个个 上上的的不不允允许许重重复复的的r组组合合 ，我我们们可可以以如如下下得得到到一一个个1,2,n上上的的一一个个允允许许重重复复的的r组合组合 。故故n个个元元素素的的允允许许重重复复的的r组组合合与与n+r-1个个元元素素的的不不允允许许重重复复的的组组合合之之间间有有一一一一对对应应关关系系，故故它它们们的的组组合合数数相相同同，于于是定理得证。是定理得证。第37页，讲稿共92张，创作于星期二04.04.202338n定定理理1.3 r个个无无区区别别的的球球放放进进n个个有有标标志志的的盒盒子子

24、，而而每每盒放的球可多于一个，则共有盒放的球可多于一个，则共有 种方案种方案n例例1.28 试问试问 有多少项？有多少项？解解 这这相相当当于于将将4个个无无区区别别的的球球放放进进3个个有有标标志志的的盒盒子子，而每盒放的球可多于一个，故共有而每盒放的球可多于一个，故共有 项项:1.8 允许重复的组合允许重复的组合第38页，讲稿共92张，创作于星期二04.04.202339n例例 从从 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个个作作不不相相邻邻的的的的组组合合，

25、其组合数为其组合数为1.8.2 不相邻组合不相邻组合第39页，讲稿共92张，创作于星期二04.04.202340n证证 若若 是一个不相邻的是一个不相邻的r组合，不妨设组合，不妨设 ，可可构构造造一一个个 上上的的r组组合合 。反之，给定一个反之，给定一个 上的上的r组合组合 可以如下得到一个可以如下得到一个1,2,n上的一个上的一个不相邻不相邻 的的r组合组合1.8.2 1.8.2 不相邻组合不相邻组合第40页，讲稿共92张，创作于星期二04.04.202341n例例 证明证明k个连续的正整数的乘积能被个连续的正整数的乘积能被k!整除整除。证证 不妨设不妨设k个连续的正整数为个连续的正整数为

26、n，n+1，n+k-1。考虑从考虑从n+k-1个元素中取个元素中取k个的组合，其组合数为：个的组合，其组合数为：由于由于 是一个正整数，所以有是一个正整数，所以有 1.9 组合的解释组合的解释第41页，讲稿共92张，创作于星期二04.04.202342n(1)组组合合意意义义：n个个元元素素的的r-子子集集与与n-r子子集集一一一一对对应应，n个个元元素素的的r-子子集集的的个个数数为为 ，n-r子子集集的的个个数数为为 ，故等式成立。，故等式成立。n例例 3个元素个元素1,2,3的的2-子集与子集与1-子集一一对应。子集一一对应。1.9 组合的解释组合的解释第42页，讲稿共92张，创作于星期

27、二04.04.202343(2)n组合意义：从这组合意义：从这n个元素中任取一个元素个元素中任取一个元素a，个个组合可以如下分为两类：组合可以如下分为两类：l不含有元素不含有元素a的的r组合，其组合数为组合，其组合数为 l含元素含元素a的的r组合，其组合数为组合，其组合数为 1.91.9 组合的解释组合的解释第43页，讲稿共92张，创作于星期二04.04.2023441.9 组合的解释组合的解释(3)组合意义组合意义1：任取任取r个元素个元素 l不包含不包含 ，其组合数为，其组合数为 l包含包含 ，但不包含，但不包含 ，其组合数为，其组合数为l包含包含 ，其组合数为，其组合数为 第44页，讲稿

28、共92张，创作于星期二04.04.202345n组合意义组合意义2：1.91.9 组合的解释组合的解释(0,0)(0,0)(n+1,r)(n,0)(n,0)(n,r)第45页，讲稿共92张，创作于星期二04.04.2023461.9 组合的解释组合的解释n由等式由等式(3)我们可以得到若干有用的公式：我们可以得到若干有用的公式：第46页，讲稿共92张，创作于星期二04.04.2023471.9 组合的解释组合的解释第47页，讲稿共92张，创作于星期二04.04.2023481.9 组合的解释组合的解释(4)代数证明：代数证明：第48页，讲稿共92张，创作于星期二04.04.202349组组合合

29、意意义义：等等式式的的左左端端可可以以看看作作是是先先从从n个个元元素素中中取取 个个组组合合，然然后后对对每每一一个个 组组合合，从从中中再再取取r个个元元素素的的组组合合。这这相相当当于于直直接接从从n个个元元素素中中取取r个个元元素素的组合，但每个的组合，但每个r组合重复了组合重复了 次。次。1.9 组合的解释组合的解释第49页，讲稿共92张，创作于星期二04.04.2023501.9 组合的解释组合的解释n(5)n组组合合意意义义：用用两两种种不不同同的的方方式式计计算算n个个元元素素的的集集合合S的的子子集的个数集的个数 S 的所有子集的个数为的所有子集的个数为 另另一一方方面面，S

30、有有n个个元元素素，在在构构成成S的的子子集集时时，S的的每每个个元元素素都都有有两两种种选选择择，或或在在该该子子集集中中，或或不不在在该该子子集集中中，由由乘乘法法法法则知，则知，S有有 个子集。个子集。第50页，讲稿共92张，创作于星期二04.04.202351n(6)n代数证明：在等式代数证明：在等式 中令中令x=1,y=-1便得便得n组组合合意意义义：在在n个个元元素素的的集集合合S中中取取r组组合合，r为为奇奇数数的组合数目等于的组合数目等于r为偶数的组合数目为偶数的组合数目。取定取定S中的一个元素中的一个元素a，对，对S的任一个奇组合的任一个奇组合 若若 则则 对应于偶组合对应于

31、偶组合 若若 则则 对应于偶组合对应于偶组合 1.9 组合的解释组合的解释第51页，讲稿共92张，创作于星期二04.04.202352n反之，对反之，对S的任一个偶组合的任一个偶组合 若若 则则 应于奇组合应于奇组合 若若 ，则，则 对应于奇组合对应于奇组合 。显显然然这这是是奇奇组组合合与与偶偶组组合合之之间间的的一一一一对对应应关关系系。故故等式成立。等式成立。1.91.9 组合的解释组合的解释第52页，讲稿共92张，创作于星期二04.04.202353n例例 考虑四个元素的集合考虑四个元素的集合a,b,c,d，其所有的奇数组其所有的奇数组合为合为 a,b,c,d,a,b,c,a,b,d,

32、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 组合的解释组合的解释第53页，讲稿共92张，创作于星期二04.04.202354n(7)n代数证明：考虑等式代数证明：考虑等式两边的系数便得两边的系数便得1.9 组合的解释组合的解释第54页，讲稿共92张，创作于星期二04.04.202355n组组合合意意义义1：从从m+n个个有有标标志志的的球球中中取取r个个，这这m+n个个球球中中有有m个个是是红红的的，有有n个个是是蓝蓝的的，所所有有的的r组组合合不不外外乎以下几种可能：乎以下几种可能：

33、l0个红球，个红球，r个篮球个篮球:l1个红球，个红球，r-1个篮球个篮球:lr个红球，个红球，0个篮球个篮球:1.9 组合的解释组合的解释第55页，讲稿共92张，创作于星期二04.04.202356n(8)证证 在等式在等式(7)中取中取r=m便得便得1.91.9 组合的解释组合的解释第56页，讲稿共92张，创作于星期二04.04.202357n当当m=n时有时有1.9 组合的解释组合的解释第57页，讲稿共92张，创作于星期二04.04.202358n例例(a)用组合方法证明用组合方法证明 和和 都是整数都是整数.证证 考考虑虑将将2n个个有有标标志志的的球球放放入入n个个有有区区别别的的盒

34、盒子子中，每盒中，每盒2个球，其放法数为：个球，其放法数为：1.9 组合的解释组合的解释第58页，讲稿共92张，创作于星期二04.04.202359n类类似似地地考考虑虑将将3n个个有有标标志志的的球球放放入入n个个有有区区别别的的盒盒子中，每盒子中，每盒3个球，可得其放法数为：个球，可得其放法数为：故故 为整数为整数1.9 组合的解释组合的解释第59页，讲稿共92张，创作于星期二04.04.202360n(b)(b)证明证明 是整数。是整数。n证证考考虑虑将将n2个个有有标标志志的的球球放放入入n个个有有区区别别的的盒盒子子中中，每盒每盒n个球，其放法数为：个球，其放法数为：当当n个盒子无区

35、别时，其方法数为：个盒子无区别时，其方法数为：1.9 组合的解释组合的解释第60页，讲稿共92张，创作于星期二04.04.2023611.9 组合的解释组合的解释n例例 证明：证明：其中其中k,n为非负整数。为非负整数。证证 第61页，讲稿共92张，创作于星期二04.04.2023621.161.201.221.27习题习题第62页，讲稿共92张，创作于星期二04.04.202363例例1.30 7位位科科学学家家从从事事一一项项机机密密研研究究，实实验验室室装装有有“电电子子锁锁”，每每位位科科学学家家都都有有一一把把打打开开“电电子子锁锁”的的钥钥匙匙。为为了了安安全全起起见见，必必须须有

36、有4 4位位到到场场方方可可打打开开“电电子子锁锁”。试试问问该该“电电子子锁锁”必必须须具具备备多多少少特特征征？每位科学家的？每位科学家的“钥匙钥匙”应具有多少这些特征？应具有多少这些特征？解解 因因为为任任意意三三个个人人在在一一起起，至至少少缺缺少少电电子子锁锁的的 一一种种特特征征，而而且且对对于于两两个个不不同同的的三三人人组组，必必至至少少缺缺少两种特征，故电子锁至少应具备少两种特征，故电子锁至少应具备 特征。特征。1.10 应用举例应用举例第63页，讲稿共92张，创作于星期二04.04.202364对对于于任任一一位位科科学学家家，其其余余6个个人人中中任任意意三三个个人人在在

37、场场，至至少少缺缺少少一一个个他他所所具具有有的的特特征征而而无无法法打打开开大大门门，且且对对于于两两个个不不同同三三人人组组，必必至至少少缺缺少少两两种种特特征征，所所以以每个人的每个人的“钥匙钥匙”至少应有至少应有 种特征。种特征。1.10 应用举例应用举例第64页，讲稿共92张，创作于星期二04.04.202365n例例1.31 4个全同的质点，总能量为个全同的质点，总能量为4E0，其中，其中E0是常数。是常数。每个质点的能级可能为每个质点的能级可能为kE0，k=0,1,2,3,4。(a)若质点服从若质点服从Bose-Einstein分布，即能级为分布，即能级为kE0的的质点可以有质点

38、可以有k2+1种状态，而且同能级的质点可以处于种状态，而且同能级的质点可以处于相同的状态，问有多少种不同的分布图象？相同的状态，问有多少种不同的分布图象？(b)若质点服从若质点服从Fermi-Dirac分布，即能级为分布，即能级为kE0的质的质点可以有点可以有2(k2+1)种状态，而且不允许同能级的两个质种状态，而且不允许同能级的两个质点有相同的状态，问有多少种不同的分布图象？点有相同的状态，问有多少种不同的分布图象？1.10 应用举例应用举例第65页，讲稿共92张，创作于星期二04.04.202366n解解 总能量为总能量为4E0的四个质点有以下的四个质点有以下5种可能的分布：种可能的分布：

39、(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状态数状态数171051第66页，讲稿共92张，创作于星期二04.04.202367 对应于对应于(0,0,0,4)有有 种图象。种图象。对应于对应于(0,0,1,3)有有 种图象。种图象。对应于对应于(0,0,2,2)有有 对应于对应于(0,1,1,2)有有 对应于对应于(1,1,1,1)有有 所求图象数为：所求图象数为：N=17+20+

40、15+15+5=72 1.10 应用举例应用举例第67页，讲稿共92张，创作于星期二04.04.202368n(2)根根据据kE0能能级级的的质质点点可可以以有有2(1+k2)种种不不同同的的状状态，故各能级的状态为态，故各能级的状态为 对应于对应于(0,0,0,4)有有 0 种图象。种图象。对应于对应于(0,0,1,3)有有 种图象。种图象。1.10 应用举例应用举例k012344状态数状态数3420102第68页，讲稿共92张，创作于星期二04.04.202369 对应于对应于(0,0,2,2)有有 对应于对应于(0,1,1,2)有有 对应于对应于(1,1,1,1)有有 种图象。种图象。故

41、所求的图象数为故所求的图象数为 N=0+80+45+120+1=246 1.10 应用举例应用举例第69页，讲稿共92张，创作于星期二04.04.202370n例例1.33从从(0,0)点点到到达达(m,n)点点(ma，问有多少条路径？，问有多少条路径？n解解 路路径径的的第第一一步步必必然然是是从从(0,0)点点到到达达(0,1)点点，问问题题等等价价于于求求从从(0,1)点点到到达达(m,n)的的满满足足条条件件的的路路径径数数。所求路径数为所求路径数为1.10 应用举例应用举例第70页，讲稿共92张，创作于星期二04.04.2023711.10 1.10 应用举例应用举例(0,0)(0,

42、0)(1,0)(1,0)(0,1)(0,1)y=xy=x(m,n(m,n)第71页，讲稿共92张，创作于星期二04.04.202372n例例1.34 一一场场音音乐乐会会的的票票价价为为50元元一一张张，排排队队买买票票的的顾顾客客中中有有m位位持持有有50元元的的钞钞票票，n位位持持有有100元元的的钞钞票票。售售票票处处没没有有准准备备50元元的的零零钱钱，试试问问有有多多少少种种排排队队的的办办法法使使购购票票能能顺顺利利进进行行，不不出出现现找找不不出出零零钱钱的的状状态态。假假定每位顾客只限买一张，而且定每位顾客只限买一张，而且 。n解解如如图图所所示示，所所求求排排队队的的方方法法

43、数数为为从从点点 到到点点 ，且且不不越越过过直直线线OC的的路路径径数数。而而这这等等于于从从点点 到到 的路径数减去从点的路径数减去从点 到到 的到达的到达直线直线OC的路径数。的路径数。1.10 应用举例应用举例第72页，讲稿共92张，创作于星期二04.04.202373n而而后后者者等等于于从从点点 到到点点 的的路路径径数数，故所求的排队方法数为故所求的排队方法数为 1.10 应用举例应用举例第73页，讲稿共92张，创作于星期二04.04.2023741.10 应用举例应用举例C(n,n)O(0,0)A(1,0)B(0,1)M(m+1,n)M(m,n)第74页，讲稿共92张，创作于星

44、期二04.04.2023751.10 应用举例应用举例n证证 2:将将50元和元和100元的钞票分别记为元的钞票分别记为1和和-1.则问题成则问题成为证明由为证明由m个个1和和n个个-1构成的构成的m+n项项 其部分和满足其部分和满足 的数列的个数等于的数列的个数等于第75页，讲稿共92张，创作于星期二04.04.2023761.10 应用举例应用举例n由由m个个1和和n个个-1构成的构成的m+n项的数列的个数等于项的数列的个数等于n考虑考虑m个个1和和n个个-1的不可接受的序列的不可接受的序列n因为序列是不可接受的因为序列是不可接受的,所以存在一个最小的所以存在一个最小的k使得部使得部分和分

45、和第76页，讲稿共92张，创作于星期二04.04.2023771.10 1.10 应用举例应用举例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故不可接受序列的个数为故不可接受序列的个数为第77页，讲稿共92张，创作于星期二04.0

46、4.202378n数字通讯中的一个重要问题是设计信道的编码器数字通讯中的一个重要问题是设计信道的编码器译码器对。而在设计编码器译码器时的一个关键译码器对。而在设计编码器译码器时的一个关键问题是考虑所设计码的纠错能力。问题是考虑所设计码的纠错能力。n例例 编码编码00,01,10,11无法查错。无法查错。编码编码00,11可以查单错，但无法纠错。可以查单错，但无法纠错。编码编码001,110不但可以查单错，也可以纠单错。不但可以查单错，也可以纠单错。1.10 应用举例应用举例第78页，讲稿共92张，创作于星期二04.04.202379n定定义义 若若 ，是是两两个个用用n位位二二进进制制数数表表

47、示示的的码码，设设 ，若若 个个数数为为 ，则则记记为为 ，称之为，称之为 ，码的码的 Hamming距离。距离。定理定理 对任意的码对任意的码 下列三角不等式成立：下列三角不等式成立：证证 设设 若若 ，则，则 ，中至少有一个成立，故不等式成立。中至少有一个成立，故不等式成立。1.10 应用举例应用举例第79页，讲稿共92张，创作于星期二04.04.202380n最小距离译码准则：给定码最小距离译码准则：给定码C，设接受字为，设接受字为 ，将，将 译为译为C中与中与 有最小有最小Hamming距离的码距离的码 n定定理理 一一个个编编码码能能纠纠r个个错错的的充充要要条条件件是是该该编编码码

48、中中的的任意两个码的任意两个码的Hamming距离至少是距离至少是 。1.10 1.10 应用举例应用举例第80页，讲稿共92张，创作于星期二04.04.202381n例例 设设有有一一组组Hamming距距离离不不小小于于 的的n位位二二进进制码：制码：问问m最多为多少？最多为多少？解解 考虑下列考虑下列m个互不相交的个互不相交的n位二进制码的集合：位二进制码的集合：显然显然 1.10 应用举例应用举例第81页，讲稿共92张，创作于星期二04.04.202382于是有于是有 故故1.10 应用举例应用举例第82页，讲稿共92张，创作于星期二04.04.202383课堂习题课堂习题 n 1.1

49、2 试证等式：试证等式：证证 对等式对等式 (1)两边求导得两边求导得 (2)在等式在等式(2)中令中令x=1便得便得 第83页，讲稿共92张，创作于星期二04.04.202384课堂习题课堂习题n1.17 n和和r都都是正整数，而且是正整数，而且 试证下列等式：试证下列等式：(d)(e)解解(d)第84页，讲稿共92张，创作于星期二04.04.202385课堂习题课堂习题n(e)第85页，讲稿共92张，创作于星期二04.04.202386n1.23 令令 试证：试证：证证 当当 时，时，T中分别有中分别有 个三元组，故个三元组，故 课堂习题课堂习题第86页，讲稿共92张，创作于星期二04.0

50、4.202387课堂习题课堂习题n证法证法1 下面用归纳法证明下面用归纳法证明 当当n=2时，结论显然成立时，结论显然成立 假定结论对假定结论对n时成立，下面证明结论对时成立，下面证明结论对 n+1也成立也成立 第87页，讲稿共92张，创作于星期二04.04.202388课堂习题课堂习题第88页，讲稿共92张，创作于星期二04.04.202389n证法证法2 分两种情况分两种情况 (1):有有 个三元组；个三元组；(2):有有 个三元组。个三元组。课堂习题课堂习题第89页，讲稿共92张，创作于星期二04.04.202390n1.35 凸凸10边边形形的的任任意意三三条条对对角角线线不不共共点点