组合数学课件

组合数学课件课程简介相关课程使用教材《数学分析》《高等代数》《离散数学》书名：组合数学（第三版）作者：孙淑玲出版社：中国科学技术大学出版社本课程针对计算机科学中的一个重要学科——组合数学，组合数学是数学的一个分支，它研究事物在结定模式下的配置，研究这种配置的存在性，所有可能配置的计数和分类以及配置的各种性质。组合数学在计算机科学中有着极其广泛的应用。组合学问题求解方法层出不穷、干变万化，应以理解为基础，善于总结各种技巧，掌握科学的组织和推理方法。目录（1）引言第1章排列与组合1.1加法法则和乘法法则1.2排列1.3组合1.4二项式定理1.5组合恒等式及其含义1.6模型转换本章小结习题第2章鸽笼原理2.1鸽笼原理2.2鸽笼原理的推广2.3Ramsey定理本章小结习题第3章容斥原理3.1容斥原理3.2重集r-组合3.3错排问题3.4有限制排列3.5*一般有限制排列3.6*广义容斥原理本章小结习题第4章母函数4.1母函数的基本概念4.2母函数的基本运算4.3在排列组合中的应用4.4整数的拆分4.5Ferrers图目录目录（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.4Burnside引理6.5Pólya定理6.6Pó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是有限集合，若，且时，，则有。ijijSS1,miiiSSSS11mmiiiiSSS§1.1加法法则例1§1.1加法法则和乘法法则1.1.1加法法则例题例1、有一所学校给一名物理竞赛优胜者发奖，奖品有三类，第一类是三种不同版本的法汉词典；第二类是四种不同类型的物理参考书；第三类是二种不同的奖杯。这位优胜者只能挑选一样奖品。那么，这位优胜者挑选奖品的方法有多少种？解：设S是所有这些奖品的集合，Si是第i类奖品的集合(i=1,2,3)，显然，Si∩Sj=Φ(i≠j)，根据加法法则有iiSSSSS31231||||||||3429§1.1加法法则例2、3§1.1加法法则和乘法法则1.1.1加法法则例题例2、大于0小于10的奇偶数有多少个？例3、小于20可被2或3整除的自然数有多少个？解：设S是符合条件数的集合，S1、S2分别是符合条件的奇数、偶数集合，显然，S1∩S2=Φ，根据加法法则有SSS12||||||549若|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种。集合论定义设是有限集合，且，则有。11mmiiiiSSS1miiSS(1,2,...,)iSim12{(,,...,)|,1,2,...,}miiaaaaSim§1.1乘法法则例4§1.1加法法则和乘法法则1.1.2乘法法则例题例4、从A地到B地有二条不同的道路，从B地到C地有四条不同的道路，而从C地到D地有三条不同的道路。求从A地经B、C两地到达D地的道路数。解：设S是所求的道路数集合，S1、S2、S3分别是从A到B、从B到C、从C到D的道路集合，根据乘法法则有SSSS123||||||||24324§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={k1*b1,k2*b2,…,kn*bn}，其中：bi为n个互不相同的元素，称ki为bi的重数，i=1,2,…,n，n=1,2,…,∞，ki=1,2,…,∞。重集的概念§1.2线排列§1.2排列定义1.11.2.1线排列集合论定义定理1.1从n个不同元素中，取r个(0≤r≤n)按一定顺序排列起来，其排列数P(n,r)。设A={an}，从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)...(1)()!nPnrnnnrnr§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中的某个固定元素，不妨设为a1，另一类不包含a1。第一类排列相当于先从A-{a1}中取r-1个元素进行排列，有P(n-1,r-1)种取法，再将a1放入每一个上述排列中，对任一排列，a1都有r种放法。由乘法法则，第一类排列共有r×P(n-1,r-1)个。第二类排列实质上是A-{a1}的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−排列，因而所求的四位数个数为5!(5,4)120(54)!P§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}的全排列，由乘法法则，排列个数为(8,8)8!40320P(7,7)(2,2)7!2!10080PP§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!2]4×2×P(7,3)，满足题目要求的5位数个数为(9,5)42(7,3)15120168013440PP§1.2圆排列§1.2排列定义1.21.2.2圆排列定理1.2设A={an}，从A中取r个(0≤r≤n)元素按某种顺序（如逆时针）排成一个圆圈，称为圆排列（循环排列）。设A={an}，A的r圆排列个数为P(n,r)/r。证明：由于把一个圆排列旋转所得到另一个圆排列视为相同的圆排列，因此线排列a1a2…ar，a2a3…ara1，…ara1a2…ar-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.31.2.3重排列集合论定义定理1.3从n个不同元素中，可重复选取r个按一定顺序排列起来，称为重排列。从重集B={k1*b1,k2*b2,…,kn*bn}中选取r个按一定顺序排列起来。重集B={∞*b1,∞*b2,…,∞*bn}的r−排列的个数为nr。证明：构造B的r−排列如下：选择第一项时可从n个元素中任选一个，有n种选法