北航现代工程数学第1、2、3课ppt课件

教材和参考书,教材IntroductoryCombinatorics（组合数学）R.A.Bruadli著机械工业出版社第四版（中文）45元第四版（英文）59元销售经理余勇考书组合数学引论孙淑玲许胤龙中国科学技术大学出版社组合数学卢开澄清华大学出版社成绩作业40%考试60%,组合数学,第1章什么是组合数学第2章鸽巢原理第3章排列与组合第4章生成排列和组合第5章二项式系数第6章容斥原理及应用第7章递推关系和生成函数第8章特殊计数序列,第1章什么是组合数学,组合数学是研究“安排”的学科。主要研究以下四类问题。存在性问题（是否存在某种安排）计数问题（安排的个数、枚举、分类）构造问题（寻找安排的算法）优化问题（找出一定条件下的最优安排）,排课表问题,需安排甲、乙、丙、丁四位教师教英语、日语、德语、法语四门课，每人教一门。甲和乙能教英语、日语，丙能教英语、德语、法语，丁只能教德语，是否能够排出课表？甲、乙、丙、丁分别教英语、日语、法语、德语。,棋盘完美覆盖问题,一个多米诺骨牌可覆盖同一行或同一列两相邻方格。若用若干多米诺骨牌覆盖棋盘所有方格，并且多米诺骨牌不重叠，则称该覆盖为完美覆盖。mn棋盘有完美覆盖iffm和n中至少有一个是偶数。当m是偶数时，每块多米诺骨牌竖放。当m是奇数且n是偶数时，每块多米诺骨牌横放。当m和n都是奇数时，棋盘的方格数mn是奇数。,幻方,在由1,2,n2组成的nn方阵中，若每行之和、每列之和、每条对角线之和都相等，则称该方阵为n阶幻方。对于n2，存在n阶幻方。例如，左下方方阵是3阶幻方。若右下方方阵是2阶幻方，则u+v=u+y，所以v=y，矛盾。无2阶幻方。,计数问题,将三角形顶点染红、蓝两色，共有23=8种方法，若一种染色旋转后可变为另一种，则认为这两种染色相同，那么仅有4种方法（分别有0,1,2,3个顶点染红色）。有多少种方法将正整数n表示成正整数之和，即n有多少个分拆。如4有5个分拆：4，3+1，2+2，2+1+1，1+1+1+1,构造问题,构造n阶幻方的方法，其中n是奇数。将1放在第一行中间。自左下至右上沿对角线顺次放随后各数，将最后一行认为是第一行上面的行，第一列认为是最后一列右面的列。若要放数的位置已有数，则将数放在原数下方。,优化问题,第2章鸽巢原理,本章主要讨论简单形式和加强形式的鸽巢原理及其应用。本章还简单讨论鸽巢原理的推广：Ramsey定理。2.1鸽巢原理：简单形式2.2鸽巢原理：加强形式2.3Ramsey定理作业,2.1鸽巢原理：简单形式,定理2.1.1若将多于n个物体放入n个盒子，则至少有一个盒子中的物体数大于1。设f:AB，将A看做物体的集合，B看做盒子的集合，物体a放在盒子f(a)中。如果|A|B|，则f不是从A到B的单射（一对一的函数）。,鸽巢原理应用,从1,2,200中任意选出101个数，必有两个数其中一个能够整除另一个。证明将数表示成形式2ka，其中a是奇数。小于200的奇数只有100个，即1,3,199，所以这101个数中必有两数表示为2ka和2ja，2ka|2ja当且仅当kj,鸽巢原理应用,设n是正整数，必存在由数字0和7组成的正整数能被n整除。,中国剩余定理,设m和n是互素的正整数，即它们的最大公约数是1，0am，0bn，必存在正整数x使得，m除x余a，n除x余b。证明考虑n个数a,m+a,(n1)m+a若其中两数im+a和jm+a被n除余数相同，则n|(ij)m，n|(ij)，0|ij|5。,r(3,3)=6,设K6的六个顶点分别为v1,v6。v1与v2,v6的连边中必有三个是同色的，不妨设v1与v2,v3,v4的连边都是红色，若三角形v2v3v4中某边是红色的，则有红三角形。若三角形v2v3v4中边都是蓝色的，则有蓝三角形。因此，K6K3,K3。r(3,3)6，因此，r(3,3)=6。,显然，r(m,n)=r(n,m)。r(m,2)=m。若Km中都是红边，则有红Km；若Km中有蓝边，则有蓝K2。所以KmKm,K2。若Km1中都是红边，则既没有红Km，也没有蓝K2。所以Km1Km,K2不成立。40r(3,10)=r(10,3)43，即K43K3,K10成立且K39K3,K10不成立。对于i=40,41,42，不知KiK3,K10是否成立。,r(k,l)表,可以将Ramsey定理推广到任意多种颜色的情况。引进记号KpKn1,Knk表示：用k种颜色c1,ck为Kp的边任意染色，或者有一个被染成c1色的Kn1，或者有一个被染成ck色的Knk。Ramsey定理若n1,nk2，则有正整数p使得KpKn1,Knk使得KpKn1,Knk成立的最小正整数p称为Ramsey数r(n1,nk)。r(3,3,3)=17,Ramsey定理是加强形式鸽巢原理的推广。令t=1，将“为1元子集u染色ci”看作“将u放入第i个盒子中”，可以得出r1(q1,qk)=q1+qkk+1,作业,7，11，14，17,第3章排列与组合,3.1四个基本的计数原理3.2集合的排列3.3集合的组合3.4多重集的排列3.5多重集的组合作业,3.1四个基本的计数原理,加法原理设S=S1S2Sm是m个两两不相交集合之并，即若ij，则SiSj=。那么，|S|=|S1|+|S2|+|Sm|。乘法原理|A1Am|=|A|Am|其中A1Am=(a1,am):a1A1,amAm,减法原理设A是有限集合U的子集，A的补集则A的元素个数|A|由以下公式给出：除法原理如果有限集S被分成包含同样多个元素的k部分，那么部分的数目k由以下公式给出：,相等原理如果在集合A和B之间存在一一对应，则|A|=|B|。例n元集S=1,n的子集个数等于由0和1组成的长度为n的串的个数。证明可在S的子集的集合与由0和1组成的长度为n的串的集合之间建立一一对应如下：让S的每个子集A对应串a1an，其中对于每个iS，,例确定10!的正整数因子数,10!=2310=2834527m|10!iffm=2i3j5k7l,其中0i8,0j4,0k2,0l110!的正整数因子数=|(i,j,k,l):0i8,0j4,0k2,0l1|=9532=270,恰有一位数字是5的n，则P(n,r)=0。P(n,0)=1（空序列），P(n,1)=n。,排列数的计算公式,定理3.2.1若rn，则证明第1个元素有n种选择，第2个元素有n1种选择，。n元集的全排列数为n!。,各位非0、互异、数字5和6不相邻的7位数有多少个？解法1不出现5和6的满足条件的7位数是集合A=1,2,3,4,7,8,9的全排列，有P(7,7)个。以下用代表不是5和6的数字，用代表数字5或6。考虑只出现5，不出现6的数。从A中取出6个数字排好，再在7个位置之一插入5，有7P(7,6)个。出现6不出现5的数也有7P(7,6)个。,考虑5和6都出现的情况。第1位是5。将不是6的5位排好，将6插入5个位置之一，有5P(7,5)个。5最后位是5，有5P(7,5)个。5在中间位置。将不是5和6的5位排好，将5插入4个位置之一，将6插入5个位置之一，有45P(7,5)个。5,各位不是0、互异、数字5和6不相邻的7位数有367!67!=307!个。,解法2,循环排列,普通排列更恰当些应叫做线性排列。把r个元素排成一个圆称为循环r-排列，或r-圆排列。每个循环r-排列对应r个不同的线性r-排列。例如，左边的循环4-排列对应4个线性4-排列：1234，2341，3412，4123,循环排列数,定理3.2.2n元集的循环r-排列数为r元集的循环r-排列数为(r1)!。,例10男生5女生围圆桌聚餐，任何两个女生不相邻的坐法有多少种？解男生先坐好，有9！种坐法。固定一种男生坐法，然后让女生插入10个空档，女生之间还存在排序问题，故有P(10,5)种排法。所以，共有9!P(10,5)种坐法。例10人围坐一圆桌，其中甲、乙两人不愿挨着坐，共有多少种坐法？解若不考虑甲和乙是否挨着，有9!种坐法。若甲固定坐在乙左边，可将甲和乙看作一人，有8!种坐法。若甲固定坐在乙右边，也有8!种坐法。所以，满足条件的坐法有9!28!种。,3.3集合的组合,集合S的r-组合即为S的r元子集，将n元集的r-组合数记为,推论3.3.1设0rn，则证法一设|S|=n，让S的r-组合A对应它的补集(nr)-组合，可在r-组合与(nr)-组合之间建立一一对应。证法二,定理3.3.2证明n元集有0,1,n元子集。对于n元集S=a1,a2,an的每个子集A，对每个ai，可有两种选择，aiA或者aiA，所以S有2n个子集。,某班有男生21人，女生14人，需选举4人组成班委会，要求班委会有男有女，可能有多少种选举结果？解法一班委会有i个女生的选举结果有种，选举结果总数为解法二若不要求班委会有男有女，则选举结果数为，所求数为,某班有男生21人，女生14人，需选举4人组成班委会，要求班委会有男有女，可能有多少种选举结果？解从男、女生中各选一人，再任选两人，故选举结果总数为这样做对吗？如果不对，错在哪里？,3.4多重集的排列,定理3.4.1多重集S=a1,a2,ak的r-排列数为kr。证明S的r-排列即为a1,a2,ak的长度是r的串，其中每个元素都有k种选择，所以，r-排列数为kr。,定理3.4.2设n=n1+n2+nk，则多重集S=n1a1,nkak的全排列数为证法2将所有n个元素都看作不同的，则全排列数为n！。交换排列中的同一元素，得到同样的排列，所以每个排列重复了n1!n2!nk!次，所以S的全排列数为,证明可在多重集S=n1a1,nkak的全排列集合和满足要求的将物体放入做标签盒子的方法集合之间建立一一对应如下：对于S的每个全排列d1dn，若di是aj，则将ci放入盒子Bj。所以，放入做标签盒子的方法数也是对于放入i个物体的li个盒子，有li!种方法为盒子做标签，所以放入不做标签盒子的方法数为,例将4个元素a,b,c,d放入红色盒子与蓝色盒子，每个盒子放两个元素，有以下6种方法：红色盒子：a,b；蓝色盒子：c,d。红色盒子：c,d；蓝色盒子：a,b。红色盒子：a,c；蓝色盒子：b,d。红色盒子：b,d；蓝色盒子：a,c。红色盒子：a,d；蓝色盒子：b,c。红色盒子：b,c；蓝色盒子：a,d。若不为盒子涂色，则第1,2种方法成为一种方法，第3,4种方法成为一种方法，第5,6种方法成为一种方法，只有3种方法。,例将5个元素a,b,c,d,e放入红色盒子与蓝色盒子，红色盒子放1个元素，蓝色盒子放4个元素，有以下5种方法：红色盒子：a；蓝色盒子：b,c,d,e。红色盒子：b；蓝色盒子：a,c,d,e。红色盒子：c；蓝色盒子：a,b,d,e。红色盒子：d；蓝色盒子：a,b,c,e。红色盒子：e；蓝色盒子：a,b,c,d。若不为盒子涂色，仍然有5种方法。,定理3.4.4有k种颜色的n个车，其中第i种颜色的有ni个。将这n个车摆放在的棋盘上使得任何两个车不能互相攻击，摆放方法数为证明用(i,j)表示第i行第j列方格。占据(i1,j1)和(i2,j2)的车不能互相攻击当且仅当i1i2且j1j2,若n个车摆放在(1,j1),(2,j2),(n,jn)，则j1j2jn是1,2,n的一个全排列。用ci表示第i种颜色的车。摆放车的位置(1,j1),(2,j2),(n,jn)确定之后，n1c1,n2c2,nkck的每个全排列对应一种摆放法。例如，c1c1c4c2c3c2c1c3对应第1,2,7行摆放c1，第4,6行摆放c2，第5,8行摆放c3，第3行摆放c4。因此，摆放方法数为,例求S=3a,2b,4c的8排列数。,2a,2b,4c的8排列数为3a,1b,4c的8排列数为3a,2b,3c的8排列数为S的8排列数为420+280+560=1260。,3.5多重集的组合,多重集n1a1,n2a2,nkak的r-组合是一个多重集m1a1,m2a2,mkak，其中r=m1+m2+mk，0mini，i=1,k。例如，2a,1b,3c的2-组合如下：2a，1a,1b，1a,1c，1b,1c，2c,定理3.5.1多重集S=a1,a2,ak的r-组合数为证明x1a1,x2a2,xkak是S的r组合当且仅当(x1,x2,xk)是方程x1+x2+xk=r的非负整数解。S的r-组合数=方程x1+x2+xk=r的非负整数解的个数。令T=r1,(k1)。(x1,x2,xk)是x1+x2+xk=r的非负整数解iff是T的全排列。S的r-组合数=T的全排列数。,求S=9a,9b,9c,9d的使得每种元素至少出现一次的9-组合个数。令y1=x11，y2=x21，y3=x31，y4=x41