《组合数学》求取 ⇩

第一章 Ramsey定理1

1.1 鸽笼原理1

1.2 鸽笼原理的加强形式3

1.3 Ramsey定理6

Ⅰ 完全图Kn的染色6

Ⅱ Ramsey定理8

Ⅲ Ramsey数11

Ⅳ Ramsey定理的一些应用13

习题一16

第二章 排列、组合和二项式定理17

2.1 排列17

Ⅰ 集合17

Ⅱ 排列19

2.2 组合24

2.3 二项式定理31

Ⅰ 二项式定理31

Ⅱ 二项式系数34

Ⅲ 恒等式36

Ⅳ 杨辉矩阵41

习题二44

第三章 划分与Stirling数47

3.1 正整数的划分47

Ⅰ 有序划分48

Ⅱ 划分数49

Ⅲ Ferrers示图50

3.2 集合的划分和第二类Sirtling数55

Ⅰ 集合的划分和第二类Stirling数55

Ⅱ Bell数59

3.3 第一类Stirling数60

Ⅰ 第一类Stirling数60

Ⅱ 两类Stirling数的关系62

3.4 分配问题64

Ⅰ 12态64

Ⅱ 其它类型的例66

习题三68

第四章 生成函数70

4.1 引论70

Ⅰ 定义及例子70

Ⅱ 形式幂级数的运算71

4.2 组合个数的生成函数78

Ⅰ 组合个数的生成函数78

Ⅱ 分配模式83

Ⅲ 不定方程的整数解个数的生成函数84

4.3 指数型生成函数87

Ⅰ 指数型生成函数87

Ⅱ 排列个数的指数型生成函数89

Ⅲ Stirling数的生成函数91

4.4 划分数的生成函数96

Ⅰ 正整数的划分数的生成函数96

Ⅱ Euler恒等式99

Ⅲ p（n）的估值104

习题四106

第五章 递推关系109

5.1 递推关系的例子109

5.2 常系数线性齐次递推关系的求解113

5.3 常系数线性非齐次递推关系的求解120

5.4 用生成函数来求解递推关系122

5.5 Fibonacci数124

5.6 差分127

Ⅰ 差分简介127

Ⅱ 幂和问题130

Ⅲ 差分与递推132

习题五133

第六章 容斥原理和反演公式135

6.1 容斥原理的基本公式135

6.2 容斥原理的应用140

Ⅰ Euler-？函数的计算公式140

Ⅱ 更列数141

Ⅲ 有限制条件的排列数143

Ⅳ 夫妻数145

Ⅴ 有禁区的排列数146

6.3 经典M？bius反演公式及应用152

Ⅰ 数列的Dirichlet卷积152

Ⅱ 经典M？bius反演公式154

Ⅲ 环状字的计数156

6.4 局部有限偏序集上的M？bius反演公式158

Ⅰ 偏序集及局部有限偏序集上的关联代数158

Ⅱ M？bius反演公式165

Ⅲ M？bius函数的计算168

习题六171

第七章 Polya定理174

7.1 置换的轮换174

Ⅰ 群174

Ⅱ 置换的轮换175

7.2 Burnside引理179

Ⅰ 轨道179

Ⅱ Burnside引理181

7.3 Polya定理184

7.4 带权的Polya定理189

习题七196

第八章 相异代表系197

8.1 相异代表系197

Ⅰ P.Hall定理197

Ⅱ 分划的公共代表系199

8.2 关联矩阵202

Ⅰ 积和式202

Ⅱ 关联矩阵203

8.3 拉丁长方206

Ⅰ 拉丁长方与拉丁方206

Ⅱ 拉丁长方的扩充207

8.4 线秩、项秩与最大零矩209

习题八215

附表1 阶乘及其素因子分解217

附表2 二项式系数？218

附表3 n的k部划分数p（n,k）219

附表4 n的划分数p（n）220

附表5 第一类Stirling数s（n,k）221

附表6 第二类Stirling数S（n,k）222

参考文献223

索引225