组合数学选讲.ppt

*****1元2元5元10元20元50元100元*****1元2元5元10元20元50元100元*****1元2元5元10元20元50元100元*选择5张纸币的方法数对应于安排6条竖线和5颗星的方法数，因此选择5张纸币的方法数就是从11个可能的位置选5颗星位置的方法数。这对应于含11个物体的集合中无序地选择5个物体的方法数，可以有种方式。定理：n个元素集合中允许重复的的r-组合有个。*四、生成函数无穷实数序列a0,a1,…,ak,…的生成函数是无穷级数：G(x)=a0+a1x1+a2x2+…+akxk+…=aixi由定义可知，一个序列和它的生成函数是一一对应的。给定了一个序列就可以得到这个序列的生成函数。反之，如果给定了生成函数，则序列也随之而定。由此可知，生成函数实质上就是序列的另一种表达形式。*五、鸽巢原理1.一般的鸽巢原理鸽巢原理又称抽屉原理，它是组合数学中的一个重要的也是最基本的原理。这个原理是指：有n只鸽子，飞进m(nm)个鸽巢时，至少有一个鸽巢内有两只或两只以上的鸽子。这是个显而易见的道理，然而，它却有许多重要而有趣的应用和不同的表达形式，这里先介绍鸽巢原理的简单表达形式。*定理：如果把n+1个或更多的物体被放入到n个盒子里，则至少有一个盒子包含了两个或更多的物体。*2.推广的鸽巢原理鸽巢原理指出当物体比盒子多时，一定至少有两个物体在同一个盒子里。但是当物体数超过盒子数的倍数时可以叙述更多的结果。例如，有21只鸽子，只有10个鸽巢，则至少有一个鸽巢中住着3只鸽子。*定理：把多于mn(m乘以n)个的物体放到n个盒子里，则至少有一个盒子里有不少于m+1的物体。例：在100个人中至少有多少人生日在同一个月？*组合数学*组合数学是一个古老而又年轻的数学分支。传说，大禹在4000多年前就观察到神龟背上的幻方…...幻方可以看作是一个3阶方阵，其元素是1到9的正整数，每行、每列以及两条对角线的和都是15。519372486*贾宪北宋数学家（约11世纪）著有《黄帝九章细草》、《算法斅古集》斅音“笑（“古算法导引”）都已失传。杨辉著《详解九章算法》（1261年）中曾引贾宪的“开方作法本源”图（即指数为正整数的二项式展开系数表，现称“杨辉三角形”）和“增乘开方法”（求高次幂的正根法）。前者比帕斯卡三角形早600年，后者比霍纳（WilliamGeogeHorner，1786—1837）的方法（1819年）早770年。*1666年莱布尼兹所著《组合学论文》一书问世，这是组合数学的第一部专著。书中首次使用了组合论（Combinatorics）一词。组合数学的蓬勃发展则是在计算机问世和普遍应用之后。由于组合数学涉及面广，内容庞杂，并且仍在很快地发展着，因而还没有一个统一而有效的理论体系。*组合数学的研究内容*1．存在性：有没有满足条件的安排？2．计数：满足条件的安排有多少种？3．构造：给出满足条件的安排的具体构造。4．优化：在众多满足要求的安排中，按一定的标准挑出最优的安排。组合数学主要研究一组离散对象满足一定条件的安排，讨论的内容大致有四方面：一、计数基本计数关系式集合的运算，可用于有限个元素的计数问题。记|A|为A所含元素的个数，设A1和A2是有限集合，根据集合运算的定义，有以下关系式成立。*A1A2E*2.相容排斥原理设A1和A2是有限集合，其元素个数分别为|A1|和|A2|，则|A1∪A2|=|A1|+|A2|-|A1∩A2|*例1：一个班级有50名学生，有16人第一次考试优秀，有11人第二次考试优