第18讲+组合数学【范端喜】.docx

1.p12 例9（填空）2.p17 2.生成组合，递归调用算法3.p19 定理2（填空）4.p20 例3（填空）5.p22 性质2 解释组合意义6.p25 （4）解释组合意义7.p28 例5（填空）8.p29 （3）空盒放法( )种9.p32 定理1：第二类stirling （证明）10.p34 例1 （填空）列式11.p36 定理2(3)(填空或大题)证明12.p44 例5 列出式子即可13.p49 4.2.5 定理（填空）14.p51 例4 求解问题15.p56 例2 写出递归关系式（改题目）16.p64 catalan写前几项{1,1,2,5,14,42}（填空）17.p75 定理1 （填空）如例118.p80 例2 （证明）通过定理求解：一个矩形染色19.p86 例如：构建3阶完全的正交拉丁方簇目录第1章绪论 (1)1.1 组合数学的起源 (1)1.2 组合数学的研究内容 (3)1.3 组合数学的应用 (5)实验项目——构造幻方 (5)第2章排列与组合 (7)2.1 加法原理与乘法原理 (7)2.1.1 加法原理 (7)2.1.2 乘法原理 (8)2.1.3 应用举例 (8)2.2 排列与组合 (10)2.2.1 集合的排列 (10)2.2.2 集合的组合 (12)2.2.3 排列和组合的模型 (13)2.3 排列与组合的生成算法 (14)2.3.1 生成排列的算法 (14)2.3.2 生成组合的算法 (16)2.4 多重集合的排列与组合 (17)2.4.1 多重集合的排列 (17)2.4.2 多重集合的组合 (18)2.4.3 排列和组合的模型 (20)第3章二项 (21)3.1 二项式定理 (21)3.1.1 二项式定理及其证明 (21)3.1.2 二项式系数的基本性质 (22)3.1.3 组合恒等式 (24)3.2 多项式定理 (27)3.3 Stirling数（司特林数） (29)3.4 集合的分划 (31)3.4.1 集合分划的定义 (31)3.4.2 第2类stirling数的性质 (32)3.5 正整数的分拆 (34)3.5.1 有序分拆 (34)3.5.2 无序分拆 (35)3.5.3 分拆的Ferrers图（费若斯图） (37)3.6 综合应用——球盒分配问题 (39)第4章容斥原理与鸽笼原理 (41)4.1 容斥原理 (41)4.1.1 间接计数法 (41)4.1.2 容斥原理的三种形式 (43)4.2 容斥原理的应用 (46)4.2.1 有限重集合的r组合 (46)4.2.2 有禁止位置的错排问题 (46)4.2.3 有禁止模式的错排问题 (47)4.2.4 不相邻的排列 (48)4.2.5 不相邻的组合 (49)4.3 鸽笼原理 (49)4.4 Ramsey问题与Ramsey数 (52)4.4.1 Ramsey问题 (52)4.4.2 Ramsey数 (53)第5章递推关系与母函数 (55)5.1 递推关系 (55)5.2 母函数 (57)5.2.1 母函数的定义 (57)5.2.3 利用母函数求解递归关系式 (57)5.2.2 母函数的性质 (59)5.3 Fibonacci序列 (60)5.3.1 Fibonacci序列 (60)5.3.2 Fibonacci数的性质 (62)5.4 Catalan序列 (63)第6章Polya计数理论 (69)6.1 群 (69)6.1.1 群 (69)6.1.2 群的基本性质 (70)6.1.3 子群、循环群、交换群 (71)6.2 置换群 (71)6.2.1 置换群的定义 (72)6.2.2 置换的轮换之积表示 (74)6.3 Burnside 引理 (77)6.3.1 共轭类 (77)6.3.2 k不动置换类 (78)6.3.3 等价类 (79)6.3.4 Burnside引理 (80)6.4 Polya定理 (81)6.4.1 Polya定理的一般形式 (81)6.4.2 母函数型的Polya定理 (82)第7章组合设计 (84)7.1 拉丁方与正交拉丁方 (84)7.1.1 拉丁方 (84)7.1.2 正交拉丁方 (84)7.1.3 正交拉丁方的性质 (85)7.2 正交拉丁方的构造 (85)7.2.1 域的概念 (85)7.2.2 用有限域构造完全的正交拉丁方族 (86)7.2.3 由低阶的正交拉丁方构造高阶的正交拉丁方 (87)7.3 正交拉丁方的应用举例 (88)7.4 平衡不完全区组设计 (89)7.4.1 平衡不完全区组设计的定义 (89)7.4.2 Steiner三元系（斯梯纳三连系） (90)组合数学讲义第1章绪论第1章绪论组合数学是一个历史悠久的数学分支，可追溯到远古时代，18世纪，组合数学得到较深入的研究，20世纪，计算机的诞生使组合数学得以蓬勃发展。

组合(2)【教材】10.3组合【目的】1.掌握组合数的两个性质,并能运用它解决一些简单的应用问题.2.初步掌握“一一对应”与“归纳”的思想.3.进一步训练用组合数公式及分类(步)计数原理解决实际问题.【过程】：一、复习引入1.复习:(1)组合数的计算公式的两种表示怎样?有何用途?(2)用组合数公式计算?310=C ,?710=C 它们有何关系?(相等)2.引入:这种相等并非偶然,它正是本节课我们要学习的组合数的性质之一.二、新课1.组合数的性质一(1)提出问题:为什么710310C C =或71010710==C C 呢?46646-=C C 吗? 将其推广到m n nm n C C -=呢? (2)解决问题:引导学生分三个层次解决.a.用“取法”与“剩法”和组合的概念解释:从10个元素中取出7个元素后,还剩下3个元素.就是说,从10个元素中每次取出7个元素的一个组合,与剩下的(10-7)个元素的组合是一一对应的,因此,71010710==C C .(可再举几个例子) b.推广到一般:一般地,从n 个不同元素中取出m 个元素后,剩下(n-m)个元素.因此,从n 个不同元素中取出m 个元素的每一个组合,与剩下的(n-m)个元素的每一个组合一一对应,故m n nm n C C -= c.用组合数公式证明:(见教材)(3)几点说明:a.这时组合数的性质一,当2n m >时,用m n nm n C C -=,可将组合数计算大大简化. b.为了使公式在n m =时也成立,规定10=n C . c.公式特征:两边下标同,上标之和等于下标.2.组合数的性质二(1)提出问题:见教材101页例4.分析:本题是一个典型的抽球问题.口袋内7个白球虽然大小相同,但它们仍是不同的元素,为了便于理解可以看成它们编上了号码:白1,白2,…白7,从而让学生理解(1)即是从8个不同元素中每次取出3个的组合,取法为38C 种.对于(2)可启发学生:取出的3个球中含有1个黑球,则只考虑在7个白球中取2个,因而有27C 种取法.对于(3)可让学生分析得出.启发:三个问题结果有何关系呢?38C =37C +27C ,你能对此作出合理解释吗?(2)解决问题:引导学生分三个层次解决.a.用组合数定义解释:38C =37C +27C ,即从口袋内的8个球中所取出的3个球,可以分成两类:一类含1个黑球,一类不含黑球.故根据分类计数原理,等式成立.b.推广到一般:一般地,从1a ,2a ,…1+n a 这1+n 个不同的元素中取出m 个的组合数是m n C 1+,这些组合可分成两类:一类含1a ,一类不含1a ,含有1a 的组合是从2a ,3a ,…1+n a 这n 个元素中取出(1-m )个元素与1a 组成的,共有1-m n C 个, 不含1a 是从2a ,3a ,…1+n a 这n 个元素中取出m个元素组成的,共有m n C 个,由分类计数原理得: m n C 1+=m n C +1-m nC . c.用组合数公式证明:(见教材)(3)几点说明:a.这是组合数的第二个性质,在下节“二项式定理”中,将会看到它的重要应用.b.此公式在计算、证明的过程中,同样能简化运算.c.公式特征:下标相同,而上标差1的两个组合数之和等于下标比原下标多1上标与高的相同的一个组合数.d.此公式的引入过程,用到了“分类”的思想,“分类”是处理排列组合问题的重要方法.3.例题:例1、计算 (1) 198200C (2)69584737C C C C +++ ( 210 ) (3) 21025242322C C C C C +++++ 例2、求证 2122--+++=n m n m n m n m C C C C例3、解方程 x x C C 217217=+ 例4、求x x x x C C 321383+-+的值. (先求出10=x ,代入的所求值为466)4.练习:教材第103页练习1、2、3三、小结:1.组合数的性质:(1) m n n m n C C -= (2) m n C 1+=m n C +1-m nC2.应用组合数的性质时,要点是当2n m >时,可由m n n m n C C -=简化运算;性质二可正用,即裂项,也可逆用,即并项.3.三个思想:“取法”与“剩法”一一对应的思想,特殊到一般的归纳思想,“含与不含其元素”的分类思想.四、作业:教材第104页 习题第2、4题.。

组合数学――离散数学中一个古老而前沿的话题海南华侨中学李红庆组合数学与现实生活是形影不离的，在生活中随时可见．例如，你是校学生会体育部长，学校高二年级有１２个班级，要由１６名高二学生组成的校足球队，为了平衡各班情况，每班至少有１名学生参加，就要计算足球队员名额分配的方案的种数．创建幻方：在纸上画一个２×２×２网络图（见右下图），用铅笔沿着网络的线路走，从A到B最短的线路有多少种？其中经过MN的概率是多少？再如在玩扑克游戏中，计算任意取3张牌，恰好是黑桃A，K，Q的概率．所有这些问题都是组合数学问题．组合数学是离散数学中一个古老而前沿的课题．组合数学的问题背景渊源于数学娱乐和游戏之中．它是数学的一门重要分支，而且由于信息技术的发展，计算机给现实生活带来了日趋深远的影响．组合数学的应用越来越具有重要性和广泛性，组合数学自上世纪６０年代以来迅速发展．现在普通高中新课程标准对组合数学引起了足够的重视，组合问题在离散数学中处于承前启后的作用，它既是递推数列、古典概型、排列知识的延伸，又是二项式定理、离散型随机变量的概率分布列知识的奠基内容，是离散数学中一个重要的组成部分，它研究的主要内容——其一是一组离散对象满足一定条件的排列的存在性；其二是如果一组离散对象满足一定条件的排列是可能的，那么会存在多种方法去实现它．此时，人们可以对排列进行构造，用枚举来计数，而在这些环节的操作中，需要通过优化进行分类．为了使大家对组合数学有一些更具体的了解，现在我们回归到组合问题的具体实例上．例1 如图，4横×3纵×3竖的网络图，蚂蚁选择最短路线从A沿着网络线爬到B的不同的方法有多少种？如果线段CD断开，那么蚂蚁从A沿着网络线爬到B的不同的方法又有多少种？问题分析：组合数学经常使用的方法并不高深复杂．最主要的方法是计数时的合理分类和组合模型的转换．但是，要学好组合数学并非易事，既需要一定的数学修养，也要一定理性而创新的思辩能力，才能找到合适的转化模型．例1中问题可以转化到给7个方格填有序的3类数值．解：横轴x 方向的线段编号：1，2，3；纵y 轴方向的线段a ，b ；竖轴z 轴方向的线段编号：一，二．（1）所以蚂蚁从A 沿着网络线爬到B 的不同的方法是从7个方框中选出3个来按顺序填上1，2，3；再从余下的4个方框中选出2个来按顺序填上a ，b ；最后剩下的2个方框由一，二按顺序填上．即322742210C C C ⨯⨯=种；（2）先计算蚂蚁经过CD 的不同的爬法，将数字“二”填入第5个方框中，前面4个方框分别由a ，1，2，一填入，后面2个方框由b ，3填入，见图解121242C C C ⨯二，等于()211422()24C C C ⨯⨯=，那么线段CD 断开，那么蚂蚁从A 沿着网络线爬到B 的不同的方法是21024186-=种．过一把瘾：1．如图，一宗待通关的大型商品共12件，由三条并排的通道依次通关检验（每条4件），每检验一件后由关长亲自复验放行．若A 件恰好是放行的第5件，B 件恰好是放行的第6件，求这12件商品全部被放行的情形有多少种？例2 某城市在中心广场建造一个花圃，花圃分为6个部分（如下图），现要栽种4种不同颜色，每部分栽种一种，且相邻部分不能栽种同种颜色的花，不同的栽种方法有多少种？ 问题分析 显然区域1与其他5个区域的颜色不同，那么可以种同一种颜色的可能有52，53，63，64，42．由于只有四种颜色的花，那么每情形中都有两个的2个区域栽同一种颜色．解：所有组合有：56,,1,423；56,,3,124；56,,2,134；54,,6,132；46,,5,123共有5种情形，每种有4424A =种排列，那么不同的栽种方法有445120A ⨯=种．过一把瘾：2．用四种颜色对下列各图的A ，B ，C ，D，E五个区域染色，要求相邻的区域染不同的颜色．问各有多少种不同的染色方法？例3 某城市规划沿着该城市的中山大道修建10个主题公园，由于一时资金不能全部到位，3个主题公园暂缓修建，两头的主题公园不在暂缓之列，相邻的两个主题公园不能同时列入暂缓之列，那么暂缓修建的方案共有多少种？问题分析：组合问题难点在分类与模型的选择上，本题用直接的方法去解，涉及的问题还是比较复杂的，经过分析可以考虑问题的相对面，暂缓3个公园的修建应该等价于原来有7个主题公园，现在新增加3个主题公园的问题，那么它的模型应该是“插入法”的模型，即7个并排的公园之间的6个空隙中插入3个，见示意图．解：本题等价于在原来7个主题公园的基础上新增加3个主题公园，要求新增加的公园不能加在两端，原来的两个主题公园之间不能同时新增加2个，那么就是在7个并排的小五角星之间的6个空隙中插入3个，即3620C =种不同的方案．过一把瘾：3．方程16x y z w u v +++++=正整数解的组数是多少？附：过一把瘾答案1．给3条通道的商品分别用不同的数序编号：1，2，3，4；a ，b ，c ，d ；Ⅰ，Ⅱ，Ⅲ，Ⅳ．本题实际上是将Ⅲ排在第5个位置，将2排在第6个位置．即213242632C C C C III ⨯⨯，等于()21324263()720C C C C ⨯⨯⨯=种． 2．（a ）由于4种颜色，则组合框图为AB C D E ，或BA D E C 两种，染色的种数是44248A ⨯=种；（b ）组合框图有：EA C DB ，BA C E D ，AB C E D 共三种，染色的种数是44372A ⨯=．3．将用16个小球并成一排，16个小球之间有15个空隙，从其选取5个空隙，每1个插入一块“隔板”，第1块隔板左侧小球的个数是x 的取值，第1块与第2块隔板之间的小球数是y 的取值，…，第5块隔板右侧的小球数是v 的取值，那么16x y z w u v +++++=的正整数解的组数是515C 种．。