组合数学复习引导学习资料.ppt

容斥原理如果ai看作某个性质，N(ai)为满足该性质的元素数目，N(ai′)是不满足该性质的元素数。N(a1′a2′)＝|A|－∑iN(ai)+N(a1a2)N(a1′a2′a3′)＝|A|－∑iN(ai)+∑N(aiaj)－N(a1a2a3)（其中，ｉ?ｊ）容斥定理如果Ｎ是集合Ａ中的对象的数量，集合Ａ中没有性质a1,a2,…,ar的对象数量由下式给出：容斥原理一题50辆车做废气排放量检测。对污染物NOx，HC，CO等进行测试。其中一辆车上述３气超标，三辆车NOx和HC超标，两车NOx和CO超标，一辆车HC和CO超标；六辆车NOx超标，四辆车HC超标，三辆车CO超标；问：有多少辆车符合环保标准？套套公式看？解：N(a1′a2′a3′)＝42例子题:求由a,b,c,d这4个字符构成的n位符号串中，a,b,c都至少出现一次的符号串的数目题:求a,b,c,d,e,f这6个字母的全排列中不允许出现ace和df图像的排列数。题:N={1,2,…,500},求N中至少能被2,3,5其中之一除尽的数的数目。题:求不超过120的素数的个数棋盘多项式甲乙丙丁4个人住店,有4个房间1,2,3,4,甲不住1,2,3号房间,乙不住2,3,4房间,丙不住1、4号房间,丁不住1,2,4号房间,求满足要求的方案数。*鸽巢原理某次会议有n位代表参加，则至少有两个人认识的人数是一样的；任给5个整数，其中至少有3个数的和被3除尽；设a1,a2,…,am。是正整数的序列，则至少存在整数k和L,1≤k≤L≤m,使得和ak+ak+1+…+aL是m的倍数。3.13.3,A是{1,2,...,2n}中任意n+1个数，试证至少存在一对a,b∈A使得a与b互素。概念和定理群，置换，有限群和置换轮换，对换，循环节数，置换格式，共轭类对称构形着色方案与变换，如田字格相同构形，旋转等刚体变换对图田字形作着色的等价类分析排列群，置换群，置换，置换的轮换表示Ｂｕｒｎｓｉｄｅ：关于等价类数目Ｐｏｌｙａ定理：关于颜色方案的数目作业及例题章4复习引导章四Burnside引理.设G={a1,a2,...,ag},是N={1,2,...,n}上的置换群,G在N上可引出不同的等价类,其不同的等价类的个数为：定理4.12(Polya定理)设是n个对象的一个置换群,用m种颜色涂染这n个对象,则不同染色的方案数为:章四障碍在构建刚体运动的群。概念支撑点例题作业定理记忆相应定理的关注点，符号意义期待你们训练程度与试题难度，思考性题目多一点复习，相信你们自己考试和作业不同，知识必须在脑祝愉快复习，考试成功章节知识比例组合数学复习引导caozhanmao@2013－12*第一章:总框架一一对应的应用比如m用阶乘表示得到一个数组；n2个人排队的可能方案与排成n×n方阵的方案排列、组合的公式典型组合式的证明，利用组合意义证明圆周排列Q(n,r)项链的不同允许重复的组合比如1040与2030的公因子数目不相邻的组合*第二章:总框架母函数在组合中的应用在整数的分拆中的应用指数型母函数在排列中的应用。递推关系*第三章:总框架容斥原理鸽巢原理有禁区的排列*第四章:总框架置换群Burnside引理Polya定理题型题数比例填空题(定义公式)1020基本计算、简答４20应用分析类计算335综合类(存在、证明)225８０％内容训练过的类型。在作业，例题，课堂讲授出现过的类型２０％为思维分析题型，8%为个人突破性或创新测试……题型举例I填空题(涉及：定义公式)组合数学研究的问题主要是三类，即————C(n,m)=P(n,m)=C(n+r－1,r)=(4,2，1，0，…)序列的母函数？对n个无差异球放入m个无差异盒子，无一空盒，方法数为——————基本计算、简答（涉及：公式，原理，计数原理、计数公式、计数方法用于实际应用S(4,2)=s(4,2)=Q(4