ACM-ICPC程序设计系列 组合数学及应用PDF电子书下载

第1章 排列组合 1

1.1排列与组合 1

1.2两个基本计数原理 3

1.2.1加法原理 3

1.2.2乘法原理 5

1.3特殊排列组合 7

1.3.1重复排列 7

1.3.2重复组合 7

1.3.3不全相异的全排列 8

1.3.4圆周排列 8

1.4排列的生成算法 9

1.4.1序数法 10

1.4.2字典序法 13

1.4.3邻位互换法 14

1.5组合的生成 16

1.6练习题 17

第2章 母函数 21

2.1普通母函数 21

2.2整数的拆分 26

2.3 Ferrers图像 29

2.4指数型母函数 30

2.5递推关系 31

2.6斐波那契数列 35

2.7 Stirling数 41

2.8 Catalan数 42

2.9练习题 46

第3章 容斥原理与鸽巢原理 48

3.1容斥原理 48

3.1.1 De Morgan定理 48

3.1.2容斥原理的定义 49

3.2容斥原理的应用 53

3.2.1错排问题 53

3.2.2棋盘多项式与有禁区的排列 57

3.3 Mobius反演定理 64

3.4鸽巢原理 66

3.5 Ramsey数 71

3.5.1 Ramsey问题 71

3.5.2 Ramsey数 72

3.6应用实例 74

3.7练习题 81

第4章 群和Polya定理 86

4.1等价关系、群与置换群 86

4.1.1等价关系 86

4.1.2群和置换群 87

4.2循环与对换 89

4.3 Burnside引理 91

4.3.1共轭类 91

4.3.2 k不动置换类和等价类 92

4.3.3 Burnside引理 93

4.4 Polya定理 95

4.5 Polya定理应用举例 96

4.6练习题 101

第5章 组合计数与编码 103

5.1均衡不完全区组设计 103

5.1.1均衡不完全区组设计 104

5.1.2基本性质 105

5.1.3由对称BIBD构造BIBD 105

5.2拉丁方 106

5.2.1拉丁方的定义 106

5.2.2拉丁方的构造 107

5.2.3正交拉丁方 108

5.3 Hadamard矩阵 110

5.3.1 Hadamard矩阵 110

5.3.2由Hadamard矩阵构造SBIBD（4t-1，2t-1，t-1） 111

5.4编码理论基础 111

5.4.1基本概念 111

5.4.2 Hamming码 112

5.5应用实例 113

5.6练习题 126

第6章 线性规划 130

6.1线性规划问题及其表示 130

6.1.1线性规划问题 130

6.1.2线性规划问题的一般形式 131

6.1.3线性规划问题的标准形式 132

6.1.4一般形式向标准形式的转化 133

6.2单纯性算法 134

6.2.1松弛变量技术 134

6.2.2线性规划定理 135

6.2.3单纯性算法 136

6.2.4特殊情况的处理 140

6.2.5算法流程 141

6.2.6算法实现 142

6.3练习题 146

附录：参考程序 148

参考文献 199