（219）《组合数学》考试大纲

考试内容：

组合数学一般可以分为存在性问题、计数问题、构造性算法、最优性问题四个方面，考试重点是计数方面。要求如下：

1.基本计数问题  两个基本原理（加法、乘法原理），排列、组合方式，可重复的排列、组合方式,排列的生成算法；

2.二项式系数  二项式系数基本性质，二项式定理，主要的二项式系数恒等式及其组合意义，多项式定理；

3.容斥原理  包含—排斥原理，有禁止的排列（包括错排问题），棋盘多项式及其应用；

4.递推关系及其应用  Fibonacci数列，常系数线性递推关系求解；

5.母函数及其应用 整数拆分及其性质，指数型母函数及应用；

6.鸽巢原理与拉姆齐（Ramsey）定理；

7.波利亚（Polya）定理  置换群， Burnside定理，Polya计数定理。

参考书目：

1.《组合数学》（第四版） 卢开澄 编著  清华大学出版社 2006年12月      

2.《组合数学》[美]R.A.Brualdi著 冯舜玺等译 机械工业出版社 2005年2月