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

第1章排列与组合2019/12/172组合数学组合数学是研究离散结构的存在、计数、分析和优化的一门学科。应用领域:计算机科学、概率论、社会科学、生物科学、信息论等。参考书：1.R.A.Rrualdi.IntroductoryCombinatorics组合数学机械工业出版社2.孙淑玲许胤龙.组合数学引论中国科学技术大学出版社2019/12/1731.1基本计数法则1.1基本计数法则加法法则：设事件A有m种产生方式，事件B有n种产生方式，则“事件A或事件B”有m+n种产生方式。例.一位学生想选修一门数学课程或一门生物课程。若有4门数学课程和3门生物课程，则该学生有4+3=7种不同的选课方式。2019/12/1741.1基本计数法则乘法法则：设事件A有m种产生方式，事件B有n种产生方式，则“事件A与事件B”有mn种产生方式。例1.1设一个符号由两个字符组成，第1个字符由a,b,c,d,e组成，第2个字符由1,2,3组成，则由乘法法则，该符号有种方式。15352019/12/175例1.3求比10000小的正整数中含有数字1的数的个数。解比10000小的正整数可以写为的形式。共有104-1=9999个其中不含1的正整数有94-1=6560个所求正整数的个数为9999-6560=3439个。1.1基本计数法则90,4321iaaaaa2019/12/176例1.4求长度为n的二元码的数目。解长度为n的二元码的形式为由乘法法则，长度为n的二元码的数目为1.1基本计数法则niaaaain,,2,1},1,0{,21n222222019/12/177例1.6求布尔函数的数目。解自变量可能取值的个数为设取值为则n个变元的布尔函数有个。1.1基本计数法则),,,(21nxxxf),,,(21nxxxn2naa21,，naa21n2222f2019/12/1781.1基本计数法则例1.8，求能整除n的正整数的个数。解能整除n的正整数可以写为如下形式：故能整除n的正整数的个数为42313117n40,20,30,13117121321aaaaaa605342019/12/179例1.9求从a,b,c,d,e这5个字母中取6个所组成的字符串个数。要求(1)第1个和第6个字符必为子音字符；(2)每一字符串必有两个母音字符，且两个母音字母不相邻；(3)相邻的两个子音字符必不相同。解符合要求的字符串有以下几种模式：所求的字符串个数为：个。1.1基本计数法则648323332019/12/1710例设某地的街道把城市分割成矩形方格，每个方格叫做它的块。某甲从家中出发上班，向东要走过m块，向北要走过n块，问某甲上班的路径有多少条？解问题可划为求右图从点(0,0)到(m,n)的路径数:每一条从点(0,0)到(m,n)的路径与一个由m个x和n个y的排列相对应所求路径数为：1.2一一对应(0,0)(m,n)xy),(mnmC2019/12/1711定理（Cayley）n个有标号的顶点的树的数目等于。例1.12给定下列树可得序列:3,1,5,5,1。反之从序列3,1,5,5,1也可以构造出上述树。1.2一一对应2nn23754612019/12/1712定义：从n个不同的元素中，取出r个按次序排成一列，称为从这n个元素中取r个的一个排列，其排列数记为.由定义显然有(1)(2)当r=n时有,1.3排列),(rnP10!,)!(!)1()1(),(rnnrnnnrnP)(,0),(nrrnP)1(,)1,(nnnP!12)1(),(nnnnnP2019/12/1713例1.13由5种颜色的星状物，20种不同的花排成如下的图案：两边是星状物，中间是3朵花，问共有多少种这样的图案？解图案的形状为★〇〇〇★共有种图案。1.3排列136800)3,20()2,5()181920()45(PP2019/12/1714例1.14A单位有7位代表，B单位有3位代表，排在一列合影，要求B单位的人排在一起，问有多少种不同的排列方案？解B单位的某一排列作为一个元素参加单位A进行排列，可得种排列。B单位的3人共有个排列，故共有排列方案。1.3排列!8!3!!382019/12/1715例1.15若例1.14中A单位的两人排在两端，B单位的3人不能相邻，问有多少种不同的排列方案？解共有种方案。1.3排列604800)456(!72019/12/1716例1.16求20000到70000之间的偶数中由不同的数字所组成的5位数的个数。解设所求的数的形式为其中(1)若，这时e有4种选择，有(2)若，这时e有5种选择，有共有个。1.3排列abcde}8,6,4,2,0{,62ea}6,4,2{a4032)3,8(43P}5,3{a3360)3,8(52P7392336040322019/12/1717从n个对象中取r个沿一圆周排列的排列数用表示，则有abcd,dabc,cdab,bcda特别地，1.4圆周排列),(rnQrrnPrnQ),(),()!1(!),(),(nnnnnnPnnQabcd2019/12/1718例1.195颗红色的珠子，3颗蓝色的珠子装在圆板的四周，试问有多少种排列方案？若蓝色的珠子不相邻又有多少种排列方案？蓝色珠子在一起又如何？解(1)有种；(2)有种；(3)有种。1.4圆周排列!71440)345(!4!!352019/12/1719例1.205对夫妻出席一宴会，围一圆桌坐下，问有几种方案？若要求每对夫妻相邻又有多少种方案？解(1)种方案；(2)种方案。1.4圆周排列!97683224245!2019/12/1720定义从n个不同的元素中，取出r个而不考虑其次序，称为从这n个元素中取r个组合，其组合数记为。1.5组合),(rnC!),(),(rrnCrnP!),(),(rrnPrnC2019/12/1721例1.21从1～300之间任取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：有1003种方案；所求的方案数为：3C(100,3)+1003=14851001.5组合2019/12/1722例1.22甲和乙两单位共11个成员，其中甲单位7人，乙单位4人，拟从中组成一个5人小组；(1)若要求必须包含乙单位2人；(2)若要求至少包含乙单位2人；(3)若要求乙单位某一人与甲单位某一人不能同时在这个小组；试分别求各有多少种方案。解(1)(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(CC2019/12/1723例1.23假定有8位成员，两两配对分成4组，问有多少种分配方案？解方法1：将8位成员排列，共有8!个排列，每个排列两两划分，分成4组，其重复数为24.4!，所求分配方案数为1.5组合105!42!842019/12/1724方法2：将8个人分为4组，第1组有种选择，第2组有种选择，第3组有种选择，第4组有种选择，但由于各组与顺序无关，故所求分配方案数为：1.5组合4321,,,,)2,8(C),(26C)2,4(C),(22C!42!8!4)2,2()2,4()2,6()2,8(4CCCC2019/12/1725例1.24某广场有6个入口处，每个入口处每次只能通过一辆汽车，有9辆汽车要开进广场，问有多少种入场方案？解方法1：9辆汽车和5个标志的一个排列可表示一种入场方案，其重复数为5!，所求方案数为1.5组合987654321!5!142019/12/1726方法2：在9辆汽车和5个标志共14个位置中，首先选择5个作为标志的位置，这有种选择，对每一种选择，将9辆汽车依次填入剩余的位置，这有种填入方式，故所求方案数为1.5组合)5,14(C!9!5!14!9)5,14(C2019/12/1727例1.25求5位数中至少出现一个6，而被3整除的数的个数。正整数n能够被3整除的的充要条件是n的各个数字之和能够被3整除。设因为，所以于是iff1.5组合0111101010aaaankkkk)3(mod1103)(mod1010100110111aaaaaaaankkkkkk3)0(modn3)(mod0011aaaakk2019/12/17285位数共有90000个被3整除的有30000个在这30000个数中不包含6的数有个所求个数为30000-17496=125041.5组合17496398354321aaaaa2019/12/1729定理在n!中，质数p的最高幂其中。1.5组合mpnpnpnnp2)!(1mmpnp2019/12/1730例6．求1000!的末尾有几个0解1000!的末尾所含0的个数为1000!的因子分解中2和5的幂的最小者1000!因子分解中5的幂为：故1000!的末尾有249个01.5组合2491840200510005100051000510004322019/12/1731习题1.21.41.51.81.92019/12/1732允许重复的排列定理多重集合的r排列数为例用26个英文字母可以构造出多少个4个元音字母长度为8的字符串?解该问题是要求的包含4个元音字母的8排列数.在长度为8的字符串中,4个元音字母出现的位置有种每种元音出现的位置有个排列所求字符串的个数为},,,{21kaaaSrk},,,{zbaM)4,8(C44215)4,8(C442152019/12/1733定理多重集合的全排列数为其中证排列的个数为允许重复的排列},,,{2211kkanananSnnnnk21!!!!21knnnn),(),(),(121211kknnnnnCnnnCnnC!!!!21knnnn2019/12/1734例1.24某广场有6个入口处，每个入口处每次只能通过一辆汽车，有9辆汽车要开进广场，问有多少种入场方案？解方法1：9辆汽车和5个标志的一个排列可表示一种入场方案，所求方案数为允许重复的排列987654321!5!142019/12/1735例从{1,2,3}中取2个允许重复的组合为{1,1},{1,2},{1,3},{2,2},{2,3},{3,3}定理1.2在n个不同的元素中取r个进行组合，若允许重复，则组合数为证设n个不同的元素为1,2,3,…,n若是一个允许重复的r组合，不妨设，可构造一个上的不允许重复的r组合1.8.1允许重复的组合),(rrnC1},,,{raaa21raaa21},,,{121rn},,,{1121raaar2019/12/17361.8允许重复的组合反之给定一个上的不允许重复的r组合，我们可以如下得到一个{1,2,…,n}上的一个允许重复的r组合。故n个元素的允许重复的r组合与n+r-1个元素的不允许重复的组合之间有一一对应关系，故它们的组合