四川师范大学研究生组合数学课件-教案.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是所有这些奖品的集合，Si是第i类奖品的集合(i=1,2,3)，显然，Si∩Sj=Φ (i≠j) ，根据加法法则有,§1.1 加法法则例2、3,§1.1 加法法则和乘法法则,1.1.1 加法法则,例 题,例2、大于0小于10的奇偶数有多少个？,例3、小于20可被2或3整除的自然数有多少个？,解：设S是符合条件数的集合，S1、S2分别是符合条件的奇数、偶数集合，显然，S1∩S2=Φ ，根据加法法则有,若|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是所求的道路数集合，S1、S2、S3分别是从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={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.1,1.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.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−排列，因而所求的四位数个数为,§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!2]4×2×P(7,3)，满足题目要求的5位数个数为,§1.2 圆排列,§1.2 排列,定义 1.2,1.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.3,1.2.3 重排列。