《组合数学引论》求取 ⇩

绪论1

第1章 鸽巢原理7

1．1 鸽巢原理的简单形式7

1．2 鸽巢原理的加强形式10

1．3 Ramsey问题与Ramsey数16

1．3．1 Ramsey问题16

1．3．2 Ramsey数19

1．4 Ramsey数的推广21

习题24

2．1 加法原则与乘法原则28

2．1．1 加法原则28

第2章 基本计数问题28

2．1．2 乘法原则30

2．2 排列与组合31

2．2．1 集合的排列31

2．2．2 集合的组合36

2．3 多重集合的排列与组合42

2．3．1 多重集合的排列42

2．3．2 多重集合的组合46

2．4 二项式系数51

2．4．1 二项式定理51

2．4．2 二项式系数的基本性质53

2．4．3 组合恒等式59

2．4．4 多项式定理63

2．5 集合的分划与第二类Stirling数65

2．6 正整数的分拆71

2．6．1 有序分拆72

2．6．2 无序分拆74

2．6．3 分拆的Ferrers图77

2．7 分配问题82

习题89

第3章 容斥原理95

3．1 引论95

3．2 容斥原理97

3．3 容斥原理的应用108

3．3．1 具有有限重复数的多重集合的γ组合数108

3．3．2 错排问题110

3．3．3 有禁止模式的排列问题113

3．3．4 实际依赖于所有变量的函数个数的确定119

3．4 Mobius反演及可重复的圆排列121

习题126

第4章 递推关系129

4．1 递推关系的建立129

4．2 常系数线性齐次递推关系的求解133

4．3 常系数线性非齐次递推关系的求解142

4．4 用迭代归纳法求解递推关系146

4．5 Fibonacci数和Catalan数153

4．5．1 Fibonacci数153

4．5．2 Catalan数158

习题164

5．1 引论168

第5章 生成函数168

5．2 形式幂级数170

5．3 生成函数的性质176

5．4 用生成函数求解递推关系183

5．4．1 用生成函数求解常系数线性齐次递推关系184

5．4．2 用生成函数求解常系数线性非齐次递推关系188

5．5 生成函数在计数问题中的应用193

5．5．1 组合数的生成函数193

5．5．2 排列数的指数型生成函数197

5．5．3 分拆数的生成函数201

5．5．4 组合型分配问题的生成函数204

5．5．5 排列型分配问题的生成函数205

5．6 有限制位置的排列及棋子多项式206

习题214

第6章 Polya计数理论218

6．1 引论218

6．2 置换群的基本知识219

6．2．1 群和子群219

6．2．2 置换群220

6．3 计数问题的数学模型225

6．4 Burnside引理227

6．4．1 共轭类227

6．4．2 k不动置换类230

6．4．3 等价类231

6．4．4 Burnside引理233

6．5 映射的等价类236

6．6 Polya计数定理239

习题252

第7章 相异代表系254

7．1 引论254

7．2 相异代表系255

7．3 棋盘覆盖问题259

7．4 二分图的匹配问题262

7．5 一个算法264

习题271

第8章 组合设计274

8．1 两个古老问题274

8．1．1 36名军官问题274

8．1．2 女生问题276

8．2．1 几个基本术语278

8．2 平衡不完全区组设计278

8．2．2 关联矩阵及其性质279

8．2．3 三连系288

8．3 几何设计291

8．3．1 有限射影平面291

8．3．2 平面设计297

8．3．3 仿射平面303

8．4 正交拉丁方308

8．4．1 拉丁方及正交拉丁方308

8．4．2 用有限域构造正交拉丁方完备组311

8．5 Hadamard矩阵319

8．6 用有限域构造Hadamard矩阵324

习题328