《组合数学复习要点.ppt》由会员分享，可在线阅读，更多相关《组合数学复习要点.ppt（20页珍藏版）》请在三一文库上搜索。
1、复习要点,一、排列组合,1.排列和组合的基本性质 2.基本的组合等式及其证明，用组合意义法证明 组合等式 3.排列组合的计数公式，多重集的排列数和组合 数的求法 4.多项式系数及其求法 5.,二、母函数,1. 母函数与数列的关系 2. 母函数的基本性质 3. 母函数与排列数、组合数的关系 4. 用母函数解决多重集的排列和组合问题 5. 正整数的分拆的应用 6. 正整数的分拆数、不定方程的（正、非负）整 数解的个数、多重集的组合数之关系,三、递推关系,1.常系数线性递推关系的解法（特征根法） 2.用待定系数法求常系数线性非齐次递推关系的 特解(三种类型) 3.一般递推关系的线性化 4.Fibon
2、acci数列及其模型 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双不同的鞋中取出2r(2r n)只鞋,使得其中恰有k(k r)双成对的鞋.问有多少种不同的取法？（鞋分左右）,例7 某学者每周工作6天,共42小时,每天工作的小时数是整数,且每天工作时间不少于6小时也不多于8小时,如果编排一周的工作时间表,问有多少种不同的方案？,例9 确定所有的奇数数字组成的n位数的个数,其中1和3每个都出现非零偶数次.,