第1章 排列与组合精选文档.ppt

《第1章 排列与组合精选文档.ppt》由会员分享，可在线阅读，更多相关《第1章 排列与组合精选文档.ppt（103页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第1章 排列与组合本讲稿第一页，共一百零三页课程简介课程简介相关课程相关课程使用教材使用教材数学分析高等代数数学分析高等代数书名：组合数学书名：组合数学作者：曹汝成作者：曹汝成 出版社：华南理工大学出版社出版社：华南理工大学出版社 本本课课程程针针对对计计算算机机科科学学中中的的一一个个重重要要学学科科组组合合数数学学，组组合合数数学学是是数数学学的的一一个个分分支支，它它研研究究事事物物在在结结定定模模式式下下的的配配置置，研研究究这这种种配配置置的的存存在在性性，所所有有可可能能配配置置的的计计数数和和分分类类以以及及配配置置的的各各种种性性质质。组组合合数数学学与与现现实实生生活活密密切

2、切相相关关并并在在计计算算机机科科学学中中有有着着极极其广泛的应用。其广泛的应用。组合学问题求解方法层出不穷、干变万化，应以理解为基组合学问题求解方法层出不穷、干变万化，应以理解为基础，善于总结各种技巧，掌握科学的组织和推理方法。础，善于总结各种技巧，掌握科学的组织和推理方法。本讲稿第二页，共一百零三页目录（目录（1）引言引言第第1章章 排列与组合排列与组合 1.1 加法法则和乘法法则 1.2 排列 1.3 组合 1.4 二项式定理 1.5 组合恒等式及其含义 1.6 模型转换 本章小结 习题第第2章章 鸽笼原理鸽笼原理 2.1 鸽笼原理 2.2 鸽笼原理的推广 2.3 Ramsey定理 本章

3、小结 习题第第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 母函数在递推关系中的应用

4、 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定理的若干推广 本章小结 习题*课程总结课程总结注：加*的章节一般性了解本讲稿第四页，共一百零三页 存在性问题存在性问题 计数和枚举计数和枚举 优化优化问题问题 构造性问题构造性问题 科学的组织科学的组织 科学的推理科学的推理 古老古老 年轻年轻 练习练习 思考总结思考总结 笔记笔记本讲稿第五页，共一百零三页组合数学

5、研究的中心问题是按照一定的规则来组合数学研究的中心问题是按照一定的规则来安排有限多个对象安排有限多个对象 如果人们想把有限多个对象按照它们所应满足的条件来进行安排，当符合要求的安排并非显然存在或显然不存在时，首要的问题就是要证明或者否定它的存在。这就是存在性问题。如果所要求的安排存在，则可能有多种不同的安排，这又经常给人们提出这样的问题：有多少种可能的安排方案？如何对安排的方案进行分类？这就是计数问题。如果一个组合问题有解，则往往需要给出求其某一特定解的算法，这就是所谓的构造性问题。如果算法很多，就需要在一定的条件下找出一个或者几个最优或近乎最优的安排方案，这就是优化问题。本讲稿第六页，共一百

6、零三页组合数学问题的例子例1.棋盘的完备覆盖本讲稿第七页，共一百零三页组合数学问题的例子例2.36军官问题从6个不同的部队各选6种不同级别的军官,排成6行6列的队列,能否使每行(每列)的军官均来自不同的部队和不同的级别?对哪些n,存在正交的n阶拉丁方?本讲稿第八页，共一百零三页组合数学问题的例子例3.Magic问题:存在性?有多少?如何构造?816357492本讲稿第九页，共一百零三页奇数阶Magic 一个构造 设n=2k+1,j=1,2,.,k.将数码1(或j)填入方格(1,k+1)中(或(j,k+1)若当前数已填入方格(p,q)中,则后继数填入方格(p-1,q+1)中 (模n)当按上述规则

7、填数时,若方格中已填入数或当前数在方格中,则后继数填在当前数的正下方的(或2j-1个)方格中本讲稿第十页，共一百零三页n=5,j=1时17241815235714164613202210121921311182529本讲稿第十一页，共一百零三页n=5,j=223619215101811422175132194122581611247203本讲稿第十二页，共一百零三页组合数学的例子例4.Nim 游戏有堆硬币,甲,乙两人玩Nim 游戏:每人每次只能从一堆中取硬币(个数不限),取得最后一个硬币者胜出,问什么时候甲有必胜策略?本讲稿第十三页，共一百零三页Nim Game平衡Nim Game结论:在平衡

8、Nim Game中,后取者有必胜策略,在不平衡Nim Game中,先取者有必胜策略,本讲稿第十四页，共一百零三页Nim 游戏的一个例子甲 乙两人玩Nim 游戏,4 堆的硬币数分别为7,9,12 15.问谁有必胜策略,并给出一个必胜策略.791215本讲稿第十五页，共一百零三页作业1.是否存在一个4阶使它具有下列形式.2.试求3行4列棋盘的完备覆盖数.3.甲 乙两人玩Nim 游戏,4 堆的硬币数分别为8,12,14 15.问谁有必胜策略,并给出一个必胜策略.本讲稿第十六页，共一百零三页 本章重点介绍以下的基本计数方法：本章重点介绍以下的基本计数方法：加法法则和乘法法则加法法则和乘法法则 排列排列

9、 组合组合 二项式定理的应用二项式定理的应用 组合恒等式组合恒等式本讲稿第十七页，共一百零三页 相相互互独独立立的的事事件件 A、B 分分别别有有 k 和和 l 种种方方法法产产生生，则则产产生生 A 或或 B 的的方方法法数为数为 k+l 种。种。1.1 加法法则1.1.1 加法法则加法法则 若若|A|=k，|B|=l，且，且AB=，则，则|AB|=k+l。设设S是有限集合，若是有限集合，若 ，且，且时，时，则有，则有 。本讲稿第十八页，共一百零三页1.1 加法法则例11.1.1 加法法则加法法则例例1、有有一一所所学学校校给给一一名名物物理理竞竞赛赛优优胜胜者者发发奖奖，奖奖品品有有三三类

10、类，第第一一类类是是三三种种不不同同版版本本的的法法汉汉词词典典；第第二二类类是是四四种种不不同同类类型型的的物物理理参参考考书书；第第三三类类是是二二种种不不同同的的奖奖杯杯。这这位位优优胜胜者者只只能能挑挑选选一一样样奖奖品品。那那么么，这这位位优胜者挑选奖品的方法有多少种？优胜者挑选奖品的方法有多少种？解解：设设S是是所所有有这这些些奖奖品品的的集集合合，Si是是第第i类类奖奖品品的的集集合合(i=1,2,3)，显然，显然，SiSj=(ij)，根据加法，根据加法法则法则有有本讲稿第十九页，共一百零三页1.1 加法法则例2、31.1.1 加法法则加法法则例例2、大大于于0小小于于10的的奇

11、奇偶偶数数有有多少个？多少个？例例3、小小于于20可可被被2或或3整整除除的的自自然然数数有多少个？有多少个？解解：设设S是是符符合合条条件件数数的的集集合合，S1、S2分分别别是是符符合合条条件件的的奇数、偶数集合，显然，奇数、偶数集合，显然，S1S2=，根据加法，根据加法法则法则有有本讲稿第二十页，共一百零三页 若若|A|=k，|B|=l，AB=(a,b)|aA，bB，则，则|AB|=kl。1.1 乘法法则1.1.2 乘法法则乘法法则 相相互互独独立立的的事事件件 A、B 分分别别有有 k 和和 l 种种方方法法产产生生，则则选选取取A以以后后再再选选取取B 的方法数为的方法数为 kl 种

12、。种。设设 是有限集合，且是有限集合，且 ，则有，则有 。本讲稿第二十一页，共一百零三页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的道路集合，根据乘法的道路集合，根据乘法法则法则有有本讲稿第二十二页，共一百零三页1.1 乘法法则例

13、51.1.2 乘法法则乘法法则例例5、由由数数字字1,2,3,4,5可可以以构构成成多多少少个个所所有有数数字互不相同的四位偶数？字互不相同的四位偶数？解解：所所求求的的是是四四位位偶偶数数，故故个个位位只只能能选选2或或4，有有两两种种选选择择方方法法；又又由由于于要要求求四四位位数数字字互互不不相相同同，故故个个位位选选中中后后，十十位位只只有有四四种种选选择择方方法法；同同理理，百百位位、千千位位分分别别有有三三种种、两两种种选选择择方法，根据乘法方法，根据乘法法则，四位数互不相同的偶数个数为法则，四位数互不相同的偶数个数为2 4 3 2=48本讲稿第二十三页，共一百零三页1.1 乘法法

14、则例61.1.2 乘法法则乘法法则例例6、求求出出从从8个个计计算算机机系系的的学学生生、9个个数数学学系系的的学学生生和和10个个经经济济系系的的学学生生中中选选出出两个不同专业的学生的方法数。两个不同专业的学生的方法数。解：解：由乘法由乘法法则法则有有选一个计算机系和一个数学系的方法数为选一个计算机系和一个数学系的方法数为89=72选一个数学系和一个经济系的方法数为选一个数学系和一个经济系的方法数为910=90选一个经济系和一个计算机系的方法数为选一个经济系和一个计算机系的方法数为108=80由加法由加法法则法则，符合要求的方法数为，符合要求的方法数为72+90+80=242本讲稿第二十四

15、页，共一百零三页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,。本讲稿第二十五页，共一百零三页例 求自然数n的不同素因数的个数本讲稿第二十六页，共一百零三页1.2 线排列1.

16、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种种选选法法；第第一一

17、项项选选定定后后从从剩剩下下的的n-1个个元元素素中中选选排排列列的的第第二二项项有有n-1种种选选法法；由此类推，第由此类推，第r项有项有n-r+1种选法。根据乘法种选法。根据乘法法则法则有有本讲稿第二十七页，共一百零三页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个个元元素素中

18、中取取r-1个个的的排排列列，因因此此有有P(n-1,r-1)种取法。由乘法法则有种取法。由乘法法则有P(n,r)=nP(n-1,r-1)证毕。证毕。本讲稿第二十八页，共一百零三页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。第第

19、一一类类排排列列相相当当于于先先从从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)证毕。证毕。本讲稿第二十九页，共一百零三页1.2 线排列例11.2.1 线排列线排列例例1、由由数数字字1,2,3,

20、4,5可可以以构构成成多多少少个个所有数字互不相同的四位数？所有数字互不相同的四位数？解解：由由于于所所有有的的四四位位数数字字互互不不相相同同，故故每每一一个个四四位位数数就就是是集集合合1,2,3,4,5的的一一个个4排排列列，因因而而所所求求的的四四位位数数个数为个数为本讲稿第三十页，共一百零三页1.2 线排列例21.2.1 线排列线排列例例 2、将将 具具 有有 9个个 字字 母母 的的 单单 词词FRAGMENTS进进行行排排列列，要要求求字字母母A总总是是紧紧跟跟在在字字母母R的的右右边边，问问有有多多少少种种这这样样的的排排法法？如如果果再再要要求求字字母母M和和N必必须相邻呢？

21、须相邻呢？解解：由由于于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 线排列例31.2.1 线排列线排列例例3、有有多多少少个个5位位数数，每每位位数数字字

22、都都不不相相同，不能取同，不能取0，且数字，且数字7和和9不能相邻？不能相邻？解解：由由于于所所有有的的5位位数数字字互互不不相相同同，且且不不能能取取0，故故每每一一个个5位位数数就就是是集集合合1,2,9的的一一个个5-排排列列，其其排排列列数数为为P(9,5)，其其中中7和和9相相邻邻的的排排列列数数为为42P(7,3)，满满足足题题目要求的目要求的5位数个数为位数个数为本讲稿第三十二页，共一百零三页例 设由1,2,3,5,6组成的各位数字不同的4位偶数共有N个,它们的和记为M.求N及M.N=P(5,3)3=180用A1,A2,A3,A4分别表示这180 个偶数中的个位,十位,百位,千位

23、数字之和,则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.本讲稿第三十三页，共一百零三页1.2 圆排列1.2.2 圆排列圆排列设设A=an，从从A中中取取r个个(0rn)元元素素按按某某种种顺顺序序（如如逆逆时时针针）排排成成一一个个圆圆圈圈，称称为为圆排

24、列（循环排列）。圆排列（循环排列）。设设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)!)证毕。证毕。

25、本讲稿第三十四页，共一百零三页1.2 圆排列例41.2.2 圆排列圆排列例例4、有有8人人围围圆圆桌桌就就餐餐，问问有有多多少少种种就就座座方方式式？如如果果有有两两人人不不愿愿坐坐在在一一起起，又又有有多多少少种就座方式？种就座方式？解解：由由上上述述定定理理知知8人人围围圆圆桌桌就就餐餐，有有8!/8=7!=5040种种就就座座方式。方式。又又有有两两人人不不愿愿坐坐在在一一起起，不不妨妨设设此此二二人人为为A、B，当当A、B坐坐在在一一起起时时，相相当当于于7人人围围圆圆桌桌就就餐餐，有有7!/7=6!种种就就座座方方式式。而而A、B坐坐在在一一起起时时，又又有有两两种种情情况况，或或者

26、者A在在B的的左左面面，或或者者A在在B的的右右面面，因因此此A、B坐坐在在一一起起时时，共共有有26!种就座方式，因此如果有两人不愿坐在一起，就座方式为种就座方式，因此如果有两人不愿坐在一起，就座方式为7!-26!=56!=3600本讲稿第三十五页，共一百零三页1.2 圆排列例51.2.2 圆排列圆排列例例5、4男男4女女围围圆圆桌桌交交替替就就座座有有多多少少种种就座方式？就座方式？解解：显显然然，这这是是一一个个圆圆排排列列问问题题。首首先先让让4个个男男的的围围圆圆桌桌就就座座，有有4!/4=3!种种就就座座方方式式。因因为为要要求求男男女女围围圆圆桌桌交交替替就就座座，在在男男的的坐

27、坐定定后后，两两两两之之间间均均需需留留有有一一个个空空位位，女女的的就就座座相相当当于于一一个个4元元素素集集合合的的全全排排列列，就就座座方方式式数数为为4!。由由乘乘法法法法则则知知，就就座座方方式数为式数为3!4!=144本讲稿第三十六页，共一百零三页1.2 重排列1.2.3 重排列重排列从从n个不同元素中，可重复选取个不同元素中，可重复选取r个按一定个按一定顺序排列起来，称为重排列。顺序排列起来，称为重排列。从重集从重集B=k1*b1,k2*b2,kn*bn中中选取选取r个按一定顺序排列起来。个按一定顺序排列起来。重集重集B=*b1,*b2,*bn 的的r排排列的个数为列的个数为nr

28、。证证明明：构构造造B的的r排排列列如如下下：选选择择第第一一项项时时可可从从n个个元元素素中中任任选选一一个个，有有n种种选选法法，选选择择第第二二项项时时由由于于可可以以重重复复选选取取，仍仍有有n种种选选法法，同同理理，选选择择第第r项项时时仍仍有有n种种选选法法，根根据据乘乘法法法法则则，可得出可得出r排列的个数为排列的个数为nr。证毕。证毕。本讲稿第三十七页，共一百零三页1.2 重排列例61.2.3 重排列重排列例例6、由由数数字字1,2,3,4,5,6这这六六个个数数字字能能组组成成多多少少个个五五位位数数？又又可可组组成成多多少少大大于于34500的五位数？的五位数？解解：一一个

29、个五五位位数数的的各各位位数数字字可可重重复复出出现现，是是一一个个典典型型的的重重排排列列问问题题，相相当当于于重重集集B=*1,*2,*6的的5排排列列，所所求求的的五五位位数个数为数个数为65=7776。大于大于34500的五位数可由下面三种情况组成：的五位数可由下面三种情况组成：万万位位选选4,5,6中中的的一一个个，其其余余4位位相相当当于于重重集集B的的4排排列列，由乘法法则知，共有由乘法法则知，共有3 64个五位数；个五位数；万万位位是是3，千千位位5,6中中的的一一个个，其其余余3位位相相当当于于重重集集B的的3排排列列，由乘法法则知，共有由乘法法则知，共有2 63个五位数；个

30、五位数；万万位位是是3，千千位位4中中的的一一个个，百百位位选选5,6中中的的一一个个，其其余余2位位相当于重集相当于重集B的的2排列，由乘法法则知，共有排列，由乘法法则知，共有2 62个五位数；个五位数；由加法法则知，大于由加法法则知，大于34500的五位数个数为的五位数个数为364+263+262=4392本讲稿第三十八页，共一百零三页1.2 重排列计数1.2.3 重排列重排列重集重集B=n1*b1,n2*b2,nk*bk的全排的全排列列个数为个数为证证明明：将将B中中的的ni个个bi看看作作不不同同的的ni个个元元素素，赋赋予予上上标标1,2,ni，即即 ，如如此此，重重集集B就就变变成

31、成具具有有n1+n2+nk=n个不同的元素集合个不同的元素集合显然，集合显然，集合A的全排列个数为的全排列个数为n!。又又由由于于ni个个bi赋赋予予上上标标的的方方法法有有ni!种种，于于是是对对重重集集B的的任任一一个个全全排排列列，都都可可以以产产生生集集合合A的的n1!n2!nk!个个排排列列（由由乘法法则），故重集乘法法则），故重集B的全排列个数为的全排列个数为证毕。证毕。注：利用组合数的计数方法同样可以得出证明。注：利用组合数的计数方法同样可以得出证明。本讲稿第三十九页，共一百零三页1.2 重排列例71.2.3 重排列重排列例例6、有有四四面面红红旗旗，三三面面蓝蓝旗旗，二二面面黄

32、黄旗旗，五五面面绿绿旗旗可可以以组组成成多多少少种种由由14面面旗旗子子组组成成的的一排彩旗？一排彩旗？解：解：这是一个重排列问题，是求重集这是一个重排列问题，是求重集4*红旗红旗,3*蓝旗蓝旗,2*黄旗黄旗,5*绿旗绿旗的全排列个数，根据定理，一排彩旗的种数的全排列个数，根据定理，一排彩旗的种数为为本讲稿第四十页，共一百零三页1.2 重排列例81.2.3 重排列重排列例例8、用用字字母母A、B、C组组成成五五个个字字母母的的符符号号，要要求求在在每每个个符符号号里里，A至至多多出出现现2次次，B至至多多出出现现1次次，C至至多多出出现现3次次，求求此此类类符号的个数。符号的个数。解：解：这也

33、是一个重排列问题。根据分析，符合题意的符号这也是一个重排列问题。根据分析，符合题意的符号个数相当于求重集个数相当于求重集M=2*A,1*B,3*C的的5排列个数，可分排列个数，可分为三种情况：需要分别求为三种情况：需要分别求M-A、M-B和和M-C的全排列的全排列个数。根据加法法则，此类符号个数为个数。根据加法法则，此类符号个数为本讲稿第四十一页，共一百零三页1.2 项链排列1.2.4 项链排列项链排列 对圆排列，通过转动、平移、翻转、可重合的，即对圆排列，通过转动、平移、翻转、可重合的，即可看作项链排列。可看作项链排列。如如n个不同元素的个不同元素的r项链排列个数为项链排列个数为P(n,r)

34、/(2r)，具体，具体参照参照Plya定理定理。本讲稿第四十二页，共一百零三页第1章 习题 1.以以A表示集合表示集合1,2,n的全部非空的全部非空子集所成之集子集所成之集,试求试求A中集合的所有元素中集合的所有元素之和之和.2.把把2n个人分成个人分成n组组,每组每组2 人人,有多少有多少种不同的分组方法种不同的分组方法.本讲稿第四十三页，共一百零三页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

35、-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)，因此有，因此有本讲稿第四十四页，共一百零三页

36、1.3 无重组合例11.3.1 （无重）组合（无重）组合例例1、有有5本本日日文文书书，7本本英英文文书书，10本本中中文文书书，从从中中取取两两本本不不同同文文字字的的书书，问问有有多多少少种种方方案案？若若取取两两本本相相同同文文字字的的书书，问问有有多多少少种种方方案案？任任取两本书，有多少种方案？取两本书，有多少种方案？解解：从从三三种种文文字字的的书书中中取取两两种种共共有有C(3,2)=3种种取取法法。根根据据乘乘法法法法则则有有：日日英英各各一一本本的的方方法法数数为为57=35，中中英英各各一一本本的的方方法法数数为为107=70，中中日日各一本的方法数为各一本的方法数为105

37、=50，由加法法则得，由加法法则得35+70+50=155取两本相同文字的，有两本中文、两本英文或两本日文三种方式，由加法法取两本相同文字的，有两本中文、两本英文或两本日文三种方式，由加法法则得则得C(5,2)+C(7,2)+C(10,2)=76任取两本书，相当于从任取两本书，相当于从5+7+10=22本书中取两本的组合，即本书中取两本的组合，即C(22,2)=231本讲稿第四十五页，共一百零三页例.设An是一个凸n边形,在An的内部任何3条对角线不相交于同一点,求(1)An的对角线的条数;(2)由An的边和对角线围成的三角形的个数本讲稿第四十六页，共一百零三页1.3 无重组合例21.3.1

38、（无重）组合（无重）组合例例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

39、)种方案；种方案；三个数同属于集合三个数同属于集合C，有，有C(100,3)种方案；种方案；三个数分别属于集合三个数分别属于集合A,B,C，由乘法法则有，由乘法法则有1003种方案。种方案。由加法法则得，所求的方案数为由加法法则得，所求的方案数为3C(100,3)+1003=1485100本讲稿第四十七页，共一百零三页1.3 无重组合例31.3.1 （无重）组合（无重）组合例例3、某某车车站站有有1到到6个个入入口口处处，每每个个入入口口处处每每次次只只能能进进一一个个人人，问问一一小小组组9个个人人进进站的方案数有多少？站的方案数有多少？解解I：按按照照从从入入口口1到到入入口口6的的顺顺序

40、序可可得得到到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!=

41、726485760解解III：考考虑虑9个个人人选选择择方方案案，第第1个个人人有有6种种选选择择，第第2个个人人除除了了选选择择入入口口，还还要要考考虑虑在在第第1个个人人的的前前面面或或后后面面，故故有有7种种选选择择同同理理，第第9个个人人有有14种种选择，根据乘法法则，故进站方案数为选择，根据乘法法则，故进站方案数为6 7 14=726485760本讲稿第四十八页，共一百零三页1.3 无重组合例41.3.1 （无重）组合（无重）组合例例4、求求5位位数数中中至至少少出出现现一一个个6，而而被被3整整除除的的数的个数数的个数。解解：10进进制制数数被被3整整除除的的充充要要条条件件是是各

42、各位位数数的的和和能能被被3整整除除。据据此此可可进进行行如下讨论：如下讨论：从从左左往往右右计计，如如最最后后一一个个6出出现现在在个个位位，则则十十百百千千位位各各有有10种种选选择择，万位有万位有3种可能，根据乘法法则，总个数为种可能，根据乘法法则，总个数为3103；如如最最后后一一个个6出出现现在在十十位位，则则个个位位有有9种种选选择择，百百千千位位各各有有10种种选选择择，万位有万位有3种可能，根据乘法法则，总个数为种可能，根据乘法法则，总个数为31029；如如最最后后一一个个6出出现现在在百百位位，则则个个十十位位各各有有9种种选选择择，千千位位有有10种种选选择，万位有择，万位

43、有3种可能，根据乘法法则，总个数为种可能，根据乘法法则，总个数为31092；如如最最后后一一个个6出出现现在在千千位位，则则个个十十百百位位各各有有9种种选选择择，万万位位有有3种种可能，根据乘法法则，总个数为可能，根据乘法法则，总个数为393；如如最最后后一一个个6出出现现在在万万位位，则则个个十十百百位位各各有有9种种选选择择，千千位位有有3种种可能，根据乘法法则，总个数为可能，根据乘法法则，总个数为393；根据加法法则，符合条件的整数个数为根据加法法则，符合条件的整数个数为3103+31029+31092+393+393=12504本讲稿第四十九页，共一百零三页1.3 无重组合例51.3

44、.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的幂

45、必然大于的幂必然大于249，因此，因此1000!的末尾有的末尾有249个零。个零。本讲稿第五十页，共一百零三页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其中包含的奇数为

46、其中包含的奇数为(1)(2+1)(1+1)-1=5本讲稿第五十一页，共一百零三页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个个数数

47、的的组组合合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的的取取法法，反反之之亦亦然然，这这两两种种取取法法是是一一一一对对应应的的，从从而而这这两两种种取取法

48、法是是等等价价的的。如如此此，从从n个个不不同同元元素素中中可可重重复复选选取取r个个的的组组合合数数，和和从从n+r-1个个不同元素中不重复选取不同元素中不重复选取r个的组合数是相同的，故个的组合数是相同的，故F(n,r)=C(n+r-1,r)本讲稿第五十二页，共一百零三页1.3 重复组合例71.3.2 重复组合重复组合r个无区别的球放入个无区别的球放入n个有标志的盒子里，个有标志的盒子里，每盒的球数可多于每盒的球数可多于1个，则共有个，则共有F(n,r)种种方案。方案。例例7、试问试问(x+y+z)4的展开式有多少项？的展开式有多少项？证证明明：这这是是一一个个允允许许重重复复组组合合的的

49、典典型型问问题题，实实质质上上定定理理1.6的的另另一一种种说说法法。由由于于每每盒盒的的球球数数不不受受限限制制，相相当当于于重重集集*a1,*a2,*an的的r组合。组合。解解：(x+y+z)4展展开开式式每每一一项项都都是是4次次方方的的，相相当当于于从从3个个不不同同元元素素中中可可以以重重复复的的选选择择4个个，或或者者相相当当于于将将4个个无无区区别别的的球球放到放到3个有标志的盒子里。故展开项个数为个有标志的盒子里。故展开项个数为 F(3,4)=C(3+4-1,4)=15本讲稿第五十三页，共一百零三页1.3 重复组合例8、91.3.2 重复组合重复组合例例8、某某餐餐厅厅有有7种

50、种不不同同的的菜菜，为为了了招招待待朋朋友友，一个顾客需要买一个顾客需要买14个菜，问有多少种买法？个菜，问有多少种买法？例例9、求求n个个无无区区别别的的球球放放入入r个个有有标标志志的的盒盒子子里里(nr)而无一空盒的方案数。而无一空盒的方案数。解解：这这 个个 问问 题题 相相 当当 于于 重重 集集*1,*2,*7的的14组组合合。根根据定理据定理1.6知买菜的方法数为知买菜的方法数为F(7,14)=C(7+14-1,14)=4845解解：由由于于每每个个盒盒子子不不能能为为空空，故故每每个个盒盒子子里里可可先先放放一一个个球球，这这样样还还剩剩n-r个个球球，再再将将这这n-r个个球