组合数学及应用

《组合数学及应用》围绕组合计数问题，将数学原理与实际应用相结合，介绍集合与多集上的排列与组合、二（多）项式定理、二项分布与信息熵、鸽巢原理、拉姆齐理论、生成函数、递归关系（包括斐波那契数、斯特林数、卡特兰数、调和数的递归关系）、容斥原理、伯恩赛德计数定理和波利亚计数定理。《组合数学及应用》共分八章，每一章都配有一个计算机、电子信息、人工智能等领域的应用案例，以展示数学原理或方法在这些专业问题上的应用。此外，每章末附有习题，供读者练习和进一步思考，以巩固和深化理解。《组合数学及应用》围绕组合计数问题，将数学原理与实际应用相结合，介绍集合与多集上的排列与组合、二（多）项式定理、二项分布与信息熵、鸽巢原理、拉姆齐理论、生成函数、递归关系（包括斐波那契数、斯特林数、卡特兰数、调和数的递归关系）、容斥原理、伯恩赛德计数定理和波利亚计数定理。《组合数学及应用》共分八章，每一章都配有一个计算机、电子信息、人工智能等领域的应用案例，以展示数学原理或方法在这些专业问题上的应用。此外，每章末附有习题，供读者练习和进一步思考，以巩固和深化理解。

目录
第1章 排列与组合
1.1 加法原则与乘法原则 1
1.2 集合上的排列 2
1.3 集合上的组合 4
1.4 多集上的排列 6
1.5 多集上的组合 9
1.6 应用：进程互斥建模与死锁分析 10
习题 15
第2章 二项式定理与信息熵
2.1 二项式定理与多项式定理 19
2.2 二项式恒等式 23
2.3 二项分布及其熵 30
2.4 应用：决策树学习 33
习题 38
第3章 鸽巢原理
3.1 鸽巢原理的简单形式 41
3.2 鸽巢原理的一般形式 44
3.3 应用：多索引哈希 46
习题 52
第4章 拉姆齐理论
4.1 双色拉姆齐数 55
4.2 多色拉姆齐数 64
4.3 广义拉姆齐数 67
4.4 应用：香农容量 70
习题 73
第5章 生成函数
5.1 生成函数的定义与运算 75
5.2 一些简单的生成函数 80
5.3 应用：概率分布的期望与方差 83
习题 87
第6章 递归关系
6.1 常系数线性齐次递归关系 89
6.2 基于生成函数求解递归关系 95
6.3 斐波那契数及其递归关系 98
6.4 卡特兰数及其递归关系 100
6.5 斯特林数及其递归关系 103
6.6 调和数及其递归关系 109
6.7 应用：快速排序 110
习题 112
第7章 容斥原理
7.1 容斥原理的简单形式 115
7.2 容斥原理的一般形式 119
7.3 棋子多项式 122
7.4 莫比乌斯反演 132
7.5 应用：非对称旅行商问题 138
习题 143
第8章 伯恩赛德计数定理和波利亚计数定理
8.1 置换群 145
8.2 伯恩赛德计数定理 148
8.3 波利亚计数定理 152
8.4 应用：门电路等价类问题 154
习题 156
参考文献 159
附录符号表 165
索引 167