组合数学讲义(10版).doc

PAGE PAGE PAGE I p12 例9（填空） p17 2.生成组合，递归调用算法 p19 定理2（填空） p20 例3（填空） p22 性质2 解释组合意义 p25 （4）解释组合意义 p28 例5（填空） p29 （3） 空盒放法( )种 p32 定理1： 第二类stirling （证明） p34 例1 （填空）列式 p36 定理2(3)(填空或大题)证明 p44 例5 列出式子即可 p49 4.2.5 定理（填空） p51 例4 求解问题 p56 例2 写出递归关系式（改题目） p64 catalan写前几项 {1,1,2,5,14,42}（填空） p75 定理1 （填空）如例1 p80 例2 （证明） 通过定理求解：一个矩形染色 p86 例如：构建3阶完全的正交拉丁方簇 目 录 TOC \o 1-3 \h \z \u 第1章 绪 论 1 1.1 组合数学的起源 1 1.2 组合数学的研究内容 3 1.3 组合数学的应用 5 实验项目——构造幻方 5 第2章 排列与组合 7 2.1 加法原理与乘法原理 7 2.1.1 加法原理 7 2.1.2 乘法原理 8 2.1.3 应用举例 8 2.2 排列与组合 10 2.2.1 集合的排列 10 2.2.2 集合的组合 12 2.2.3 排列和组合的模型 13 2.3 排列与组合的生成算法 14 2.3.1 生成排列的算法 14 2.3.2 生成组合的算法 16 2.4 多重集合的排列与组合 17 2.4.1 多重集合的排列 17 2.4.2 多重集合的组合 18 2.4.3 排列和组合的模型 20 第3章二项式定理与多项式定理 21 3.1 二项式定理 21 3.1.1 二项式定理及其证明 21 3.1.2 二项式系数的基本性质 22 3.1.3 组合恒等式 24 3.2 多项式定理 27 3.3 Stirling数（司特林数） 29 3.4 集合的分划 31 3.4.1 集合分划的定义 31 3.4.2 第2类stirling数的性质 32 3.5 正整数的分拆 34 3.5.1 有序分拆 34 3.5.2 无序分拆 35 3.5.3 分拆的Ferrers图（费若斯图） 37 3.6 综合应用——球盒分配问题 39 第4章 容斥原理与鸽笼原理 41 4.1 容斥原理 41 4.1.1 间接计数法 41 4.1.2 容斥原理的三种形式 43 4.2 容斥原理的应用 46 4.2.1 有限重集合的r组合 46 4.2.2 有禁止位置的错排问题 46 4.2.3 有禁止模式的错排问题 47 4.2.4 不相邻的排列 48 4.2.5 不相邻的组合 49 4.3 鸽笼原理 49 4.4 Ramsey问题与Ramsey数 52 4.4.1 Ramsey问题 52 4.4.2 Ramsey数 53 第5章 递推关系与母函数 55 5.1 递推关系 55 5.2 母函数 57 5.2.1 母函数的定义 57 5.2.3 利用母函数求解递归关系式 57 5.2.2 母函数的性质 59 5.3 Fibonacci序列 60 5.3.1 Fibonacci序列 60 5.3.2 Fibonacci数的性质 62 5.4 Catalan序列 63 第6章 Polya计数理论 69 6.1 群 69 6.1.1 群 69 6.1.2 群的基本性质 70 6.1.3 子群、循环群、交换群 71 6.2 置换群 71 6.2.1 置换群的定义 72 6.2.2 置换的轮换之积表示 74 6.3 Burnside 引理 77 6.3.1 共轭类 77 6.3.2 k不动置换类 78 6.3.3 等价类 79 6.3.4 Burnside引理 80 6.4 Polya定理 81 6.4.1 Polya定理的一般形式 81 6.4.2 母函数型的Polya定理 82 第7章 组合设计 84 7.1 拉丁方与正交拉丁方 84 7.1.1 拉丁方