组合数学复习要点

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,复习要点,一、排列组合,1.排列和组合的基本性质,2.基本的组合等式及其证明，用组合意义法证明,组合等式,3.排列组合的计数公式，多重集的排列数和组合,数的求法,4.多项式系数及其求法,5.,应用,二、母函数,1.母函数与数列的关系,2.,母函数的基本性质,3.,母函数与排列数、组合数的关系,4.,用母函数解决多重集的排列和组合问题,5.,正整数的分拆的应用,6.,正整数的分拆数、不定方程的（正、非负）整,数解的个数、多重集的组合数之关系,三、递推关系,1.常系数线性递推关系的解法（特征根法）,2.用待定系数法求常系数线性非齐次递推关系的,特解,(,三种类型,),3.,一般递推关系的线性化,4.Fibonacci,数列及其模型,5.Stirling,数列的组合意义,6.,根据具体问题建立递推关系并求解,四、容斥原理,1.容斥原理的基本形式（容斥原理、逐步淘汰原,理）,2.容斥原理的应用（比如在排列组合、初等数论,等方面）,3.有限制条件的排列（比如错排问题、相邻禁位,排列问题、保位问题）,4.有禁区的排列,五、抽屉原理和,Ramsey,问题,1.抽屉原理的几种基本形式,2.抽屉原理的应用,3.完全图的染色问题,4.,Ramsey,问题基本概念,5.,几个基本的,Ramsey,数,六、波利亚,(Plya),定理,1.置换在研究等价类计数中的作用,2.将置换表为轮换之积,3.Burnside,引理计数公式,4.Plya,定理计数公式,5.,Plya,定理的应用,例,6,从,n,双不同的鞋中取出,2,r,(2,r,n,),只鞋,使得其中恰有,k,(,k,r,),双成对的鞋,.,问有多少种不同的取法？（,鞋分左右,）,例,7,某学者每周工作,6,天,共,42,小时,每天工作的小时数是整数,且每天工作时间不少于,6,小时也不多于,8,小时,如果编排一周的工作时间表,问有多少种不同的方案？,例,9,确定所有的奇数数字组成的,n,位数的个数,其中,1,和,3,每个都出现非零偶数次,.,