组合数学是离散数学的一个分支。专门研究计数的问题。
数学的发展历史
组合数学的三大问题
-
存在性
是否存在合理的解
-
计数
有多少个解
-
优化
哪个解是最优的
历史的组合问题
幻方
存在
一个N*N的方格，是否存在组合
无论每行的和，每列的和，对角线的和都相等？
大约在30年前，已经有数学家证明了任意大约等于3的数n，存下n阶幻方
计数
一个数n，到底存在多少个不同的幻方？
据不完全统计
- 4阶存在7040个
- 5阶存在 2 亿7 千5 百多万个
- 6阶存在数大约 在1.774310×1019 至1.776610×1019 之间
可见再高阶的幻方数量将是一个难以想象的数
抽象转换
世界杯比赛场数问题
如果全世界有224个队伍参加比赛，两两组合进行直接淘汰赛，那么一共需要进行多少场比赛可以决出冠军？
答案是：224-1
因为没进行异常两两组合的比赛，会淘汰1个队伍，那么要决出冠军，需要淘汰224-1只队伍，所以答案可以直接给出223
计数技术
基本法则
-
加法
cb-add - 乘法
- 减法
- 除法
排列组合
-
无重排序
P(4, 3) = 4 x 3 x 2
-
无重组合
C(4, 3) = P(4, 3) / 3!
-
可重排列
= n^r
-
多重全排列
P(n, r1, r2 .... rk)= P(n, n) / (r1! * r2! * ... rk!)
格路问题
路径数为C(m + n, n)
从(0, 0)到(m, n)只能向右和向上走，一共走m + n步，要向右走m步，向上走n步。
那么就排列成一个xyx....xxyy的一个组合
那么问题就规约为m + n的位置上，选择m个位置作为x（向右走），那么就可以得出组合的计数
递归关系
有C(n - r, r) = C(n - r - 1, r) + C(n - r, r -1)
二项式定理
所以计数为C(n, r)
圆排列
从n个不相同的元素取r个排成一个圆，的排列数为P(n, r)/r
乒乓球入洞
n个不同的乒乓球，进入r个洞的的方案数
P(n + r, n + r)/ r!
线性方程整数解
x1 + x2 + ... xn = b
的正整数解的个数为C(n + b -1, b)
不相邻组合
从{1, 2, .. n}取出r个不相邻的数
问题归约为从1到n - r个数取r个数的问题
所以计数为C(n - r - 1, r)
全排列
-
递归
先生成n - 1规模的全排列
然后用a[n]遍历每个排列项，从左到右插入，生成n规模的全排列
-
字典法
字母按字典法排序
先初始字典序最小的一个串
然后生成一个比当前串大一点点的串
直到生成字典序为逆序的最大串为止
-
SJT算法
通过交换来生成全排列
Stirling数
再计算n!的时候，当n足够大后，计算n!将会相当困难
母函数
一个函数：
如果关注的是x的解，那么G(x)是一个函数
如果关注的是c0, c1...的序列，那么G(x)就是一个母函数
应用
- 若有1g, 2g, 3g, 4g砝码各一个，能称出5g的有多少中方案
可得x的5次方系数为2
所以是两种
-
整数拆分
整数n拆分成1, 2, ... m的和，允许重复，有多少种方案
计算出x的n次方的系数
则为计数的答案
通解
如果直到母函数G(x)的表达式
通过对G(x)化简，对每一个单项进行泰勒展开式分解，可以得到任意复杂的序列C(n)
假设有以下序列的递推关系，并构造母函数，有
通过化简，可得
通过泰勒展开得
通过通解解法，可得斐波那契额数列得F(n)函数式
多重全排列
通过母函数的定义可知
Ck为x的k次方的组合数
而P(n, k) = Ck * k!
因此，如果要利用母函数计算x的k次方的排列数
则为
容斥定理
例子
-
计算1到500，能被3或者5整除的数的个数
A = 500/3 = 166
B = 500/5 = 100
A and B = 500/15 = 33
A or B = A + B - (A and B) = 233
-
整数拆分，求x1 + x2 + x3 = 15的 非负整数解的个数
约束：0 <= x1 <= 5, 0 <= x2 <= 6, 0 <= x3 <= 7
如果没有约束 A U B U C = C(17 , 2)
A: x1 >= 6
B: x2 >= 7
C: x3 >= 8
A and B and C = A U B U C - A - B -C + A and B + B and C + A and C
其中A利用
x + 6 + x2 + x3 = 15
可得A = C(11, 2)
同理可得B, C, ...
鸽巢原理
如果有n-1个抽屉，有n个球，那么至少有一个抽屉有至少两个球
群论
pendig
