组合数学第一章.

组合数学——第一章主讲教师数学学院魏毅强教授联系电话[phone]Email:[e-mail]@tyut.edu.cn2第一章排列组合1.1加法法则与乘法法则1.4Stirling近似公式1.2一一对应原理1.5全排列的生成算法1.6组合的生成1.3排列与组合[e-mail]3第一章排列组合1.1加法法则与乘法法则1.3Stirling近似公式1.4模型转换1.5全排列的生成算法1.6组合的生成1.7可重组合1.8若干等式及其组合意义1.9应用举例1.2排列与组合[e-mail]41.1加法法则与乘法法则[加法法则]设事件A有m种产生方式，事件B有n种产生方式，则事件A或B之一有m+n种产生方式。集合论语言：若|A|=m,|B|=n,AB=,则|AB|=m+n。例1书架上有数学类书5本，计算机类书3，任取其中一本，有多少种取法。共有5+3=8种取法[e-mail]51.1加法法则与乘法法则[乘法法则]设事件A有m种产生式，事件B有n种产生方式，则事件A与B有m·n种产生方式。集合论语言：若|A|=m,|B|=n,AB={(a,b)|aA,bB},则|AB|=m·n。例2从A到B有三条道路，从B到C有两条道路，则从A经B到C有几条道路?有32=6条[e-mail]6例3机动车牌照字由7个字符组成，第一个字符是汉字，表示省份或军区等，第二个字符是英文字母，表示市、区或行业等，其余5位可选自英文字母或数字（有时用第三个字符表示行业，如出租用T)，问一个市的机动车拥有量最多是多少？机动车拥有量最多是：(26+10)5辆。出租车拥有量最多是：(26+10)4辆。1.1加法法则与乘法法则[e-mail]71.1加法法则与乘法法则例4某种样式的运动服的着色由底色和装饰条纹的颜色配成。底色可选红、蓝、橙、黄，条纹色可选黑、白，则共有42=8种着色方案。若此例改成底色和条纹都用红、蓝、橙、黄四种颜色的话，则，方案数就不是44=16，而只有43=12种。在乘法法则中要注意事件A和事件B的相互独立性。[e-mail]81.1加法法则与乘法法则例51)求小于10000的含1的正整数的个数2)求小于10000的含0的正整数的个数小于10000的正整数可看做4位数,共有104－1=9999个（0000除外）不含1的4位数有：94－1＝6560个含1的4位数有：9999－6560=3439个另:全部4位数有104个,不含1的四位数有94个,含1的4位数为两个数的差:104－94=3439个[e-mail]92)“含0”和“含1”不可直接套用。0019(含1但不含0)。在组合的习题中有许多类似的隐含的规定，要特别留神。不含0的1位数有9个，2位数有92个，3位数有93个，4位数有94个不含0小于10000的正整数有9+92+93+94=(95－1)/(9－1)=7380个含0小于10000的正整数有9999－7380=2619个1.1加法法则与乘法法则[e-mail]101.1加法法则与乘法法则例6求除尽n=73.112.134的数的个数除尽n=73.112.134的数可表示为x=7a.11b.13c其中40,20,30cba故整除的个数为60534[e-mail]111.2一一对应原理如我们说A集合有n个元素|A|=n，无非是建立了将A中元与[1,n]元一一对应的关系。在组合计数时往往借助于一一对应实现模型转换.比如要对A集合计数，但直接计数有困难，于是可设法构造一易于计数的B，使得A与B一一对应。[一一对应原理]如果事件A与事件B间存在一一对应（双射），则事件A与B一样大，即|A|=|B|。[e-mail]12例7在65名选手之间进行淘汰赛(即一场的比赛结果，失败者退出比赛),最后产生一名冠军，问要举行几场比赛？另一种思路是淘汰的选手与比赛(按场计)集一一对应。淘汰64名选手，需要64场比赛。1.2一一对应原理一种常见的思路是按轮计场（费事）：32+16+8+4+2+1+1=64注意，每轮都有一人轮空。[e-mail]13例8设凸n边形的任意三条对角线不共点，求对角线在多边形内交点的个数。可以先计算对角线的个数，然后计算交点，但是存在在多边形内无交点的情形，比较复杂。可以考虑对应关系：多边形内交点to多边形四个顶点。可以证明这是一一对应（映射，单且满）。1.2一一对应原理交点的个数：[e-mail]141.3排列与组合定义从n个不同的元素中，取r个不重复的元素，按次序排列，称为从n个中取r个的无重排列。排列的全体组成的集合用P(n,r)表示。所有不同排列的个数称为排列数，也记为P(n,r)。或Prn，或Arn。当r=n时称为全排列。所有不同全排列的个数记为Pn或An。[e-mail]151.3排列与组合从n个中取r个的排列的典型例子是(取球模型):从n个不同的球中,取出r个,放入r个不同的盒子里,每盒1个。第1个盒子有n种不同选择，第2个有n-1种选择，······，第r个有n-r+1种选择。故由乘法原理有P(n,r)=n(n-1)······(n-r+1)=n!/(n-r)![e-mail]16规定1.3排列与组合1,1!00nP从n中取出r个排列的模型，可看作是从n个有区别的球中取出r个，放入r个有标记的盒子中，且无一空盒。特别，当r=n时有!nPPnnn显然)!(!!!rnnPPrnPrnnrrn[e-mail]17例9由5种颜色的星状物，20种不同的花排列成如下图案：两边是星状物，中间是3朵花，问共有多少种这样的图案？两边是星状物，从五种颜色的星状物中取两个的排列的排列数是P(5,2)=20根据乘法法，则得图案数为20种不同的花取3种排列的排列数是P(20,3)=20×19×18=684020×6840=1368001.3排列与组合[e-mail]18例10A单位有7名代表，B单位有3位代表，排成一列合影，如果要求B单位的3人排在一起，问有多少种不同的排列方案。若A单位的2人排在队伍两端，B单位的3人不能相邻，问有多少种不同的排列方案？B单位3人按一个元素参加排列，P(8,8)×P(3,3)A单位的人排法固定后A*A*A*A*A*A*A，B单位第一人有6种选择，第二人有5种，第三人有4种，因此答案为P(7,7)×6×5×41.3排列与组合[e-mail]19于是我们只需要计算Si即可。例11求由{1,3,5,7}组成的不重复出现的整数的总和解：这样的整数可以是1位数,2位数,3位数,4位数,S=S1+S2+S3+S4,S1=1+3+5+7=16,1.3排列与组合若设Si，i=1,2,3,4，是i位数的总和，则[e-mail]20S2=3(1+3+5+7)10+3(1+3+5+7)=480+48=528S4=6(1+3+5+7)1000+6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=96000+9600+960+96=106656S3=6(1+3+5+7)100+6(1+3+5+7)10+6(1+3+5+7)=9600+960+96=10656S=16+528+10656+106656=117856两位数有：13,15,17,31,33,35,37,51,53,55,57,71,73,75,77，所以同理1.3排列与组合[e-mail]211.3排列与组合例12假设一高速路口有4个出口，现有9辆车子从这6个口下高速，问有多少种不同的下法？解法一假设出口编号为：K1，K2，K3，K4；9辆车的编号为1,2,3,4,5,6,7,8,91号车选择出口有4种；2号车选择就有5种，因为当2号车与1号车选同一出口时，两车有前后顺序的问题；同理3号车有6种选择；依此类推，9号车应有12种选择。故不同的下法共有4*5*6*…*12=12!/3![e-mail]221.3排列与组合解法二如果只有一个出口，则显然9辆车的不同下法为9！；如果有两个出口，则可以加入一个分隔符F与车辆号一起进行排列，在F的左右排列可看作是分别从两个出口的一种下法，故此时的下法为10！。本题有4个出口，应加入三个分隔符，所以不同的下法有12!/3!.注意到，分隔标记F是无区别的[e-mail]231.3排列与组合解法三在9辆车的标号与3个分隔符共同组成的12个标记中，首先选出3个作为分隔符，不同选法有C(12,3)，然后余下的9个作为车辆标号进行排列，应有9!种不同方案，故总的下法有C(12,3)*9!=12!/3!注意本解法用到了组合的概念，它也可以作为基本的组合模型[e-mail]241.3排列与组合定义从n个不同元素中取r个不重复的元素组成一个子集，而不考虑其元素的顺序，称为从n个中取r个的无重组合。rnC组合的全体组成的集合用C(n,r)表示，所有不同组合的个数记为C(n,r)或Cnr若球不同，盒子相同，则是从n个不同元素中取r个不重复的组合的模型。[e-mail]25若球不同，盒子相同，则是从n个中取r个的组合的模型。若放入盒子后再将盒子标号区别，则又回到排列模型。每一个组合可有r!个标号方案。故有C(n,r)·r!=P(n,r),即C(n,r)=P(n,r)/r!=n!———r!(n-r)!1.3排列与组合[e-mail]261.3排列与组合例13有5本不同的俄文书，7本不同的英文书，10本不同的中文书。如果从中任1)取2本不同文字的书；2)取2本相同文字的书；3)任取两本书问各有多少种不同的取法？解1)5×7+5×10+7×10=155;2)C(5,2)+C(7,2)+C(10,2)=10+21+45=76;3)155+76=231=()[e-mail]271.3排列与组合例14从[1,300]中取3个不同的数，使这3个数的和能被3整除，有多少种方案？解将[1,300]分成3类：A={i|i≡1(mod3)}={1,4,7,…,298},B={i|i≡2(mod3)}={2,5,8,…,299},C={i|i≡3(mod3)}={3,6,9,…,300}.要满足条件，有四种解法：1)3个数同属于A;2)3个数同属于B3)3个数同属于C;4)A,B,C各取一数.故共有3C(100,3)+1003=485100+1000000=[e-mail]