第1章 排列与组合精.ppt

第1章 排列与组合第1页，本讲稿共103页课程简介课程简介相关课程相关课程使用教材使用教材数学分析高等代数数学分析高等代数书名：组合数学书名：组合数学作者：曹汝成作者：曹汝成 出版社：华南理工大学出版社出版社：华南理工大学出版社 本本课课程程针针对对计计算算机机科科学学中中的的一一个个重重要要学学科科组组合合数数学学，组组合合数数学学是是数数学学的的一一个个分分支支，它它研研究究事事物物在在结结定定模模式式下下的的配配置置，研研究究这这种种配配置置的的存存在在性性，所所有有可可能能配配置置的的计计数数和和分分类类以以及及配配置置的的各各种种性性质质。组组合合数数学学与与现实生活密切相关并在计算机科学中有着极其广泛的应用。现实生活密切相关并在计算机科学中有着极其广泛的应用。组合学问题求解方法层出不穷、干变万化，应以理解为基础，组合学问题求解方法层出不穷、干变万化，应以理解为基础，善于总结各种技巧，掌握科学的组织和推理方法。善于总结各种技巧，掌握科学的组织和推理方法。第2页，本讲稿共103页目录（目录（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图目目 录录第3页，本讲稿共103页目录（目录（2）4.6*在组合恒等式中的应用 本章小结 习题第第5章章 递推关系递推关系 5.1 递推关系的建立 5.2 常系数线性齐次递推关系 5.3 常系数线性非齐次递推关系 5.4 迭代法与归纳法 5.5 母函数在递推关系中的应用 5.6*典型的递推关系 本章小结 习题第第6章章 Plya定理定理 6.1 群的概念 6.2 置换群 6.3 循环、奇循环与偶循环 6.4 Burnside引理 6.5 Plya定理 6.6 Plya定理的应用 6.7 母函数形式的Plya定理 6.8*图的计数 6.9*Plya定理的若干推广 本章小结 习题*课程总结课程总结注：加*的章节一般性了解第4页，本讲稿共103页 存在性问题存在性问题 计数和枚举计数和枚举 优化优化问题问题 构造性问题构造性问题 科学的组织科学的组织 科学的推理科学的推理 古老古老 年轻年轻 练习练习 思考总结思考总结 笔记笔记第5页，本讲稿共103页组合数学研究的中心问题是按照一定的规则来安组合数学研究的中心问题是按照一定的规则来安排有限多个对象排有限多个对象 如果人们想把有限多个对象按照它们所应满足的条件来进行安排，当符合要求的安排并非显然存在或显然不存在时，首要的问题就是要证明或者否定它的存在。这就是存在性问题。如果所要求的安排存在，则可能有多种不同的安排，这又经常给人们提出这样的问题：有多少种可能的安排方案？如何对安排的方案进行分类？这就是计数问题。如果一个组合问题有解，则往往需要给出求其某一特定解的算法，这就是所谓的构造性问题。如果算法很多，就需要在一定的条件下找出一个或者几个最优或近乎最优的安排方案，这就是优化问题。第6页，本讲稿共103页组合数学问题的例子例1.棋盘的完备覆盖第7页，本讲稿共103页组合数学问题的例子例2.36军官问题从6个不同的部队各选6种不同级别的军官,排成6行6列的队列,能否使每行(每列)的军官均来自不同的部队和不同的级别?对哪些n,存在正交的n阶拉丁方?第8页，本讲稿共103页组合数学问题的例子例3.Magic问题:存在性?有多少?如何构造?816357492第9页，本讲稿共103页奇数阶Magic 一个构造 设n=2k+1,j=1,2,.,k.将数码1(或j)填入方格(1,k+1)中(或(j,k+1)若当前数已填入方格(p,q)中,则后继数填入方格(p-1,q+1)中 (模n)当按上述规则填数时,若方格中已填入数或当前数在方格中,则后继数填在当前数的正下方的(或2j-1个)方格中第10页，本讲稿共103页n=5,j=1时17241815235714164613202210121921311182529第11页，本讲稿共103页n=5,j=223619215101811422175132194122581611247203第12页，本讲稿共103页组合数学的例子例4.Nim 游戏有堆硬币,甲,乙两人玩Nim 游戏:每人每次只能从一堆中取硬币(个数不限),取得最后一个硬币者胜出,问什么时候甲有必胜策略?第13页，本讲稿共103页Nim Game平衡Nim Game结论:在平衡Nim Game中,后取者有必胜策略,在不平衡Nim Game中,先取者有必胜策略,第14页，本讲稿共103页Nim 游戏的一个例子甲 乙两人玩Nim 游戏,4 堆的硬币数分别为7,9,12 15.问谁有必胜策略,并给出一个必胜策略.791215第15页，本讲稿共103页作业1.是否存在一个4阶使它具有下列形式.2.试求3行4列棋盘的完备覆盖数.3.甲 乙两人玩Nim 游戏,4 堆的硬币数分别为8,12,14 15.问谁有必胜策略,并给出一个必胜策略.第16页，本讲稿共103页 本章重点介绍以下的基本计数方法：本章重点介绍以下的基本计数方法：加法法则和乘法法则加法法则和乘法法则 排列排列 组合组合 二项式定理的应用二项式定理的应用 组合恒等式组合恒等式第17页，本讲稿共103页 相相互互独独立立的的事事件件 A、B 分分别别有有 k 和和 l 种种方方法法产产生生，则则产产生生 A 或或 B 的的方方法法数数为为 k+l 种。种。1.1 加法法则1.1.1 加法法则加法法则 若若|A|=k，|B|=l，且，且AB=，则，则|AB|=k+l。设设S是有限集合，若是有限集合，若 ，且，且时，时，则有，则有 。第18页，本讲稿共103页1.1 加法法则例11.1.1 加法法则加法法则例例1、有有一一所所学学校校给给一一名名物物理理竞竞赛赛优优胜胜者者发发奖奖，奖奖品品有有三三类类，第第一一类类是是三三种种不不同同版版本本的的法法汉汉词词典典；第第二二类类是是四四种种不不同同类类型型的的物物理理参参考考书书；第第三三类类是是二二种种不不同同的的奖奖杯杯。这这位位优优胜胜者者只只能能挑挑选选一一样样奖奖品品。那那么么，这这位位优优胜胜者者挑挑选选奖奖品的方法有多少种？品的方法有多少种？解解：设设S是是所所有有这这些些奖奖品品的的集集合合，Si是是第第i类类奖奖品品的的集集合合(i=1,2,3)，显然，显然，SiSj=(ij)，根据加法，根据加法法则法则有有第19页，本讲稿共103页1.1 加法法则例2、31.1.1 加法法则加法法则例例2、大大于于0小小于于10的的奇奇偶偶数数有多少个？有多少个？例例3、小小于于20可可被被2或或3整整除除的的自自然然数数有有多少个？多少个？解解：设设S是是符符合合条条件件数数的的集集合合，S1、S2分分别别是是符符合合条条件件的的奇数、偶数集合，显然，奇数、偶数集合，显然，S1S2=，根据加法，根据加法法则法则有有第20页，本讲稿共103页 若若|A|=k，|B|=l，AB=(a,b)|aA，bB，则，则|AB|=kl。1.1 乘法法则1.1.2 乘法法则乘法法则 相相互互独独立立的的事事件件 A、B 分分别别有有 k 和和 l 种种方方法法产产生生，则则选选取取A以以后后再再选选取取B 的方法数为的方法数为 kl 种。种。设设 是有限集合，且是有限集合，且 ，则有，则有 。第21页，本讲稿共103页1.1 乘法法则例41.1.2 乘法法则乘法法则例例4、从从A 地地到到B地地有有二二条条不不同同的的道道路路，从从B地地到到C地地有有四四条条不不同同的的道道路路，而而从从C地地到到D地地有有三三条条不不同同的的道道路路。求求从从A地地经经B、C两地到达两地到达D地的道路数。地的道路数。解解：设设S是是所所求求的的道道路路数数集集合合，S1、S2、S3分分别别是是从从A到到B、从、从B到到C、从、从C到到D的道路集合，根据乘法的道路集合，根据乘法法则法则有有第22页，本讲稿共103页1.1 乘法法则例51.1.2 乘法法则乘法法则例例5、由由数数字字1,2,3,4,5可可以以构构成成多多少少个个所所有数字互不相同的四位偶数？有数字互不相同的四位偶数？解解：所所求求的的是是四四位位偶偶数数，故故个个位位只只能能选选2或或4，有有两两种种选选择择方方法法；又又由由于于要要求求四四位位数数字字互互不不相相同同，故故个个位位选选中中后后，十十位位只只有有四四种种选选择择方方法法；同同理理，百百位位、千千位位分分别别有有三三种种、两两种种选选择择方方法法，根根据乘法据乘法法则，四位数互不相同的偶数个数为法则，四位数互不相同的偶数个数为2 4 3 2=48第23页，本讲稿共103页1.1 乘法法则例61.1.2 乘法法则乘法法则例例6、求求出出从从8个个计计算算机机系系的的学学生生、9个个数数学学系系的的学学生生和和10个个经经济济系系的的学学生生中中选选出出两两个个不同专业的学生的方法数。不同专业的学生的方法数。解：解：由乘法由乘法法则法则有有选一个计算机系和一个数学系的方法数为选一个计算机系和一个数学系的方法数为89=72选一个数学系和一个经济系的方法数为选一个数学系和一个经济系的方法数为910=90选一个经济系和一个计算机系的方法数为选一个经济系和一个计算机系的方法数为108=80由加法由加法法则法则，符合要求的方法数为，符合要求的方法数为72+90+80=242第24页，本讲稿共103页1.1 重集的概念1.1.3 计数问题的分类计数问题的分类 有序安排或有序选择有序安排或有序选择 允许重复允许重复/不允许重复不允许重复 无序安排或无序选择无序安排或无序选择 允许重复允许重复/不允许重复不允许重复 标准集的特性：确定、无序、标准集的特性：确定、无序、相异等。相异等。重集：重集：B=k1*b1,k2*b2,kn*bn，其中：，其中：bi为为n个互不相同个互不相同的元素，称的元素，称 ki为为bi的的重数重数，i=1,2,n，n=1,2,，ki=1,2,。第25页，本讲稿共103页例 求自然数n的不同素因数的个数第26页，本讲稿共103页1.2 线排列1.2.1 线排列线排列从从n个不同元素中，取个不同元素中，取r个个(0rn)按一按一定顺序排列起来，其排列数定顺序排列起来，其排列数P(n,r)。设设A=an，从，从A中选择中选择r个个(0rn)元素排列起元素排列起来，来，A的的r有序子集，有序子集，A的的r排列。排列。如如n,rZ且且nr0,P(n,r)=n!/(n-r)!。如如n=r，称全排列，称全排列P(n,n)=n!；如如nr,P(n,r)=0；如；如r=0,P(n,r)=1。证证明明：构构造造集集合合A的的r排排列列时时，可可以以从从A的的n各各元元素素中中任任选选一一个个作作为为排排列列的的第第一一项项，有有n种种选选法法；第第一一项项选选定定后后从从剩剩下下的的n-1个个元元素素中中选选排排列列的的第第二二项项有有n-1种种选选法法；由此类推，第由此类推，第r项有项有n-r+1种选法。根据乘法种选法。根据乘法法则法则有有第27页，本讲稿共103页1.2 线排列推论11.2.1 线排列线排列推论推论1.1.1：如如n,rN且且nr2，则，则P(n,r)=nP(n-1,r-1)。证证明明：在在集集合合A的的n个个元元素素中中，任任一一个个元元素素都都可可以以排排在在它它的的r排排列列首首位位，故故首首位位有有n种种取取法法；首首位位取取定定后后，其其他他位位置置的的元元素素正正好好是是从从A的的另另n-1个个元元素素中中取取r-1个个的的排排列列，因因此此有有P(n-1,r-1)种取法。由乘法法则有种取法。由乘法法则有P(n,r)=nP(n-1,r-1)证毕。证毕。第28页，本讲稿共103页1.2 线排列推论21.2.1 线排列线排列推论推论1.1.1：如如n,rN且且nr2，则，则P(n,r)=nP(n-1,r-1)。推论推论1.1.2：如如n,rN且且nr2，则，则P(n,r)=rP(n-1,r-1)+P(n-1,r)。证证明明：当当r2时时，把把集集合合A的的r排排列列分分为为两两大大类类：一一类类包包含含A中中的的某某个个固固定定元元素素，不不妨妨设设为为a1，另另一一类类不不包包含含a1。第第一一类类排排列列相相当当于于先先从从A-a1中中取取r-1个个元元素素进进行行排排列列，有有P(n-1,r-1)种种取取法法，再再将将a1放放入入每每一一个个上上述述排排列列中中，对对任任一一排排列列，a1都都有有r种种放放法法。由由乘乘法法法法则则，第第一一类类排排列列共共有有rP(n-1,r-1)个个。第第二二类类排排列列实实质质上上是是A-a1的的r排列，共有排列，共有P(n-1,r)个。再由加法法则有个。再由加法法则有P(n,r)=rP(n-1,r-1)+P(n-1,r)证毕。证毕。第29页，本讲稿共103页1.2 线排列例11.2.1 线排列线排列例例1、由由数数字字1,2,3,4,5可可以以构构成成多多少少个个所有数字互不相同的四位数？所有数字互不相同的四位数？解解：由由于于所所有有的的四四位位数数字字互互不不相相同同，故故每每一一个个四四位位数数就就是是集集合合1,2,3,4,5的的一一个个4排排列列，因因而而所所求求的的四四位位数数个数为个数为第30页，本讲稿共103页1.2 线排列例21.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的的全全排排列列，由由乘乘法法则，排列个数为法法则，排列个数为第31页，本讲稿共103页1.2 线排列例31.2.1 线排列线排列例例3、有有多多少少个个5位位数数，每每位位数数字字都都不不相相同同，不能取不能取0，且数字，且数字7和和9不能相邻？不能相邻？解解：由由于于所所有有的的5位位数数字字互互不不相相同同，且且不不能能取取0，故故每每一一个个5位位数数就就是是集集合合1,2,9的的一一个个5-排排列列，其其排排列列数数为为P(9,5)，其其中中7和和9相相邻邻的的排排列列数数为为42P(7,3)，满满足足题题目要求的目要求的5位数个数为位数个数为第32页，本讲稿共103页例 设由1,2,3,5,6组成的各位数字不同的4位偶数共有N个,它们的和记为M.求N及M.N=P(5,3)3=180用A1,A2,A3,A4分别表示这180 个偶数中的个位,十位,百位,千位数字之和,则M=A1+10A2+100A3+1000A4.在这180个偶数中,个位数为2,4,6的各为60个A1=60(2+4+60)=720.在这180个偶数中,十(百,千)位数为1,3,5的偶数各有 3P(4,2)=36个,为2,4,6的偶数各有 2P(4,2)=24个.A2=A3=A4=(1+3+5)36+(2+4+6)24=612.M=720+612(10+100+1000)=680040.第33页，本讲稿共103页1.2 圆排列1.2.2 圆排列圆排列设设A=an，从从A中中取取r个个(0rn)元元素素按按某某种种顺顺序序（如如逆逆时时针针）排排成成一一个个圆圆圈圈，称称为为圆圆排列（循环排列）。排列（循环排列）。设设A=an，A的的r圆排列个数为圆排列个数为P(n,r)/r。证证明明：由由于于把把一一个个圆圆排排列列旋旋转转所所得得到到另另一一个个圆圆排排列列视视为为相相同同的的圆圆排排列列，因因此此线线排排列列a1a2ar，a2a3ara1，ara1a2ar-1在在圆圆排排列列中中是是一一个个，即即一一个个圆圆排排列列可可产产生生r个个不不同同的的线线排排列列；同同理理，r个个不不同同的的线线排排列列对对应应一一个个圆圆排排列列。而而总总共共有有P(n,r)个个线线排排列，故圆排列的个数为列，故圆排列的个数为 P(n,r)/r=n!/(r(n-r)!)证毕。证毕。第34页，本讲稿共103页1.2 圆排列例41.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坐坐在在一一起起时时，共共有有26!种就座方式，因此如果有两人不愿坐在一起，就座方式为种就座方式，因此如果有两人不愿坐在一起，就座方式为7!-26!=56!=3600第35页，本讲稿共103页1.2 圆排列例51.2.2 圆排列圆排列例例5、4男男4女女围围圆圆桌桌交交替替就就座座有有多多少少种种就座方式？就座方式？解解：显显然然，这这是是一一个个圆圆排排列列问问题题。首首先先让让4个个男男的的围围圆圆桌桌就就座座，有有4!/4=3!种种就就座座方方式式。因因为为要要求求男男女女围围圆圆桌桌交交替替就就座座，在在男男的的坐坐定定后后，两两两两之之间间均均需需留留有有一一个个空空位位，女女的的就就座座相相当当于于一一个个4元元素素集集合合的全排列，就座方式数为的全排列，就座方式数为4!。由乘法法则知，就座方式数为。由乘法法则知，就座方式数为3!4!=144第36页，本讲稿共103页1.2 重排列1.2.3 重排列重排列从从n个不同元素中，可重复选取个不同元素中，可重复选取r个按一个按一定顺序排列起来，称为重排列。定顺序排列起来，称为重排列。从重集从重集B=k1*b1,k2*b2,kn*bn中中选取选取r个按一定顺序排列起来。个按一定顺序排列起来。重集重集B=*b1,*b2,*bn 的的r排排列的个数为列的个数为nr。证证明明：构构造造B的的r排排列列如如下下：选选择择第第一一项项时时可可从从n个个元元素素中中任任选选一一个个，有有n种种选选法法，选选择择第第二二项项时时由由于于可可以以重重复复选选取取，仍仍有有n种种选选法法，同同理理，选选择择第第r项项时时仍仍有有n种种选选法法，根根据据乘乘法法法法则，可得出则，可得出r排列的个数为排列的个数为nr。证毕。证毕。第37页，本讲稿共103页1.2 重排列例61.2.3 重排列重排列例例6、由由数数字字1,2,3,4,5,6这这六六个个数数字字能能组组成成多多少少个个五五位位数数？又又可可组组成成多多少少大大于于34500的五位数？的五位数？解解：一一个个五五位位数数的的各各位位数数字字可可重重复复出出现现，是是一一个个典典型型的的重重排排列列问问题题，相相当当于于重重集集B=*1,*2,*6的的5排排列列，所所求求的的五五位数个数为位数个数为65=7776。大于大于34500的五位数可由下面三种情况组成：的五位数可由下面三种情况组成：万万位位选选4,5,6中中的的一一个个，其其余余4位位相相当当于于重重集集B的的4排排列列，由由乘法法则知，共有乘法法则知，共有3 64个五位数；个五位数；万万位位是是3，千千位位5,6中中的的一一个个，其其余余3位位相相当当于于重重集集B的的3排排列，由乘法法则知，共有列，由乘法法则知，共有2 63个五位数；个五位数；万万位位是是3，千千位位4中中的的一一个个，百百位位选选5,6中中的的一一个个，其其余余2位位相相当当于于重重集集B的的2排排列列，由由乘乘法法法法则则知知，共共有有2 62个个五五位数；位数；由加法法则知，大于由加法法则知，大于34500的五位数个数为的五位数个数为364+263+262=4392第38页，本讲稿共103页1.2 重排列计数1.2.3 重排列重排列重集重集B=n1*b1,n2*b2,nk*bk的全排的全排列列个数为个数为证证明明：将将B中中的的ni个个bi看看作作不不同同的的ni个个元元素素，赋赋予予上上标标1,2,ni，即即 ，如如此此，重重集集B就就变变成成具具有有n1+n2+nk=n个不同的元素集合个不同的元素集合显然，集合显然，集合A的全排列个数为的全排列个数为n!。又又由由于于ni个个bi赋赋予予上上标标的的方方法法有有ni!种种，于于是是对对重重集集B的的任任一一个个全全排排列列，都都可可以以产产生生集集合合A的的n1!n2!nk!个个排排列列（由由乘法法则），故重集乘法法则），故重集B的全排列个数为的全排列个数为证毕。证毕。注：利用组合数的计数方法同样可以得出证明。注：利用组合数的计数方法同样可以得出证明。第39页，本讲稿共103页1.2 重排列例71.2.3 重排列重排列例例6、有有四四面面红红旗旗，三三面面蓝蓝旗旗，二二面面黄黄旗旗，五五面面绿绿旗旗可可以以组组成成多多少少种种由由14面面旗旗子子组组成的一排彩旗？成的一排彩旗？解：解：这是一个重排列问题，是求重集这是一个重排列问题，是求重集4*红旗红旗,3*蓝旗蓝旗,2*黄旗黄旗,5*绿旗绿旗的全排列个数，根据定理，一排彩旗的种数的全排列个数，根据定理，一排彩旗的种数为为第40页，本讲稿共103页1.2 重排列例81.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的全排列的全排列个数。根据加法法则，此类符号个数为个数。根据加法法则，此类符号个数为第41页，本讲稿共103页1.2 项链排列1.2.4 项链排列项链排列 对圆排列，通过转动、平移、翻转、可重合的，即可看作对圆排列，通过转动、平移、翻转、可重合的，即可看作项链排列。项链排列。如如n个不同元素的个不同元素的r项链排列个数为项链排列个数为P(n,r)/(2r)，具，具体参照体参照Plya定理定理。第42页，本讲稿共103页第1章 习题 1.以以A表示集合表示集合1,2,n的全部的全部非空子集所成之集非空子集所成之集,试求试求A中集合的中集合的所有元素之和所有元素之和.2.把把2n个人分成个人分成n组组,每组每组2 人人,有多有多少种不同的分组方法少种不同的分组方法.第43页，本讲稿共103页1.3 无重组合1.3.1 （无重）组合（无重）组合设设A=an，从，从A中选择中选择r个个(0rn)元素组合起来，元素组合起来，A的的r无序子集，无序子集，A的的r组合。组合。如如rn，有，有C(n,r)=P(n,r)/r!=n!/(r!(n-r)!)。如如nr=0，C(n,r)=1；如如nr，C(n,r)=0。从从n个不同元素中，取个不同元素中，取r个个(0rn)不考不考虑顺序组合起来，其组合数虑顺序组合起来，其组合数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)，因此有，因此有第44页，本讲稿共103页1.3 无重组合例11.3.1 （无重）组合（无重）组合例例1、有有5本本日日文文书书，7本本英英文文书书，10本本中中文文书书，从从中中取取两两本本不不同同文文字字的的书书，问问有有多多少少种种方方案案？若若取取两两本本相相同同文文字字的的书书，问问有有多多少少种种方案？任取两本书，有多少种方案？方案？任取两本书，有多少种方案？解解：从从三三种种文文字字的的书书中中取取两两种种共共有有C(3,2)=3种种取取法法。根根据据乘乘法法法法则则有有：日日英英各各一一本本的的方方法法数数为为57=35，中中英英各各一一本本的的方方法法数数为为107=70，中中日日各一本的方法数为各一本的方法数为105=50，由加法法则得，由加法法则得35+70+50=155取两本相同文字的，有两本中文、两本英文或两本日文三种方式，由加法法取两本相同文字的，有两本中文、两本英文或两本日文三种方式，由加法法则得则得C(5,2)+C(7,2)+C(10,2)=76任取两本书，相当于从任取两本书，相当于从5+7+10=22本书中取两本的组合，即本书中取两本的组合，即C(22,2)=231第45页，本讲稿共103页例.设An是一个凸n边形,在An的内部任何3条对角线不相交于同一点,求(1)An的对角线的条数;(2)由An的边和对角线围成的三角形的个数第46页，本讲稿共103页1.3 无重组合例21.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，由乘法法则有，由乘法法则有1003种方案。种方案。由加法法则得，所求的方案数为由加法法则得，所求的方案数为3C(100,3)+1003=1485100第47页，本讲稿共103页1.3 无重组合例31.3.1 （无重）组合（无重）组合例例3、某某车车站站有有1到到6个个入入口口处处，每每个个入入口口处处每每次次只只能能进进一一个个人人，问问一一小小组组9个个人进站的方案数有多少？人进站的方案数有多少？解解I：按按照照从从入入口口1到到入入口口6的的顺顺序序可可得得到到9个个人人一一个个排排列列，再再把把两两个个入入口口间间设设上上一一个个标标志志，加加上上这这5个个标标志志相相当当于于每每一一个个排排列列有有14个个元元素素，其其中中5个个标标志志没没有有区区别别，但但其其位位置置将将区区分分各各入入口口的的进进站站人人数数，相相当当于于14个个元元素素集集合合的的5组组合合，故进站方案数为故进站方案数为9!C(14,5)=726485760解解II：同同上上分分析析，问问题题转转化化为为重重集集1*p1,1*p2,1*p9,5*标标志志的的全全排排列列（pi代表代表9个人，个人，i=1,9），故进站方案数为），故进站方案数为14!/5!=726485760解解III：考考虑虑9个个人人选选择择方方案案，第第1个个人人有有6种种选选择择，第第2个个人人除除了了选选择择入入口口，还还要要考考虑虑在在第第1个个人人的的前前面面或或后后面面，故故有有7种种选选择择同同理理，第第9个个人人有有14种选择，根据乘法法则，故进站方案数为种选择，根据乘法法则，故进站方案数为6 7 14=726485760第48页，本讲稿共103页1.3 无重组合例41.3.1 （无重）组合（无重）组合例例4、求求5位位数数中中至至少少出出现现一一个个6，而而被被3整除的数的个数整除的数的个数。解解：10进进制制数数被被3整整除除的的充充要要条条件件是是各各位位数数的的和和能能被被3整整除除。据据此此可可进行如下讨论：进行如下讨论：从从左左往往右右计计，如如最最后后一一个个6出出现现在在个个位位，则则十十百百千千位位各各有有10种种选选择择，万万位位有有3种可能，根据乘法法则，总个数为种可能，根据乘法法则，总个数为3103；如如最最后后一一个个6出出现现在在十十位位，则则个个位位有有9种种选选择择，百百千千位位各各有有10种种选选择择，万位有万位有3种可能，根据乘法法则，总个数为种可能，根据乘法法则，总个数为31029；如如最最后后一一个个6出出现现在在百百位位，则则个个十十位位各各有有9种种选选择择，千千位位有有10种种选选择择，万位有万位有3种可能，根据乘法法则，总个数为种可能，根据乘法法则，总个数为31092；如如最最后后一一个个6出出现现在在千千位位，则则个个十十百百位位各各有有9种种选选择择，万万位位有有3种种可可能能，根根据据乘法法则，总个数为乘法法则，总个数为393；如如最最后后一一个个6出出现现在在万万位位，则则个个十十百百位位各各有有9种种选选择择，千千位位有有3种种可可能能，根根据据乘法法则，总个数为乘法法则，总个数为393；根据加法法则，符合条件的整数个数为根据加法法则，符合条件的整数个数为3103+31029+31092+393+393=12504第49页，本讲稿共103页1.3 无重组合例51.3.1 （无重）组合（无重）组合例例5、求求1000!的末尾有几个零。的末尾有几个零。解解：此此问问题题在在于于求求将将1000!分分解解为为素素数数的的乘乘积积时时，2和和5的的幂幂是是多多少少。末尾零的个数应该等于末尾零的个数应该等于2和和5的幂中较小的那个数。的幂中较小的那个数。11000中中5的的倍倍数数的的数数共共200个个，其其中中有有40个个52的的倍倍数数，这这40个个数数中中有有8个个53的的倍倍数数，而而这这8个个数数中中又又有有1个个54的的倍倍数数，故故1000!分分解解为为素素数数的的乘积时，乘积时，5的幂应该是的幂应该是200+40+8+1=249显然，显然，2的幂必然大于的幂必然大于249，因此，因此1000!的末尾有的末尾有249个零。个零。第50页，本讲稿共103页1.3 无重组合例61.3.1 （无重）组合（无重）组合例例6、求求能能除除尽尽1400的的正正整整数数数数目目（1除除外外），其中包含多少个奇数？其中包含多少个奇数？解解：1400=23527，故故除除尽尽1400的的正正整整数数分分解解为为素素数数的的乘乘积积的的形形式式应应该该为为2l5m7n，其其中中0l3,0m2,0n1，但但应应排排除除l=m=n=0的的情情况况。故满足条件的数目为故满足条件的数目为(3+1)(2+1)(1+1)-1=23其中包含的奇数为其中包含的奇数为(1)(2+1)(1+1)-1=5第51页，本讲稿共103页1.3 重复组合1.3.2 重复组合重复组合从从n个不同元素中，可重复选取个不同元素中，可重复选取r个不考虑顺个不考虑顺序组合起来，其组合数序组合起来，其组合数F(n,r)。从重集从重集B=k1*b1,k2*b2,kn*bn中取中取r个元素不考虑顺序的组合。个元素不考虑顺序的组合。重集重集B=*b1,*b2,*bn 的的r组组合数合数F(n,r)=C(n+r-1,r)证证明明：设设n个个元元素素b1,b2,bn和和自自然然数数1,2,n一一一一对对应应。于于是是任任何何组组合合皆皆可可看看作作是是一一个个r个个数数的的组组合合c1,c2,cr。由由于于是是组组合合，不不妨妨认认为为各各ci是是按按照照大大小小顺顺序序排排列列的的，相相同同的的ci连连续续排排在在一一起起，不妨设不妨设c1c2cr。又令又令di=ci+i-1(i=1,2,r)，即，即d1=c1,d2=c2+1,dr=cr+r-1。因因1cin，故故1din+r-1，得得到到一一个个集集合合1,2,n+r-1的的r组组合合 d1,d2,dr(d1d2dr)。显显然然有有一一种种c1,c2,cr的的取取法法，就就有有一一种种d1,d2,dr的的取取法法，反反之之亦亦然然，这这两两种种取取法法是是一一一一对对应应的的，从从而而这这两两种种取取法法是是等等价价的的。如如此此，从从n个个不不同同元元素素中中可可重重复复选选取取r个个的的组组合合数数，和和从从n+r-1个不同元素中不重复选取个不同元素中不重复选取r个的组合数是相同的，故个的组合数是相同的，故F(n,r)=C(n+r-1,r)第52页，本讲稿共103页1.3 重复组合例71.3.2 重复组合重复组合r个无区别的球放入个无区别的球放入n个有标志的盒子里，个有标志的盒子里，每盒的球数可多于每盒的球数可多于1个，则共有个，则共有F(n,r)种种方案。方案。例例7、试问试问(x+y+z)4的展开式有多少项？的展开式有多少项？证证明明：这这是是一一个个允允许许重重复复组组合合的的典典型型问问题题，实实质质上上定定理理1.6的的另另一一种种 说说 法法。由由 于于 每每 盒盒 的的 球球 数数 不不 受受 限限 制制，相相 当当 于于 重重 集集*a1,*a2,*an的的r组合。组合。解解：(x+y+z)4展展开开式式每每一一项项都都是是4次次方方的的，相相当当于于从从3个个不不同同元元素素中中可可以以重重复复的的选选择择4个个，或或者者相相当当于于将将4个个无无区区别别的的球球放放到到3个个有有标标志的盒子里。故展开项个数为志的盒子里。故展开项个数为 F(3,4)=C(3+4-1,4)=15第53页，本讲稿共103页1.3 重复组合例8、91.3.2 重复组合重复组合例例8、某某餐餐厅厅有有7种种不不同同的的菜菜，为为了了招招待待朋朋友友，一一个个顾顾客客需需要要买买14个个菜菜，问问有有多多少种买法？少种买法？例例9、求求n个个无无区区别别的的球球放放入入r个个有有标标志志的的盒盒子子里里(nr)而而无无一一空空盒盒的的方方案案数。数。解解：这这 个个 问问 题题 相相 当当 于于 重重 集集*1,*2,*7的的14组组合合。根根据据定理定理1.6知买菜的方法数为知买菜的方法数为F(7,14)=C(7+14-1,14)=4845解解：由由于于每每个个盒盒子子不不能能为为空空，故故每每个个盒盒子子里里可可先先放放一一个个球球，这这样样还还剩剩n-r个个球球，再再将将这这n-r个个球球防防到到r个个盒盒子子里里，由由于于这这时时每每盒盒的的球球数数不不受受限限制制，相相当当于于重重集集*a1,*a2,*ar的的n-r组组