包邮组合数学

第1章 绪论 1 1.1 起源 1 1.2 研究内容 2 1.3 求解方法 3 习题1 4 第2章 组合数学基础 5 2.1 两个基本法则 5 2.1.1 加法法则 5 2.1.2 乘法法则 6 2.2 排列与组合 7 2.2.1 相异元素不允许重复的排列数和组合数 7 2.2.2 相异元素允许重复的排列 8 2.2.3 不尽相异元素的全排列 9 2.2.4 相异元素不允许重复的圆排列 10 2.2.5 相异元素允许重复的组合 11 2.2.6 不尽相异元素任取r个的组合问题 12 2.3 组合等式及其组合意义 13 2.4 多项式系数 18 2.4.1 Newton二项式 18 2.4.2 一般分配问题 18 2.4.3 多项式系数 19 2.4.4 多项式展开的项数 20 2.4.5 例题 20 2.5 应用 22 2.5.1 排列组合的应用 22 2.5.2 组合等式在汉明距离与汉明码中的应用 27 习题2 28 第3章 母函数及其应用 31 3.1 母函数 31 3.1.1 母函数的定义 31 3.1.2 组合的母函数 32 3.1.3 母函数的应用 34 3.2 母函数的性质 37 3.3 指数型母函数 40 3.3.1 数列的指母函数 42 3.3.2 排列的指母函数 43 3.3.3 指母函数的特例 44 3.3.4 指母函数的应用 44 3.4 正整数的分拆 46 3.4.1 弗雷斯图 47 3.4.2 有序分拆 48 3.4.3 无序分拆 48 3.4.4 例题 49 3.5 应用 54 3.5.1 母函数在排列组合中的应用 54 3.5.2 母函数在组合恒等式中的应用 56 3.5.3 指母函数在概率生成函数中的应用 58 习题3 60 第4章 递推关系 62 4.1 基本概念 62 4.1.1 递推关系 62 4.1.2 递推关系的分类 62 4.1.3 定解问题 63 4.1.4 例题 63 4.2 常系数线性递推关系 66 4.2.1 解的性质 67 4.2.2 解的结构 67 4.2.3 特征根法 68 4.2.4 非齐次方程 74 4.2.5 一般递推关系化简 79 4.3 解递推关系的其它方法 82 4.3.1 迭代法与归纳法 82 4.3.2 母函数方法 84 4.4 两种典型数列 90 4.4.1 Fibonacci数列 90 4.4.2 Stirling数列 94 4.5 应用 97 习题4 106 第5章 容斥原理 109 5.1 引言 109 5.2 容斥原理 110 5.2.1 容斥原理 110 5.2.2 逐步淘汰原理 111 5.2.3 一般问题 112 5.2.4 对称原理 114 5.3 应用 115 5.3.1 排列组合问题 115 5.3.2 初等数论问题 116 5.3.3 集合的划分 118 5.3.4 其它应用 118 5.4 限制排列与棋盘多项式 123 5.4.1 有限制的排列 123 5.4.2 棋盘多项式 125 5.4.3 有禁区的排列 128 习题5 130 第6章 抽屉原理 132 6.1 抽屉原理 132 6.1.1 基本形式 132 6.1.2 推广形式 133 6.1.3 特例 133 6.1.4 例题 133 6.2 应用 134 6.2.1 抽屉原理的应用 134 6.2.2 极端原理 141 习题6 142 第7章 群论在组合数学中的应用 143 7.1 代数运算 143 7.2 群论基础 144 7.3 单位元、 逆元、 消去律 145 7.4 群的同态 147 7.5 变换群 149 7.6 循环群 152 7.7 子群 153 7.8 不变子群 155 7.9 置换群 156 7.9.1 置换 156 7.9.2 置换的运算 157 7.9.3 置换与空间刚体变换 157 7.9.4 置换群、 轮换 159 7.10 Pólya定理 160 7.11 母函数型的Pólya定理 162 7.12 应用 163 习题7 165 第8章 求解组合优化问题的几种智能算法 167 8.1 求解TSP问题的传统进化算法 167 8.1.1 邻点表示法 167 8.1.2 顺序表示法 168 8.1.3 路径表示法 169 8.1.4 路径的矩阵表示及相应的遗传算子 171 8.1.5 带有局部搜索的解TSP的进化算法框架 176 8.2 求解运输问题的传统进化算法 176 8.3 求解其他离散问题的传统进化方法 180 8.3.1 两种调度问题 180 8.3.2 分组(类)问题 183 8.4 求解TSP问题的一个新的进化算法 185 8.4.1 新的编码方式和相应的解码方式 186 8.4.2 新的遗传算子和局部搜索 187 8.4.3 一个基于新编码方式的新的遗传算法 188 习题8 188 第9章 组合算法 189 9.1 计算的复杂度 189 9.2 归并排序 191 9.2.1 排序算法 191 9.2.2 示例 192 9.2.3 复杂性分析 192 9.3 排序网络 194 9.3.1 0-1原理 194 9.3.2 BN网络 195 9.3.3 复杂性分析 196 9.3.4 Batcher奇偶归并网络 197 9.4 快速傅里叶变换 198 9.4.1 预备定理 198 9.4.2 快速算法 199 9.4.3 复杂性分析 202 9.5 卷积的快速算法 203 9.5.1 卷积及其等价形式 203 9.5.2 复杂度分析 205 9.6 多项式变换及其应用 212 9.6.1 多项式变换的引进 213 9.6.2 一维快速多项式变换 218 9.7 小波变换的Mallat金字塔算法 221 9.8 余弦变换 225 习题9 227 第10章 编码理论 229 10.1 信息传输 229 10.2 编码与解码 229 10.3 错误校正码 231 10.3.1 错误校正和汉明距离 231 10.3.2 汉明界 234 10.3.3 错误的概率 235 10.3.4 合意解码及其与寻找分子序列中的模式之间的关系 236 10.4 线性分组码 240 10.4.1 生成矩阵 240 10.4.2 使用线性码的错误校正 241 10.4.3 汉明码 244 习题10 244 参考文献 248