组合数学

组合数学是离散数学的一个分支。专门研究计数的问题。

数学的发展历史

cb-his

组合数学的三大问题

• 存在性

  是否存在合理的解

• 计数

  有多少个解

• 优化

  哪个解是最优的

历史的组合问题

幻方

cb-33

存在

一个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
• 乘法

cb-multi

• 减法

cb-sub

• 除法

排列组合

• 无重排序

  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)

cb-squtroad

从(0, 0)到(m, n)只能向右和向上走，一共走m + n步，要向右走m步，向上走n步。

那么就排列成一个xyx....xxyy的一个组合

那么问题就规约为m + n的位置上，选择m个位置作为x（向右走），那么就可以得出组合的计数

递归关系

cb-gelu
有C(n - r, r) = C(n - r - 1, r) + C(n - r, r -1)

二项式定理

cb-twoab
cb-abr
所以计数为C(n, r)

圆排列

从n个不相同的元素取r个排成一个圆，的排列数为P(n, r)/r

cb-cycle

乒乓球入洞

cb-pingpo

n个不同的乒乓球，进入r个洞的的方案数

P(n + r, n + r)/ r!

线性方程整数解

x1 + x2 + ... xn = b

的正整数解的个数为C(n + b -1, b)

cb-xb

不相邻组合

从{1, 2, .. n}取出r个不相邻的数

cb-toget

问题归约为从1到n - r个数取r个数的问题

所以计数为C(n - r - 1, r)

全排列

• 递归

  先生成n - 1规模的全排列

  然后用a[n]遍历每个排列项，从左到右插入，生成n规模的全排列

cb-ap-digui

• 字典法

  字母按字典法排序

  先初始字典序最小的一个串

  然后生成一个比当前串大一点点的串

  直到生成字典序为逆序的最大串为止

• SJT算法

  通过交换来生成全排列

Stirling数

再计算n!的时候，当n足够大后，计算n!将会相当困难

cb-stirling

母函数

一个函数：

cb-mother

如果关注的是x的解，那么G(x)是一个函数

如果关注的是c0, c1...的序列，那么G(x)就是一个母函数

应用

• 若有1g, 2g, 3g, 4g砝码各一个，能称出5g的有多少中方案

cb-mom-g

可得x的5次方系数为2

所以是两种

• 整数拆分

  整数n拆分成1, 2, ... m的和，允许重复，有多少种方案

cb-mom-int

计算出x的n次方的系数

则为计数的答案

通解

如果直到母函数G(x)的表达式

通过对G(x)化简，对每一个单项进行泰勒展开式分解，可以得到任意复杂的序列C(n)

cb-er

假设有以下序列的递推关系，并构造母函数，有

cb-mon-tai

通过化简，可得

cb-mon-tai-h

通过泰勒展开得

cb-tai
通过通解解法，可得斐波那契额数列得F(n)函数式

多重全排列

cb-mother

通过母函数的定义可知

Ck为x的k次方的组合数

而P(n, k) = Ck * k!

因此，如果要利用母函数计算x的k次方的排列数

则为

cb-mon-pk

容斥定理

cb-rongchi

例子

• 计算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