复旦大学计算机科学与工程系吴永辉离散数学排列组合基础知识

第十一章排列与组合11.1基本计数原理11.2集合的排列11.3集合的组合11.4多重集的排列和组合11.5容斥原理11.1基本计数原理组合数学在研究记数时经常要用到最基本的原理：加法原理和乘法原理。11.1基本计数原理1加法原理1）定理11.1（加法原理）设A和B是有限集合S的两个互不相交的子集，且AB=S，则|S|=|A|+|B|。/*划分*/证明：集合S中的元素在子集A中的个数有|A|个，因为A和B互不相交，且AB=S，故S中元素不在A中必在B中，且B中元素不在A中，所以S中不在A中的元素有|B|个，即|S|=|A|+|B|。2）加法原理实例：北京每天直达上海的客车有5次，客机有3次，则每天由北京直达上海的旅行方式有5+3=8种。2乘法原理1）定理11.2（乘法原理）设A和B是有限集合，|A|=p，|B|=q，则:|AB|=pq。2）乘法原理实例：从A到B有三条道路，从B到C有两条道路，则从A经B到C有32=6条道路。3例11.1某学生从2门数学课和4门计算机课中任选一门，则有2+4=6种选修方法。/*要选一门数学课或一门计算机课，但两者不同时都选，2门数学课和4门计算机课为该生的选课范围，则该生能以2+4=6种选修方法选择一门课。*/若他要选数学课和计算机课各一门，则有24=8种选修方法。乘法原理可被推广到3,4或任意有限多个集合的情形。例：梅利莎病毒：通过以含恶意宏的字处理文档为附件的电子邮件传播。当字处理文档被打开时，宏从用户的地址簿中找到前50个地址，并将字处理文档为附件发给它们。/*病毒按乘法原理飞快地扩散*/11.2集合的排列一、排列二、环排列一、排列1定义11.1（排列）从n个元素的集合S中有序选取的r个元素称为S的一个r-排列，不同的排列总数记为p(n,r)。若r=n，则称此排列为全排列。当rn，规定p(n,r)=0。2定理11.3对rn的正整数n,r，有p(n,r)=n(n-1)…(n-r+1)。证明方法：直接证明。证明：从集合S中选取第一个元素有n种可能，再选取第二个元素有n-1种可能，……，依次类推，选取第r个元素有n-r+1种可能，由乘法原理得，p(n,r)=n(n-1)…(n-r+1)。/*证明原理：乘法原理*/3例:应用加法原理,乘法原理和排列例11.2从n个编号不同的球中选取r(0rn)个排成一行，则可能出现的不同行有p(n,r)个。4例11.3某工序加工一、二、三、四、五共5道工序，则安排这些加工工序共有p(5,5)=120种方法。若工序一必须先加工，则共有p(4,4)=24种方法。若工序三不能放在最后加工，则工序三的加工安排p(4,1)=4，其余工序安排p(4,4)=24，根据乘法原理共有4*24=96种方法。例11.4在上例中,(1)若规定工序四必须紧跟工序三后面,则有多少种安排方法?(2)若规定工序二必须在工序五的前面,有多少种安排方法?解：(1)把工序三、四看成一个工序,因此有p(4,4)=24种方法;(2)把工序二放在工序五的前面,有四种情况:1）把工序二、五放在一起，有24种情况；2）工序二、五中隔一道工序，则有p(3,3)*P(3,1)=18种情况；2）工序二、五中隔两道工序，则有p(2,2)*P(3,2)=12种情况；3）工序二、五中隔三道工序，则有p(1,1)*P(3,3)=6种情况；由加法原理，把工序二放在工序五的前面,有60情况。二、环排列1定义11.2（r-环排列）从有限集合A={a1,a2,…,an}上选取r个元素排成一个环形，这样的排列称为A的一个r-环排列。2定理11.4由n个元素组成的集合A的r-环排列数是：P(n,r)/r证明：把A的所有r-线形排列分成组，使得同组的每个线形排列可以连接成一个环排列。又因一个r-环排列可产生r个r-线形排列，即每个组中恰含有r个r-线形排列，所以A的r-环排列数为p(n,r)/r。当r=n时，A的环排列数为p(n,n)/n=(n-1)!。3应用加法原理,乘法原理和环排列例11.5(1)10个男孩和5个女孩站成一排，若没有两个女孩相邻，问有多少种排法？(2)10个男孩和5个女孩站成一个圆圈，若没有两个女孩相邻，问有多少种排法？解：把男孩看成格子的分界，而每两个男孩之间则看成一个空格。（1）10个男孩站成一排的排法有p(10,10)种，对于每一种排法有11个空位置放置女孩，有p(11,5)种放法。由乘法原理得所求排列数是p(10,10)p(11,5)=(10!11!)/6!。（2）10个男孩站成一圈的排法实际上就是10个元素的环排列数，为p(10,10)/10。而对于每一种排法有10个空位置放置女孩，故方法数为p(10,5)。由乘法原理得所求排列数是(p(10,10)/10)p(10,5)=(10!9!)/5!11.3集合的组合一、集合的组合二、二项式系数及组合恒等式一、集合的组合1定义11.3从n个元素的集合A中无序选取r个元素组成S的子集称为的一个r-组合，不同的组合总数记为C(n,r)。当n0，规定C(n,0)=1。当rn时，C(n,r)=0。2定理11.5对于一切rn，有(,)!(,)!!()!pnrnCnrrrnr证明：C(n,r)表示从n个元素中选取r个元素的选数法，因为对r个元素进行行排列有r!种。由乘法原理，从n个元素中选取r个元素的排列数是p(n,r)=C(n,r)r!，即C(n,r)=n!/(r!(n-r)!)。3推论11.1对于一切rn，有C(n,r)=C(n,n-r)。证明：C(n,r)=n!/(r!(n-r)!)=n!((n-(n-r))!(n-r)!)=C(n,n-r)。4应用加法原理,乘法原理和组合例11.6在100件产品中，有2件次品。（1）从其中任意抽取3件，方式数是多少？（2）抽取的3件产品中恰有2件为次品的方式数是多少？（3）抽取的3件产品中恰有1件次品的方式数是多少？（4）抽取的3件产品中至少有1件为次品的方式数是多少？（5）抽取的3件产品中没有次品的方式数是多少？解：（1）组合问题。C(100,3)=161700种。(2)2件从次品中选取，有C(2,2)种；1件从正品中选，有C(98,1)种，由乘法原理，共有C(2,2)C(98,1)=98种。（3）1件从次品中选取，有C(2,1)种；2件从正品中选，有C(98,2)种，由乘法原理，共有C(2,1)C(98,2)=9506种。（4）抽取的3件产品中至少有1件为次品，有两种情况，即恰有1件次品和恰有2件次品。故共有9506+98=9604种。（5）没有次品即意味着是从正品中选取，有C(98,3)=152096种。例11.7从1,2,…,300之中任取3个数，使得它们的和能被3整除，有多少种选取方法？解：把1,2,…,300分成A,B,C三个组。A={x|x1(mod3)},B={x|x2(mod3)},C={x|x0(mod3)}.设任取的3个数i,j,k，则选取是无序的且满足i+j+k0(mod3)，选法可分为两类：i,j,k都取自同一组，共有三个组，方法数为3C(100,3)；i,j,k分别取自A,B,C三个集合，由乘法原理，方法数为(C(100,1))3；由加法原理，总取法数为3C(100,3)+(C(100,1))3。二、二项式系数及组合恒等式1定理11.6（二项式定理）设n为正整数，对一切x和y有：0()(,)nnknkkxyCnkxyPascal三角形/杨辉三角形Pascal三角形/杨辉三角形111121133114641。。。。。。。。Pascal三角形/杨辉三角形定理Pascal三角形/杨辉三角形定理:对于任意的1kn，则C(n+1,k)=C(n,k)+C(n,k-1)。证明：令X是n元集合，aX。则C(n+1,k)为Y=X{a}的k-元素子集的个数。Y的k-元素子集分为两类：1）Y的不包含a的子集；2）Y的包含a的子集；第一类子集相当于从X中选取k个元素，所以共有C(n,k)个；第二类子集相当于选取a后再从X中选取k-1个元素，所以共有C(n,k-1)个；所以有C(n+1,k)=C(n,k)+C(n,k-1)。二项式定理证明方法证明方法1证明方法2二项式定理证明方法1通过n个对象的r-组合数可得出表达式(a+b)n的展开式。在n个因子中选k个b和n-k个a，可得项an-kbk。因为从n个对象中选择k个共有C(n,k)种方法，所以项an-kbk共有C(n,k)个。所以(a+b)n=C(n,0)anb0+C(n,1)an-1b1+C(n,2)an-2b2+…….+C(n,n-1)a1bn-1+C(n,n)a0bn二项式定理证明方法2应用数学归纳法，通过对n用数学归纳法，同样证明二项式定理。二项式定理例题例1：利用二项式定理展开(3x-2y)4。解题思想：代数法/代入：解：设a=3x，b=-2y，n=4，可得：(3x-2y)4=(a+b)4=C(4,0)a4b0+C(4,1)a3b1+C(4,2)a2b2+C(4,3)a1b3+C(4,4)a0b4回代：=81x4-216x3y+216x2y2-96xy3+16y4例2：求(a+b)9的展开式中a5b4项的系数。解：由二项式定理，C(n,k)an-kbk=C(9,4)a5b4=126a5b4。所以，a5b4项的系数是126。例3：求(a+b+c)9的展开式中a2b3c4项的系数。解：(a+b+c)9=(a+b+c)……(a+b+c)(9项)在这9项中，2次选a，3次选b，4次选c，可得项a2b3c4。在9项中，2次选a共有C(9,2)种选法；当a选定后，选b共有C(7,3)种选法；余下4项选c。a2b3c4项的系数为C(9,2)C(7,3)=1260。2二项式定理的推论1)推论11.2对任何正整数n，有：C(n,0)+C(n,1)+……+C(n,n)=2n证明：令x=y=1，根据二项式定理，则有2n=(1+1)n=C(n,0)+C(n,1)+……+C(n,n)。2)推论11.3对任何正整数n，有：C(n,0)-C(n,1)+C(n,2)-……+(-1)nC(n,n)=0证明：令x=-1,y=1，根据二项式定理，则有0=(-1+1)n=C(n,0)-C(n,1)+……+(-1)nC(n,n)。3牛顿二项式定理1676年，牛顿推广了二项式定理，得到(x+y)的展开式。其中，是任意实数。定理11.7（牛顿二项式定理）设是一个实数，则对一切满足|x/y|1的x和y有：其中C(,k)应作如下推广：对任意实数，整数k有(1)......(1),0!(,)1,00,0kkkCkkk0()(,)kkkxyCkxy4牛顿二项式定理的推论取=-n,y=1推论11.4对任何正整数n，对|x|1有：001(1)(1,)(1)1(1,)(1)kkknkknCnkkxxCnkkxx5定理11.8设m,n,r,k为正整数，则下列恒等式成立。(1)(,)(1,1);(2)(,)(1,)(1,1)()nCnkCnkkCnkCnkCnkPascal杨辉公式，公式11221(3)(,)2(4)(,)(1)2(5)(,)(,)(,)(,),nnknnkkCnknkCnknnCnrCrkCnkCnkrk这里rk；(6)(,0)(,)(,1)(,1)......(,)(,0)(,);VandermondeCmCnrCmCnrCmrCnCmnr恒等式：这里rmin{m,n}。(7)C(m,0)C(n,0)+C(m,1)C(n,1)+……+C(m,m)C