组合数学课件教学提纲.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,组合数学课件,课程简介,相关课程,使用教材,数学分析,高等代数,离散数学,书名：组合数学（第三版）,作者：孙淑玲,出版社：中国科学技术大学出版社,本课程针对计算机科学中的一个重要学科,组合数学，组合数学是数学的一个分支，它研究事物在结定模式下的配置，研究这种配置的存在性，所有可能配置的计数和分类以及配置的各种性质。组合数学在计算机科学中有着极其广泛的应用。,组合学问题求解方法层出不穷、干变万化，应以理解为基础，善于总结各种技巧，掌握科学的组织和推理方法。,目录（1）,引言,第,1,章 排列与组合,1.1,加法法则和乘法法则,1.2,排列,1.3,组合,1.4,二项式定理,1.5,组合恒等式及其含义,1.6,模型转换,本章小结,习题,第,2,章 鸽笼原理,2.1,鸽笼原理,2.2,鸽笼原理的推广,2.3 Ramsey,定理,本章小结,习题,第,3,章 容斥原理,3.1,容斥原理,3.2,重集,r,-,组合,3.3,错排问题,3.4,有限制排列,3.5*,一般有限制排列,3.6*,广义容斥原理,本章小结,习题,第,4,章 母函数,4.1,母函数的基本概念,4.2,母函数的基本运算,4.3,在排列组合中的应用,4.4,整数的拆分,4.5 Ferrers,图,目 录,目录（2）,4.6*,在组合恒等式中的应用,本章小结,习题,第,5,章 递推关系,5.1,递推关系的建立,5.2,常系数线性齐次递推关系,5.3,常系数线性非齐次递推关系,5.4,迭代法与归纳法,5.5,母函数在递推关系中的应用,5.6*,典型的递推关系,本章小结,习题,第,6,章,P,lya,定理,6.1,群的概念,6.2,置换群,6.3,循环、奇循环与偶循环,6.4 Burnside,引理,6.5 P,lya,定理,6.6 P,lya,定理的应用,6.7,母函数形式的,P,lya,定理,6.8*,图的计数,6.9*P,lya,定理的若干推广,本章小结,习题,*,课程总结,注：加*的章节一般性了解,引 言,发展历史,涵盖内容,学习目的,学习方法,存在性问题,计数和枚举,优化,问题,构造性问题,科学的组织,科学的推理,古老,年轻,练习,思考总结,笔记,组合数学研究的中心问题是按照一定的规则来安排有限多个对象,如果人们想把有限多个对象按照它们所应满足的条件来进行安排，当符合要求的安排并非显然存在或显然不存在时，首要的问题就是要证明或者否定它的存在。这就是,存在性,问题。如果所要求的安排存在，则可能有多种不同的安排，这又经常给人们提出这样的问题：有多少种可能的安排方案？如何对安排的方案进行分类？这就是,计数问题,。如果一个组合问题有解，则往往需要给出求其某一特定解的算法，这就是所谓的,构造性,问题。如果算法很多，就需要在一定的条件下找出一个或者几个最优或近乎最优的安排方案，这就是,优化,问题。,第1章 排列与组合,本章重点介绍以下的基本计数方法：,加法法则和乘法法则,排列,组合,二项式定理的应用,组合恒等式,相互独立,的事件,A,、,B,分别有,k,和,l,种方法产生，则产生,A,或,B,的方法数为,k,+,l,种。,1.1 加法法则,1.1,加法法则和乘法法则,1.1.1,加法法则,加法法则,集合论定义,若,|,A,|=,k,，,|,B,|=,l,，且,A,B,=,，则,|,A,B,|=,k,+,l,。,设,S,是有限集合，若 ，且,时，则有 。,1.1 加法法则例1,1.1,加法法则和乘法法则,1.1.1,加法法则,例 题,例,1,、,有一所学校给一名物理竞赛优胜者发奖，奖品有三类，第一类是三种不同版本的法汉词典；第二类是四种不同类型的物理参考书；第三类是二种不同的奖杯。这位优胜者只能挑选一样奖品。那么，这位优胜者挑选奖品的方法有多少种？,解：,设,S,是所有这些奖品的集合，,S,i,是第,i,类奖品的集合,(,i,=1,2,3),，显然，,S,i,S,j,=,(,i,j,),，根据加法,法则,有,1.1 加法法则例2、3,1.1,加法法则和乘法法则,1.1.1,加法法则,例 题,例,2,、,大于,0,小于,10,的奇偶数有多少个？,例,3,、,小于,20,可被,2,或,3,整除的自然数有多少个？,解：,设,S,是符合条件数的集合，,S,1,、,S,2,分别是符合条件的奇数、偶数集合，显然，,S,1,S,2,=,，根据加法,法则,有,若,|,A,|=,k,，,|,B,|=,l,，,A,B,=(,a,b,)|,a,A,，,b,B,，则,|,A,B,|=,k,l,。,1.1 乘法法则,1.1,加法法则和乘法法则,1.1.2,乘法法则,乘法法则,相互独立,的事件,A,、,B,分别有,k,和,l,种方法产生，则选取,A,以后再选取,B,的方法数为,k,l,种。,集合论定义,设,是有限集合，且,，则有,。,1.1 乘法法则,例4,1.1,加法法则和乘法法则,1.1.2,乘法法则,例 题,例,4,、,从,A,地到,B,地有二条不同的道路，从,B,地到,C,地有四条不同的道路，而从,C,地到,D,地有三条不同的道路。求从,A,地经,B,、,C,两地到达,D,地的道路数。,解：,设,S,是所求的道路数集合，,S,1,、,S,2,、,S,3,分别是从,A,到,B,、从,B,到,C,、从,C,到,D,的道路集合，根据乘法,法则,有,1.1 乘法法则,例5,1.1,加法法则和乘法法则,1.1.2,乘法法则,例 题,例,5,、,由数字,1,2,3,4,5,可以构成多少个所有数字互不相同的四位偶数？,解：,所求的是四位偶数，故个位只能选,2,或,4,，有两种选择方法；又由于要求四位数字互不相同，故个位选中后，十位只有四种选择方法；同理，百位、千位分别有三种、两种选择方法，根据乘法,法则，四位数互不相同的偶数个数为,2,4,3,2=48,1.1 乘法法则,例6,1.1,加法法则和乘法法则,1.1.2,乘法法则,例 题,例,6,、,求出从,8,个计算机系的学生、,9,个数学系的学生和,10,个经济系的学生中选出两个不同专业的学生的方法数。,解：,由乘法,法则,有,选一个计算机系和一个数学系的方法数为,8,9=72,选一个数学系和一个经济系的方法数为,9,10,=90,选一个经济系和一个计算机系的方法数为,10,8=80,由加法,法则,，符合要求的方法数为,72+90+80=242,1.1 重集的概念,1.1,加法法则和乘法法则,1.1.3,计数问题的分类,有序安排或有序选择,允许重复,/,不允许重复,无序安排或无序选择,允许重复,/,不允许重复,标准集的特性：确定、无序、相异等。,重集：,B,=,k,1,*b,1,k,2,*b,2,k,n,*b,n,，其中：,b,i,为,n,个互不相同的元素，称,k,i,为,b,i,的,重数,，,i,=1,2,n,，,n,=1,2,，,k,i,=1,2,。,重集的概念,1.2 线排列,1.2,排列,定义,1.1,1.2.1,线排列,集合论定义,定理,1.1,从,n,个不同元素中，取,r,个,(0,r,n,),按一定顺序排列起来，其排列数,P,(,n,r,),。,设,A,=,a,n,，从,A,中选择,r,个,(0,r,n,),元素排列起来，,A,的,r,有序子集，,A,的,r,排列。,如,n,r,Z,且,n,r,0,P,(,n,r,)=,n,!/(,n-r,)!,。,如,n,=,r,，称全排列,P,(,n,n,)=,n,!,；,如,n,r,P,(,n,r,)=0,；如,r,=0,P,(,n,r,)=1,。,证明：,构造集合,A,的,r,排列时，可以从,A,的,n,各元素中任选一个作为排列的第一项，有,n,种选法；第一项选定后从剩下的,n,-1,个元素中选排列的第二项有,n,-1,种选法；,由此类推，第,r,项有,n,-,r,+1,种选法。根据乘法,法则,有,1.2 线排列推论1,1.2,排列,1.2.1,线排列,两个推论,推论,1.1.1,：,如,n,r,N,且,n,r,2,，则,P,(,n,r,)=,n,P,(,n-,1,r-,1),。,证明：,在集合,A,的,n,个元素中，任一个元素都可以排在它的,r,排列首位，故首位有,n,种取法；首位取定后，其他位置的元素正好是从,A,的另,n,-1,个元素中取,r,-1,个的排列，因此有,P,(,n,-1,r,-1),种取法。由乘法法则有,P,(,n,r,)=,n,P,(,n-,1,r-,1),证毕。,1.2 线排列推论2,1.2,排列,1.2.1,线排列,两个推论,推论,1.1.1,：,如,n,r,N,且,n,r,2,，则,P,(,n,r,)=,n,P,(,n-,1,r-,1),。,推论,1.1.2,：,如,n,r,N,且,n,r,2,，则,P,(,n,r,)=,r,P,(,n-,1,r-,1)+,P,(,n-,1,r,),。,证明：,当,r,2,时，把集合,A,的,r,排列分为两大类：一类包含,A,中的某个固定元素，不妨设为,a,1,，另一类不包含,a,1,。第一类排列相当于先从,A,-,a,1,中取,r,-1,个元素进行排列，有,P,(,n,-1,r,-1),种取法，再将,a,1,放入每一个上述排列中，对任一排列，,a,1,都有,r,种放法。由乘法法则，第一类排列共有,r,P,(,n-,1,r-,1),个。第二类排列实质上是,A,-,a,1,的,r,排列，共有,P,(,n-,1,r,),个。再由加法法则有,P,(,n,r,)=,r,P,(,n-,1,r-,1)+,P,(,n-,1,r,),证毕。,1.2 线排列例1,1.2,排列,1.2.1,线排列,例 题,例,1,、,由数字,1,2,3,4,5,可以构成多少个所有数字互不相同的四位数？,解：,由于所有的四位数字互不相同，故每一个四位数就是集合,1,2,3,4,5,的一个,4,排列，因而所求的四位数个数为,1.2 线排列例2,1.2,排列,1.2.1,线排列,例 题,例,2,、,将具有,9,个字母的单词,FRAGMENTS,进行排列，要求字母,A,总是紧跟在字母,R,的右边，问有多少种这样的排法？如果再要求字母,M,和,N,必须相邻呢？,解：,由于,A,总是,R,的右边，故这样的排列,相当于,是,8,个元素的集合,F,RA,G,M,E,N,T,S,的一个全排列，个数为,如果再要求,M,和,N,必须相邻，可先把,M,和,N,看成一个整体,=M,N,，进行,7,个元素的集合,F,RA,G,E,T,S,的全排列，在每一个排列中再进行,M,N,的全排列，由乘法法则，排列个数为,1.2 线排列例3,1.2,排列,1.2.1,线排列,例 题,例,3,、,有多少个,5,位数，每位数字都不相同，不能取,0,，且数字,7,和,9,不能相邻？,解：,由于所有的,5,位数字互不相同，且不能取,0,，故每一个,5,位数就是集合,1,2,9,的一个,5-,排列，其排列数为,P,(9,5),，其中,7,和,9,相邻的排列数为,c(7,3)4!24,2,P,(7,3),，满足题目要求的,5,位数个数为,1.2 圆排列,1.2,排列,定义,1.2,1.2.2,圆排列,定理,1.2,设,A,=,a,n,，从,A,中取,r,个,(0,r,n,),元素按某种顺序（如逆时针）排成一个圆圈，称为圆排列（循环排列）。,设,A,=,a,n,，,A,的,r,圆排列个数为,P,(,n,r,),/,r,。,证明：,由于把一个圆排列旋转所得到另一个圆排列视为相同的圆排列，因此线排列,a,1,a,2,a,r,，,a,2,a,3,a,r,a,1,，,a,r,a,1,a,2,a,r,-1,在圆排列中是一个，即一个圆排列可产生,r,个不同的线排列；同理，,r,个不同的线排列对应一个圆排列。而总共有,P,(,n,r,),个线排列，故圆排列的个数为,P,(,n,r,)/,r,=,n,!/(,r,(,n-r,)!,),证毕。,1.2 圆排列,例4,1.2,排列,例 题,1.2.2,圆排列,例,4,、,有,8,人围圆桌就餐，问有多少种就座方式？如果有两人不愿坐在一起，又有多少种就座方式？,解：,由上述定理知,8,人围圆桌就餐，有,8!/8=7!=5040,种就座方式。,又有两人不愿坐在一起，不妨设此二人为,A,、,B,，当,A,、,B,坐在一起时，相当于,7,人围圆桌就餐，有,7!/7=6!,种就座方式。而,A,、,B,坐在一起时，又有两种情况，或者,A,在,B,的左面，或者,A,在,B,的右面，因此,A,、,B,坐在一起时，共有,2,6!,种就座方式，因此如果有两人不愿坐在一起，就座方式为,7!-2,6!=,5,6!=3600,1.2 圆排列,例5,1.2,排列,例 题,1.2.2,圆排列,例,5,、,4,男,4,女围圆桌交替就座有多少种就座方式？,解：,显然，这是一个圆排列问题。首先让,4,个男的围圆桌就座，有,4!/4=3!,种就座方式。因为要求男女围圆桌交替就座，在男的坐定后，两两之间均需留有一个空位，女的就座相当于一个,4,元素集合的全排列，就座方式数为,4!,。由乘法法则知，就座方式数为,3!,4!=144,1.2 重排列,1.2,排列,定义,1.3,1.2.3,重排列,集合论定义,定理,1.3,从,n,个不同元素中，可重复选取,r,个按一定顺序排列起来，称为重排列。,从重集,B,=,k,1,*b,1,k,2,*b,2,k,n,*b,n,中选取,r,个按一定顺序排列起来。,重集,B,=,*,b,1,*,b,2,*,b,n,的,r,排列的个数为,n,r,。,证明：,构造,B,的,r,排列如下：选择第一项时可从,n,个元素中任选一个，有,n,种选法，选择第二项时由于可以重复选取，仍有,n,种选法，,，同理，选择第,r,项时仍有,n,种选法，根据乘法法则，可得出,r,排列的个数为,n,r,。,证毕。,1.2 重排列,例6,1.2,排列,例 题,1.2.3,重排列,例,6,、,由数字,1,2,3,4,5,6,这六个数字能组成多少个五位数？又可组成多少大于,34500,的五位数？,解：,一个五位数的各位数字可重复出现，是一个典型的重排列问题，相当于重集,B,=,*1,*2,*6,的,5,排列，所求的五位数个数为,6,5,=7776,。,大于,34500,的五位数可由下面三种情况组成：,万位选,4,5,6,中的一个，其余,4,位相当于重集,B,的,4,排列，由乘法法则知，共有,3,6,4,个五位数；,万位是,3,，千位,5,6,中的一个，其余,3,位相当于重集,B,的,3,排列，由乘法法则知，共有,2,6,3,个五位数；,万位是,3,，千位,4,中的一个，百位选,5,6,中的一个，其余,2,位相当于重集,B,的,2,排列，由乘法法则知，共有,2,6,2,个五位数；,由加法法则知，大于,34500,的五位数个数为,3,6,4,+,2,6,3,+,2,6,2,=4392,1.2,重,排列计数,1.2,排列,1.2.3,重排列,定理,1.4,重集,B,=,n,1,*b,1,n,2,*b,2,n,k,*b,k,的全排列,个数为,证明：,将,B,中的,n,i,个,b,i,看作不同的,n,i,个元素，赋予上标,1,2,n,i,，即 ，如此，重集,B,就变成具有,n,1,+,n,2,+,n,k,=,n,个不同的元素集合,显然，集合,A,的全排列个数为,n,!,。,又由于,n,i,个,b,i,赋予上标的方法有,n,i,!,种，于是对重集,B,的任一个全排列，都可以产生集合,A,的,n,1,!,n,2,!,n,k,!,个排列（由乘法法则），故重集,B,的全排列个数为,证毕。,注：利用组合数的计数方法同样可以得出证明。,1.2,重,排列,例7,1.2,排列,1.2.3,重排列,例 题,例,6,、,有四面红旗，三面蓝旗，二面黄旗，五面绿旗可以组成多少种由,14,面旗子组成的一排彩旗？,解：,这是一个重排列问题，是求重集,4*,红旗,3*,蓝旗,2*,黄旗,5*,绿旗,的全排列个数，根据定理，一排彩旗的种数为,1.2,重,排列,例8,1.2,排列,1.2.3,重排列,例 题,例,8,、,用字母,A,、,B,、,C,组成五个字母的符号，要求在每个符号里，,A,至多出现,2,次，,B,至多出现,1,次，,C,至多出现,3,次，求此类符号的个数。,解：,这也是一个重排列问题。根据分析，符合题意的符号个数相当于求重集,M,=2*A,1*B,3*C,的,5,排列个数，可分为三种情况：需要分别求,M,-A,、,M,-B,和,M,-C,的全排列个数。根据加法法则，此类符号个数为,1.2 项链排列,1.2,排列,定义,1.4,1.2.4,项链排列,对圆排列，通过转动、平移、翻转、可重合的，即可看作项链排列。,如,n,个不同元素的,r,项链排列个数为,P,(,n,r,)/(2,r,),，具体参照,P,lya,定理,。,1.3 无重组合,1.3,组合,定义,1.5,1.3.1,（无重）组合,集合论定义,定理,1.5,设,A,=,a,n,，从,A,中选择,r,个,(0,r,n,),元素组合起来，,A,的,r,无序子集，,A,的,r,组合。,如,r,n,，有,C,(,n,r,)=,P,(,n,r,)/,r,!=,n,!/(,r,!(,n-r,)!),。,如,n,r,=0,，,C,(,n,r,)=1,；,如,n,r,，,C,(,n,r,)=0,。,从,n,个不同元素中，取,r,个,(0,r,n,),不考,虑顺序组合起来，其组合数,C,(,n,r,),或 。,证明：,从,n,个不同元素中取,r,个元素的组合数为,C,(,n,r,),，而,r,个元素可组成,r,!,个,r,排列，即一个,r,组合对应,r,!,个,r,排列。于是,C,(,n,r,),个,r,组合对应,r,!,C,(,n,r,),个,r,排列，这是从,n,个不同元素中取,r,个元素的,r,排列数,P,(,n,r,),，因此有,1.3,无重,组合推论1,1.3,组合,1.3.1,（无重）组合,三个推论,推论,1.5.1,：,C,(,n,r,)=,C,(,n,n-r,),证明：,实际上，从,n,个不同元素中选出,r,个元素的同时，就有,n-r,个元素没有被选出，因此选出,r,个元素的方式数等于选出,n-r,个元素的方式数，即,C,(,n,r,)=,C,(,n,n-r,),。得证。,另外，也可通过计算得出证明如下,1.3,无重,组合推论2,1.3,组合,1.3.1,（无重）组合,三个推论,推论,1.5.1,：,C,(,n,r,)=,C,(,n,n-r,),推论,1.5.2(,Pascal,公式,),：,C,(,n,r,),=,C,(,n-,1,r,)+,C,(,n-,1,r-,1),证明：,利用组合分析法。在集合,A,的,n,个不同元素中固定一个元素，不妨设为,a,1,，从,n,个元素中选出,r,个元素的组合由下面两种情况组成：,r,个元素中包含,a,1,。相当于从除去,a,1,的,n-,1,个元素中选出,r-,1,个元素的组合，再加上,a,1,而得到，组合数为,C,(,n-,1,r-,1),；,r,个元素中不包含,a,1,。相当于从除去,a,1,的,n-,1,个元素中选出,r,个元素的组合而得到，组合数为,C,(,n-,1,r,),。,由加法法则即得,C,(,n,r,)=,C,(,n-,1,r,)+,C,(,n-,1,r-,1),另外，也可通过计算得出证明如下,1.3,无重,组合推论3,1.3,组合,1.3.1,（无重）组合,三个推论,推论,1.5.1,：,C,(,n,r,)=,C,(,n,n-r,),推论,1.5.2(,Pascal,公式,),：,C,(,n,r,)=,C,(,n-,1,r,)+,C,(,n-,1,r-,1),推论,1.5.3,：,C,(,n,r,)=,C,(,n-,1,r-,1)+,C,(,n-,2,r-,1)+,C,(,r-,1,r-,1),证明：,反复利用,Pascal,公式，即可证明。,或利用组合分析法，在集合,A,=,a,n,的,n,个不同元素选出,r,个元素的组合可分为以下多种情况：如,r,个元素中包含,a,1,，相当于从除去,a,1,的,n-,1,个元素中选出,r-,1,个元素的组合，再加上,a,1,而得到，组合数为,C,(,n-,1,r-,1),；如,r,个元素中不包含,a,1,但包含,a,2,，相当于从除去,a,1,a,2,的,n-,2,个元素中选出,r-,1,个元素的组合，再加上,a,2,而得到，组合数为,C,(,n-,2,r-,1),同理如,r,个元素中不包含,a,1,a,2,a,n,-,r,，但包含,a,n,-,r,+1,，相当于从剩下的,r-,1,个元素中选出,r-,1,个元素的组合，再加上,a,n,-,r,+1,而得到，组合数为,C,(,r-,1,r-,1),。由加法法则得,C,(,n,r,)=,C,(,n-,1,r-,1)+,C,(,n-,2,r-,1)+,C,(,r-,1,r-,1),1.3,无重,组合,例1,1.3,组合,1.3.1,（无重）组合,例 题,例,1,、,有,5,本日文书，,7,本英文书，,10,本中文书，从中取两本不同文字的书，问有多少种方案？若取两本相同文字的书，问有多少种方案？任取两本书，有多少种方案？,解：,从三种文字的书中取两种共有,C,(3,2)=3,种取法。根据乘法法则有：日英各一本的方法数为,5,7=35,，中英各一本的方法数为,10,7=70,，中日各一本的方法数为,10,5,=50,，由加法法则得,35+70+50=155,取两本相同文字的，有两本中文、两本英文或两本日文三种方式，由加法法则得,C,(5,2)+,C,(7,2)+,C,(10,2)=76,任取两本书，相当于从,5+7+10=22,本书中取两本的组合，即,C,(22,2)=231,1.3,无重,组合,例2,1.3,组合,1.3.1,（无重）组合,例 题,例,2,、,从,1300,之间任取,3,个不同的数，使得这,3,个数的和正好被,3,除尽，问共有几种方案？,解：,所有的整数可分为以下,3,个分类：模,3,余,0,、模,3,余,1,和模,3,余,2,，故,1300,的,300,个数可以分为,3,个集合：,A,=1,4,298,，,B,=2,5,299,，,C,=3,6,300,。任取,3,个数其和正好被,3,整除的情况如下：,三个数同属于集合,A,，有,C,(100,3),种方案；,三个数同属于集合,B,，有,C,(100,3),种方案；,三个数同属于集合,C,，有,C,(100,3),种方案；,三个数分别属于集合,A,B,C,，由乘法法则有,100,3,种方案。,由加法法则得，所求的方案数为,3,C,(100,3)+100,3,=1485100,1.3,无重,组合,例3,1.3,组合,1.3.1,（无重）组合,例 题,例,3,、,某车站有,1,到,6,个入口处，每个入口处每次只能进一个人，问一小组,9,个人进站的方案数有多少？,解,I,：,按照从入口,1,到入口,6,的顺序可得到,9,个人一个排列，再把两个入口间设上一个标志，加上这,5,个标志相当于每一个排列有,14,个元素，其中,5,个标志没有区别，但其位置将区分各入口的进站人数，相当于,14,个元素集合的,5,组合，故进站方案数为,9!,C,(14,5)=726485760,解,II,：,同上分析，问题转化为重集,1*,p,1,1*,p,2,1*,p,9,5*,标志,的全排列（,p,i,代表,9,个人，,i,=1,9,），故进站方案数为,14!/5!=726485760,解,III,：,考虑,9,个人选择方案，第,1,个人有,6,种选择，第,2,个人除了选择入口，还要考虑在第,1,个人的前面或后面，故有,7,种选择,同理，第,9,个人有,14,种选择，根据乘法法则，故进站方案数为,6,7,14,=726485760,1.3,无重,组合,例4,1.3,组合,1.3.1,（无重）组合,例 题,例,4,、,求,5,位数中至少出现一个,6,，而被,3,整除的数的个数。,解：,10,进制数被,3,整除的充要条件是各位数的和能被,3,整除。据此可进行如下讨论：,从左往右计，如最后一个,6,出现在个位，则十百千位各有,10,种选择，万位有,3,种可能，根据乘法法则，总个数为,3,10,3,；,如最后一个,6,出现在十位，则个位有,9,种选择，百千位各有,10,种选择，万位有,3,种可能，根据乘法法则，总个数为,3,10,2,9,；,如最后一个,6,出现在百位，则个十位各有,9,种选择，千位有,10,种选择，万位有,3,种可能，根据乘法法则，总个数为,3,10,9,2,；,如最后一个,6,出现在千位，则个十百位各有,9,种选择，万位有,3,种可能，根据乘法法则，总个数为,3,9,3,；,如最后一个,6,出现在万位，则个十百位各有,9,种选择，千位有,3,种可能，根据乘法法则，总个数为,3,9,3,；,根据加法法则，,符合条件的整数个数为,3,10,3,+,3,10,2,9+3,10,9,2,+3,9,3,+3,9,3,=12504,1.3,无重,组合,例5,1.3,组合,1.3.1,（无重）组合,例 题,例,5,、,求,1000!,的末尾有几个零。,解：,此问题在于求将,1000!,分解为素数的乘积时，,2,和,5,的幂是多少。末尾零的个数应该等于,2,和,5,的幂中较小的那个数。,11000,中,5,的倍数的数共,200,个，其中有,40,个,5,2,的倍数，这,40,个数中有,8,个,5,3,的倍数，而这,8,个数中又有,1,个,5,4,的倍数，故,1000!,分解为素数的乘积时，,5,的幂应该是,200+40+8+1=249,显然，,2,的幂必然大于,249,，因此,1000!,的末尾有,249,个零。,1.3,无重,组合,例6,1.3,组合,1.3.1,（无重）组合,例 题,例,6,、,求能除尽,1400,的正整数数目（,1,除外），其中包含多少个奇数？,解：,1400=2,3,5,2,7,，故除尽,1400,的正整数分解为素数的乘积的形式应该为,2,l,5,m,7,n,，其中,0,l,3,0,m,2,0,n,1,，但应排除,l,=,m,=,n,=0,的情况。故满足条件的数目为,(3+1),(2+1),(1+1)-1=23,其中包含的奇数为,(1),(2+1),(1+1)-1=5,1.3 重复组合,1.3,组合,定义,1.6,1.3.2,重复组合,集合论定义,定理,1.6,从,n,个不同元素中，可重复选取,r,个不考虑顺序组合起来，其组合数,F,(,n,r,),。,从重集,B,=,k,1,*b,1,k,2,*b,2,k,n,*b,n,中取,r,个元素不考虑顺序的组合。,重集,B,=,*,b,1,*,b,2,*,b,n,的,r,组合数,F,(,n,r,)=,C,(,n,+,r,-1,r,),证明：,设,n,个元素,b,1,b,2,b,n,和自然数,1,2,n,一一对应。于是任何组合皆可看作是一个,r,个数的组合,c,1,c,2,c,r,。由于是组合，不妨认为各,c,i,是按照大小顺序排列的，相同的,c,i,连续排在一起，不妨设,c,1,c,2,c,r,。,又令,d,i,=,c,i,+,i,-1(,i,=1,2,r,),，即,d,1,=,c,1,d,2,=,c,2,+1,d,r,=,c,r,+,r,-1,。,因,1,c,i,n,，故,1,d,i,n,+,r,-1,，得到一个集合,1,2,n,+,r,-1,的,r,组合,d,1,d,2,d,r,(,d,1,d,2,d,r,),。,显然有一种,c,1,c,2,c,r,的取法，就有一种,d,1,d,2,d,r,的取法，反之亦然，这两种取法是,一一对应的,，从而这两种取法是,等价的,。如此，从,n,个不同元素中可重复选取,r,个的组合数，和从,n,+,r,-1,个不同元素中不重复选取,r,个的组合数是相同的，故,F,(,n,r,)=,C,(,n,+,r,-1,r,),1.3,重复,组合,例7,1.3,组合,定理,1.7,1.3.2,重复组合,例 题,r,个无区别的球放入,n,个有标志的盒子里，每盒的球数可多于,1,个，则共有,F,(,n,r,),种方案。,例,7,、,试问,(,x,+,y,+,z,),4,的展开式有多少项？,证明：,这是一个允许重复组合的典型问题，实质上定理,1.6,的另一种说法。由于每盒的球数不受限制，相当于重集,*,a,1,*,a,2,*,a,n,的,r,组合。,解：,(,x,+,y,+,z,),4,展开式每一项都是,4,次方的，相当于从,3,个不同元素中可以重复的选择,4,个，或者相当于将,4,个无区别的球放到,3,个有标志的盒子里。故展开项个数为,F,(3,4)=,C,(3+4-1,4)=15,1.3,重复,组合,例8、9,1.3,组合,例 题,1.3.2,重复组合,例,8,、,某餐厅有,7,种不同的菜，为了招待朋友，一个顾客需要买,14,个菜，问有多少种买法？,例,9,、,求,n,个无区别的球放入,r,个有标志的盒子里,(,n,r,),而无一空盒的方案数。,解：,这个问题相当于重集,*1,*2,*7,的,14,组合。根据定理,1.6,知买菜的方法数为,F,(7,14)=,C,(7+14-1,14)=4845,解：,由于每个盒子不能为空，故每个盒子里可先放一个球，这样还剩,n,-,r,个球，再将这,n,-,r,个球防到,r,个盒子里，由于这时每盒的球数不受限制，相当于重集,*,a,1,*,a,2,*,a,r,的,n,-,r,组合。根据定理,1.6,知，其组合数为,F,(,r,n,-,r,)=,C,(,r,+,n,-,r,-1,n,-,r,)=,C,(,n,-1,r,-1),1.3,重复,组合,例10,1.3,组合,例 题,1.3.2,重复组合,例,10,、,在由数,0,1,9,组成的,r,位整数所组成的集合中，如果将一个整数重新排列得到另一个整数，则称这两个整数是,等价,的。那么，,有多少不等价的整数？,如果,0,和,9,最多只能出现一次，又有多少不等价的整数？,解：,分析题意知，一个,r,位整数只和所取的数字有关，与其顺序无关，因而是个组合问题。又每一整数的每一位可从,0,1,9,中任取，故不等价的,r,位整数相当于重集,*0,*1,*9,的,r,组合。根据定理,1.6,知，其组合数为,F,(10,r,)=,C,(10+,r,-1,r,)=,C,(9+,r,r,),0,和,9,最多只出现一次，可分为三种情况：均不出现时相当于重集,B,=,*1,*2,*8,的,r,组合，组合数为,F,(8,r,)=,C,(,r,+7,r,),；只出现其一，若,0,出现，相当于,B,的,r,-1,组合，然后加入,0,，组合数为,F,(8,r,-1)=,C,(,r,+6,r,-1),，同理,9,出现的组合数为,C,(,r,+6,r,-1),；均出现一次，相当于,B,的,r,-2,组合，然后加入,0,9,，组合数为,F,(8,r,-2)=,C,(,r,+5,r,-2),，由加法法则知，符合题意的整数个数为,C,(,r,+7,r,)+2,C,(,r,+6,r,-1)+,C,(,r,+5,r,-2),1.3,重复,组合,例11,1.3,组合,例 题,1.3.2,重复组合,例,11,、,求方程,x,1,+,x,2,+,x,n,=,r,的非负整数解的个数，其中,n,r,为正整数。,解：,设,重集,B,=,*,b,1,*,b,2,*,b,n,，,B,的任一个,r,组合都具有形式,x,1,*,b,1,x,2,*,b,2,x,n,*,b,n,，其中,x,i,(,i,=1,2,n,),是非负整数且满足方程,x,1,+,x,2,+,x,n,=,r,。,反之，每一个满足方程,x,1,+,x,2,+,x,n,=,r,的非负整数解,x,1,x,2,x,n,都对应重集,B,的一个,r,组合。因此，方程,x,1,+,x,2,+,x,n,=,r,的非负整数解的个数就等于重集,B,的,r,组合数,F,(,n,r,),。,1.3 不相邻组合,1.3,组合（,3,）,1.3,组合,定义,1.7,1.3.3,不相邻组合,定理,1.8,从序列,A,=1,2,n,个中选取,r,个，其中不存在,i,i,+1,两个相邻的数同时出现于一个组合的组合。,从序列,A,=1,2,n,个中选取,r,个作不相邻的组合，其组合数为,C,(,n,-,r,+1,r,),证明：,设,d,1,d,2,d,r,是所求的一个不相邻组合，不妨设,d,1,d,2,d,r,。令,c,i,=,d,i,-,i,+1(,i,=1,2,r,),，即,c,1,=,d,1,c,2,=,d,2,-1,c,r,=,d,r,-,r,+1,。因,1,d,i,n,，故,1,c,i,n,-,r,+1,，得到一个集合,1,2,n,-,r,+1,的,r,组合。显然有一种,d,1,d,2,d,r,的取法，就有一种,c,1,c,2,c,r,的取法。,反之亦然，集合,1,2,n,-,r,+1,的一个,r,组合,c,1,c,2,c,r,，不妨设,c,1,c,2,c,r,。令,d,i,=,c,i,+,i,-1(,i,=1,2,r,),，即,d,1,=,c,1,d,2,=,c,2,+1,d,r,=,c,r,+,r,-1,。因,1,c,i,n,-,r,+1,，故,1,d,i,n,，得到一个集合,1,2,n,的不相邻组合,d,1,d,2,d,r,。显然有一种,c,1,c,2,c,r,的取法，就有一种,d,1,d,2,d,r,的取法。,故这两种取法是,一一对应的,，从而这两种取法是,等价的,。从,n,个不同元素中可选取,r,个的不相邻组合数，和从,n,-,r,+1,个不同元素中选取,r,个的组合数是相同的，即,C,(,n,-,r,+1,r,),。,1.4 二项式定理,1.4,二项式定理,定理,1.9,证明：,因为,(,x,+,y,),n,=(,x,+,y,)(,x,+,y,)(,x,+,y,),，等式右端有,n,个因子，项,x,k,y,n,-,k,是从这,n,个因子中选取,k,个因子，,k,=0,1,n,。在这,k,个,(,x,+,y,),里都取,x,，而从剩下的,n,-,k,个因子,(,x,+,y,),中选取,y,作乘积得到，因此,x,k,y,n,-,k,的系数为上述选法的个数,C,(,n,r,),。故有,证毕。,注：可用数学归纳法证明，证明略；,C,(,n,k,),又称,二项式系数,。,1.4 二项式定理推论1,1.4,二项式定理,四个推论,推论,1.9.1,：,推论,1.9.2,：,推论,1.9.3,：,证明：,在推论,1.9.2,中令,x,=1,，即可得证。,利用组合分析，等式左端相当于从,A,=,a,n,中任意选择,k,(0,k,n,),个元素的所有可能数目，即对,n,个元素，每一个都有被选择和不被选择的可能，总的可能数为,2,n,。,另外，该等式还表明,A,的所有子集个数为,2,n,。,1.4 二项式定理推论2,1.4,二项式定理,四个推论,推论,1.9.1,：,推论,1.9.2,：,推论,1.9.3,：,推论,1.9.4,：,证明：,在推论,1.9.2,中令,x,=-1,，即可得证。,另外，该等式还表明,A,=,a,n,的偶数子集个数和奇数子集个数相等。,1.4 广义二项式定理,1.4,二项式定理,定理,1.10,定义,1.8,广义,二项式系数 为：,牛顿二项式定理：,1.4,广义,二项式定理,推论1,1.4,二项式定理,六个推论,推论,1.10.1,：,推论,1.10.2,：,证明：,1.4,广义,二项式定理,推论2,1.4,二项式定理,六个推论,推论,1.10.1,：,推论,1.10.2,：,推论,1.10.3,：,推论,1.10.4,：,推论,1.10.5,：,证明：,当,=1/2,时，,C,(,0)=1,