资源描述：
《《组合数学基础》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、组合数学基础组合数学基础1．加法原理与乘法原理1．1加法原理：做一件事情，完成它可以有n类办法，在第一类办法中有m1种不同的方法，在第二类办法中有m2种不同的方法，……，在第n类办法中有mn种不同的方法。那么完成这件事共有N=m1+m2+...+mn种不同的方法。1．2乘法原理：做一件事情，完成它需要分成n个步骤，做第一步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有种mn不同的方法，那么完成这件事有N=m1*m2*...*mn种不同的方法。1．3两个原理的区别：一个与分类有关，一个与分步有关；加
2、法原理是“分类完成”，乘法原理是“分步完成”。2．排列、组合及计算公式2．1排列及计算公式从n个不同元素中，任取m(m≤n)个元素按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列；从n个不同元素中取出m(m≤n)个元素的所有排列的个数，叫做从n个不同元素中取出m个元素的排列数，用符号p(n,m)表示.p(n,m)=n(n-1)(n-2)……(n-m+1)=n!/(n-m)!(规定0!=1).2．2组合及计算公式从n个不同元素中，任取m(m≤n)个元素并成一组，叫做从n个不同元素中取出m个元素的一个
3、组合；从n个不同元素中取出m(m≤n)个元素的所有组合的个数，叫做从n个不同元素中取出m个元素的组合数.用符号c(n,m)表示.c(n,m)=p(n,m)/m!=n!/((n-m)!*m!)；c(n,m)=c(n,n-m);2．3n个元素中取出r个元素的循环排列数＝p(n,r)/r=n!/r(n-r)!.2．4n个元素被分成k类，每类的个数分别是n1,n2,...nk这n个元素的全排列数为n!/(n1!*n2!*...*nk!).2．5可重复组合 如果上述组合定义中每一个元素可重复选取，则称为n元集中的可重复r-组
4、合。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
5、)=C(n+r-1,r)。可重复组合也可解释为：有n类元素,每类的个数无限,从中取出r个元素的组合。3．二项式定理C(n,0)+C(n,1)+…+C(n,n-1)+C(n,n)=2^n证明：等式左边包含了n元集的从零个元素到n个元素的全部组合，每一种组合与一个n位二进制数一一对应，对应方式为：n位二进制数共有n位，每一位对应n元集的一个元素，如果n位二进制数某一位上为1，则表示选中该位对应的元素，否则表示未选中该位对应的元素，这样一个n位二进制数就对应一种组合；反过来每一种组合同样对应一个n位二进制数，而n位二进制
6、数的总数为2^n。4.杨辉三角11112113311464115101051161520156117213535217118285670562881193684126126843691……杨辉三角的每一行中的第一个数和最后一个数均为1,其余位置上的数可利用其上一行中的数递推计算出来,其值为上一行中位于同一列和前一列的两个数之和。5.鸽巢原理5.1简单形式如果n+1个物体被放进n个盒子，那么至少有一个盒子包含两个或更多的物体。例2：在13个人中必存在两个人，他们的生日在同一月份里。例3：设有n对已婚夫妇。为保证有一对
7、夫妇被选出，至少要从这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条性质可
8、能具有其中的一种、二种、……、n种，也可能任何性质都没有。设Ai(i=1,2,……,m)表示S中具有Pi的元素构成的子集。这时容斥原理可叙述为：定理：S中不具有性质P1，P2，……，Pm的元素数是：如:m=3,时上式为：=
9、S
10、-(
11、A1
12、+
13、A2
14、+
15、A3
16、)+(
17、A1∩A2
18、+
19、A1∩A3
20、+
21、A2∩A3
22、)－
23、A1∩A2∩A3
24、推论:至少具有性质P1,
