《组合数学基础》PPT课件.ppt

,组合数学基础,组合数学基础,1加法原理与乘法原理11 加法原理：做一件事情，完成它可以有n类办法，在第一类办法中有m1 种不同的方法，在第二类办法中有 m2种不同的方法，在第n类办法中有 mn种不同的方法。那么完成这件事共有 N=m1+m2+.+mn 种不同的方法。12 乘法原理：做一件事情，完成它需要分成n个步骤，做第一步有m1 种不同的方法，做第二步有 m2种不同的方法，做第n步有 种mn不同的方法，那么完成这件事有 N=m1*m2*.*mn 种不同的方法。,13 两个原理的区别：一个与分类有关，一个与分步有关；加法原理是“分类完成”，乘法原理是“分步完成”。,2排列、组合及计算公式,21排列及计算公式 从n个不同元素中，任取m(mn)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(mn)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号 p(n,m)表示.p(n,m)=n(n-1)(n-2)(n-m+1)=n!/(n-m)!(规定0!=1).,22 组合及计算公式 从n个不同元素中，任取m(mn)个元素并成一组，叫做从n个不同元素中取出m个元素的一个组合；从n个不同元素中取出m(mn)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号c(n,m)表示.c(n,m)=p(n,m)/m!=n!/(n-m)!*m!)；c(n,m)=c(n,n-m);23 n个元素中取出r个元素的循环排列数p(n,r)/r=n!/r(n-r)!.24 n个元素被分成k类，每类的个数分别是n1,n2,.nk这n个元素的全排列数为 n!/(n1!*n2!*.*nk!).,25 可重复组合 如果上述组合定义中每一个元素可重复选取，则称为n元集中的可重复r-组合。n元集中的可重复r-组合的总数为C(n+r-1,r)。,证明：从n元集中可重复地选取r个元素，设第一个元素选x1个，第二个元素选x2个，第n个元素选xn个，则方程x1+x2+xn=r的非负整数解的个数就是n元集中的可重复r-组合的总数。该方程x1+x2+xn=r的一个非负整数解可解释为将r个1排成一排，插入n-1个分隔符，把r个1分成n段，n段中的1的个数即是方程的一个解。插入n-1个分隔符的过程实际上就是从n+r-1个位置中选择n-1个位置放分隔符，其余r个位置放1，共有C(n+r-1,n-1)=C(n+r-1,r)。可重复组合也可解释为：有n类元素,每类的个数无限,从中取出r个元素的组合。,3二项式定理,C(n,0)+C(n,1)+C(n,n-1)+C(n,n)=2n 证明：等式左边包含了n元集的从零个元素到n个元素的全部组合，每一种组合与一个n位二进制数一一对应，对应方式为：n 位二进制数共有n位，每一位对应n元集的一个元素，如果n 位二进制数某一位上为1，则表示选中该位对应的元素，否则表示未选中该位对应的元素，这样一个n位二进制数就对应一种组合；反过来每一种组合同样对应一个n位二进制数，而n位二进制数的总数为2n。,4.杨辉三角,1 1 1 1 2 1 1 3 3 1 1 4 6 4 1 1 5 10 10 5 1 1 6 15 20 15 6 1 1 7 21 35 35 21 7 1 1 8 28 56 70 56 28 8 1 1 9 36 84 126 126 84 36 9 1 杨辉三角的每一行中的第一个数和最后一个数均为1,其余位置上的数可利用其上一行中的数递推计算出来,其值为上一行中位于同一列和前一列的两个数之和。,5.鸽巢原理,5.1简单形式 如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。例2：在13个人中必存在两个人，他们的生日在同一月份里。例3：设有n对已婚夫妇。为保证有一对夫妇被选出，至少要从这2n个人中选出多少人？（n+1）5.2加强形式 令q1,q2,.qn为正整数。如果将 q1+q2+.+qn-n+1个物体放入n个盒子内,那么或者第一个盒子至少含有q1个物体,或者第二个盒子 至少含有q2个物体,.,或者第n个盒子含有qn个物体.例4:一篮子水果装有苹果、香蕉、和橘子。为了保证篮子内或者至少8个苹果或者至少6个香蕉或者至少9 个橘子，则放入篮子中的水果的最小件数是多少？（21件）,6.容斥原理及应用,设S为有穷集，P1，P2，Pm是m条性质。S中的任一元素x对于这m条性质可能具有其中的一种、二种、n种，也可能任何性质都没有。设Ai(i=1,2,m)表示S中具有Pi的元素构成的子集。这时容斥原理可叙述为：定理：S中不具有性质P1，P2，Pm的元素数是：如:m=3,时上式为：=|S|-(|A1|+|A2|+|A3|)+(|A1A2|+|A1A3|+|A2A3|)|A1A2A3|,推论:至少具有性质P1,P2,.Pm之一的集合S的物体的个数有：|A1A2.Am|=|S|=|Ai|-|AiAj|+|AiAjAk|+.+(-1)m+1|A1A2.Am|例4：求从1到1000不能被5，6，和8整除的整数的个数？（1000-（200+166+125）+（33+25+41）-8=600）,7.常见递推关系及应用,7.1算术序列 每一项比前一项大一个常数d；若初始项为h0：则递推关系为 hn=hn-1+d=h0+nd；对应的各项为：h0，h0+d，h0+2d，.,h0+nd;前n项的和为(n+1)h0+dn(n+1)/2 例5:1,2,3,.例6:1,3,5,7.等都是算术序列。7.2几何序列 每一项是前面一项的常数q倍 若初始项为h0：则递推关系为 hn=h0qn-1q=h0qn；对应的各项为:h0，h0q1，h0q2，.,h0qn例7:1,2,4,8,16,.例8:5,15,45,135,.等都是几何序列;前n项和为(qn+1-1)/(q-1)h0,7.3 Fibonacci序列 除第一、第二项外每一项是它前两项的和；若首项为f0为0,则序列为0，1，1，2，3，5，8.递推关系为(n=2)fn=fn-1+fn-2 前n项的和Sn=f0+f1+f2+.+fn=fn+2-1 例9:以下是Fibonacci的示例:(1)楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法?(2)有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?(3)有n*2的一个长方形方格,用一个1*2的骨牌铺满方格。求铺法总数？,7.4 错位排列,首先看例题：例10：在书架上放有编号为1,2,.n的n本书。现将n本书全部取下然后再放回去,当放回去时要求每本书都不能放在原来的位置上。例如:n=3时:原来位置为:123放回去时只能为:312或231这两种问题:求当n=5时满足以上条件的放法共有多少种?(不用列出每种放法)(44),错位排列的递推公式,1，2，3，.,n错位排列是1,2,3,.,n的一个排列i1i2.in,使得i11,i22,i33,.inn 错位排列数列为 0,1,2,9,44,265,.错位排列的递推公式是:dn=(n-1)(dn-2+dn-1)(n=3)=ndn-1+(-1)n-2,7.5 分平面的最大区域数,(1)直线分平面的最大区域数的序列为:2，4，7，11，.,递推公式是:fn=fn-1+n=n(n+1)/2+1(2)折线分平面的最大区域数的序列为:2,7,16,29,.,递推公式是:fn=(n-1)(2n-1)+2n;(3)封闭曲线(如一般位置上的圆)分平面的最大区域数的序列为:2,4,8,14,.,递推公式是:fn=fn-1+2(n-1)=n2-n+2,7.6 Catalan 数列,先看下面两个例题:例11:欧拉多边形分割问题：设有一个正凸n边形,可以用n-3条不相交的对角线将n边形分成n-2个互相没有重叠的三角形,例如n=5,共有图2_1所示的5种方法。,图2_1,欧拉多边形分割问题,对任意给定的一个n边形，任意选定一条边，则该边必是某一组成分割的三角形的一边，它的两个端点也是该三角形的两个端点，另一个端点可以来自于另外n-2个顶点，这个三角形将n边形分成二个多边形，图2_2是选定底边时的情况。图2_2,欧拉多边形分割问题,根据加法原理和乘法原理有：Hn=Hn-1+H3Hn-2+Hn-2H3+Hn-1(1)另外任取一条对角线Pij，将n边形一分为二，二部分分别为多边形，它们的边数之和为n+2，从一个顶点出发的n-3条对角线形成的n边形分割数为：H3Hn-1+H4Hn-2+Hn-2H4+Hn-1H3，从n个顶点出发的n(n-3)条对角线形成的n边形分割数为n(H3Hn-1+H4Hn-2+Hn-2H4+Hn-1H3)，由于一条对角线有两个端点，所以在上面的统计中，每条对角线出现了两遍，从所有的对角线出发形成的n边形分割数为：n(H3Hn-1+H4Hn-2+Hn-2H4+Hn-1H3)/2。,欧拉多边形分割问题,任何一个分割是由n-3条对角线组成的，每个分割在上式中被重复统计了n-3遍，所以：(n-3)Hn=n(H3Hn-1+H4Hn-2+Hn-2H4+Hn-1H3)/2(2)将(1)式写成n+1的情况有：Hn+1=Hn+H3Hn-1+Hn-1H3+Hn=(2+2(n-3)/n)Hn=(4n-6)/n)HnCatalan数的计算公式：Hn+1=C(2n-2,n-1)/n(n=1,2,3,.),例12,n个+1和n个-1构成2n项 a1,a2,.,a2n 其部分和满足a1+a2+.+ak=0(k=1,2,3,.,2n)，满足该条件的2n项不同的排列方式为 Cn=C(2n,n)/(n+1)对应的序列为 1,1,2,5,14,42,132,.序列1,1,2,5,14,42,132,.叫Catalan数列。N凸多边形的分割总数Hn=Cn-1,下列问题都是Catalan数列,(1)有2n个人排成一行进入剧场。入场费5元。其中只有n个人有一张5元钞票，另外n人只有10元钞票，剧院无其它钞票，问有多少中方法使得只要有10元的人买票，售票处就有5元的钞票找零？(2)一位大城市的律师在她住所以北n个街区和以东n个街区处工作。每天她走2n个街区去上班。如果她从不穿越（但可以碰到）从家到办公室的对角线，那么有多少条可能的道路？(3)在圆上选择2n个点,将这些点成对连接起来使得所得到的n条线段不相交的方法数?(4)n个结点可够造多少个不同的二叉树?(5)一个栈(无穷大)的进栈序列为1,2,3,.n,有多少个不同的出栈序列?,7.7 第二类Stirling数,定义：n个有区别的球放入r个相同的盒子中，要求无一空盒，其不同的方案数 s(n,r)称为第二类Stirling数。例如：红(k)、黄(y)、蓝(b)、白(w)四种颜色的球，放入两个无区别的盒子里，不允许空盒，其方案数共有如下7种：所以S(4,2)=7 下面就1n5,1rn列出各个S(n,r)的值如下,定理：第二类Stirling数满足下面的递推关系S(n,r)=rS(n-1,r)+S(n-1,r-1)(n1,r1),证明：设n个不同的球为b1,b2,bn，从中取一个球设为b1。把这n个球放入r个盒子无一空盒的方案全体可分为两类：b1独占一盒，其余n-1个球放入r-1个盒子无一空盒的方案数为S(n-1,r-1)b1不独占一盒，这相当于先将b2,b3,bn这n-1个球放入r个盒子，不允许有空盒的方案数共有S(n-1,r)，然后将b1放入其中一盒，这一盒子有r种可挑选，故b1不独占一盒的方案数为rS(n-1,r)。根据加法原理，则有S(n,r)=rS(n-1,r)+S(n-1,r-1)(n1,r1)对于 n=r，或r=1，显然有 S(n,n)=1，S(n,1)=1。思考题：n个有区别的球放入r个不同的盒子中，要求无一空盒，求不同的方案数。,8.正整数的分拆,8.1概念把正整数n表示成k个正整数之和的一种表示法n=n1+n2+nk称为 n的一个k部分拆，每个被加数ni称为此分拆的一个分部。n的k部分拆的个数记为P(n,k)；n的所有分拆的个数记为P(n)，即P(n)=P(n,k)，k=1,2,n，P(n)称为n的分拆数。在1669年GLeibnitz给JBernoulli的一封信里最先提出了确定分拆数的问题。不过首先系统研究这类计数问题的是Euler，对分拆数的研究是一类重要的计数课题，其内容十分丰富，在数学各分支中有广泛的应用。这里只是一个很初步的介绍。,8.2有序分拆 首先应该说明，以上所说的分拆不考虑各分部的次序。所以n的每个 k部分拆可以唯一确定地表示成如下规范形式：n=n1+n2+nk，其中n1n2nk1。这个分拆可简记为(n1,n2,nk)。一般地，正整数n的有序分拆用有序k元组(a1,ak)表示，其中数ai称为这个有序分拆的第i个分部(i=1,k)。例如4只有1个3部分拆(2,1,1)，但有3个有序3部分拆(2,1,1)，(1,2,1)和(1,1,2)。一般说来，有序分拆的计数比较容易处理。下面是一个典型的有关结论，它们说明有序分拆的计数常常能归结到可重复组合公式。正整数 n的一个 k部有序分拆(n1,n2,nk)就是k元不定方程 x1+x2+xk=n的一个正整数解，从而可知其总数是C(n-1,k-1)。,