组合数学

1. 基本计数原理

1.1 加法原理

若完成一件事有 $n$ 类方法，第 $i$ 类有 $m_i$ 种方法，各类方法互不相容，则完成该事共有 $m_1+m_2+\cdots +m_n$ 种方法。

1.2 乘法原理

若完成一件事需 $n$ 个步骤，第 $i$ 步有 $m_i$ 种方法，则完成该事共有 $m_1\times m_2\times \cdots \times m_n$ 种方法。

例：从 A 到 B 有3条路，从 B 到 C 有4条路，从 A 经 B 到 C 有 $3\times 4=12$ 种走法。

2. 排列与组合

2.1 排列

无重复排列：从 $n$ 个不同元素中取 $r$ 个排列：

$P(n,r)=\frac{n!}{(n-r)!}$

全排列：$P(n,n)=n!$

有重复排列：从 $n$ 个不同元素中取 $r$ 个（允许重复）排列：$n^r$

圆排列：$n$ 个不同元素的圆排列数：$(n-1)!$

2.2 组合

无重复组合：从 $n$ 个不同元素中取 $r$ 个：

$\left(\genfrac{}{}{0ex}{}{n}{r}\right)=C(n,r)=\frac{n!}{r!(n-r)!}$

多重组合（可重复组合）：从 $n$ 种元素中取 $r$ 个（允许重复）：

$\left(\genfrac{}{}{0ex}{}{n+r-1}{r}\right)=\left(\genfrac{}{}{0ex}{}{n+r-1}{n-1}\right)$

例：将10个相同的球放入3个不同的盒子，有多少种方法？

可重复组合：$\left(\genfrac{}{}{0ex}{}{10+3-1}{10}\right)=\left(\genfrac{}{}{0ex}{}{12}{10}\right)=66$。

2.3 组合恒等式

Pascal 恒等式：$\left(\genfrac{}{}{0ex}{}{n}{r}\right)=\left(\genfrac{}{}{0ex}{}{n-1}{r-1}\right)+\left(\genfrac{}{}{0ex}{}{n-1}{r}\right)$

二项式定理：$(x+y{)}^n={\sum }_{k=0}^n(\genfrac{}{}{0ex}{}{n}{k})x^k{y}^{n-k}$

特殊值：

• ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$
• ${\sum }_{k=0}^n(-1{)}^k(\genfrac{}{}{0ex}{}{n}{k})=0$
• ${\sum }_{k=0}^n{\left(\genfrac{}{}{0ex}{}{n}{k}\right)}^2=\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$（Vandermonde 恒等式的特例）

Vandermonde 恒等式：$\left(\genfrac{}{}{0ex}{}{m+n}{r}\right)={\sum }_{k=0}^r\left(\genfrac{}{}{0ex}{}{m}{k}\right)\left(\genfrac{}{}{0ex}{}{n}{r-k}\right)$

2.4 多重集的排列

设多重集 $S=\{n_1\cdot a_1,n_2\cdot a_2,\dots ,n_k\cdot a_k\}$，$n=n_1+n_2+\cdots +n_k$，则全排列数为：

$\frac{n!}{n_1!\cdot n_2!\cdots n_k!}$

例：MISSISSIPPI 的字母排列数。

$M:1$, $I:4$, $S:4$, $P:2$，共11个字母。 $\frac{11!}{1!\cdot 4!\cdot 4!\cdot 2!}=34650$

3. 容斥原理

3.1 两集合

$|A\cup B|=|A|+|B|-|A\cap B|$

3.2 三集合

$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$

3.3 一般形式

$\left|{\bigcup }_{i=1}^n{A}_i\right|={\sum }_i|A_i|-{\sum }_{i<j}|A_i\cap A_j|+{\sum }_{i<j<k}|A_i\cap A_j\cap A_k|-\cdots +(-1{)}^{n+1}|A_1\cap \cdots \cap A_n|$

3.4 错排问题

$n$ 个元素的错排（derangement）数：

$D_n=n!\left(1-\frac{1}{1!}+\frac{1}{2!}-\cdots +(-1{)}^n\frac{1}{n!}\right)=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}$

例：4个人的帽子全戴错的方案数。

$D_4=4!(1-1+\frac{1}{2}-\frac{1}{6}+\frac{1}{24})=24\cdot \frac{9}{24}=9$

3.5 Euler 函数

不超过 $n$ 且与 $n$ 互素的正整数个数：

$\phi (n)=n{\prod }_{p\mid n}\left(1-\frac{1}{p}\right)$

其中 $p$ 取遍 $n$ 的所有不同素因子。

例：$\phi (12)=12(1-\frac{1}{2})(1-\frac{1}{3})=12\cdot \frac{1}{2}\cdot \frac{2}{3}=4$。

4. 鸽巢原理

4.1 基本形式

将 $n+1$ 个物品放入 $n$ 个盒子，至少有一个盒子包含至少2个物品。

4.2 加强形式

将 $n$ 个物品放入 $k$ 个盒子，则至少有一个盒子包含至少 $\lceil n/k\rceil$ 个物品。

4.3 应用

例：在任意 $n+1$ 个正整数中，必有两个数之差是 $n$ 的倍数。

考虑这 $n+1$ 个数除以 $n$ 的余数，余数只有 $0,1,\dots ,n-1$ 共 $n$ 种，由鸽巢原理，必有两个数余数相同，其差是 $n$ 的倍数。

例：在边长为1的正三角形中任取5个点，必有两点距离不超过 $\frac{1}{2}$。

将正三角形分为4个边长为 $\frac{1}{2}$ 的小正三角形，5个点放入4个区域，必有2个在同一区域，距离不超过 $\frac{1}{2}$。

5. 递推关系

5.1 常系数线性齐次递推

$a_n+c_1{a}_{n-1}+c_2{a}_{n-2}+\cdots +c_k{a}_{n-k}=0$

特征方程：$x^k+c_1{x}^{k-1}+\cdots +c_k=0$

求解：

• 单根 $r$：贡献 $A{r}^n$
• $m$ 重根 $r$：贡献 $(A_0+A_{1}n+\cdots +A_{m-1}{n}^{m-1})r^n$

例：Fibonacci 数列 $F_n=F_{n-1}+F_{n-2}$，$F_0=0$，$F_1=1$。

特征方程：$x^2-x-1=0$，$x=\frac{1\pm \sqrt{5}}{2}$。 $F_n=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right]$

5.2 常系数线性非齐次递推

$a_n+c_1{a}_{n-1}+\cdots +c_k{a}_{n-k}=f(n)$

通解 = 齐次通解 + 非齐次特解

特解形式取决于 $f(n)$：

6. 生成函数

6.1 定义

序列 $\{a_n\}$ 的普通生成函数：

$G(x)={\sum }_{n=0}^{\infty }{a}_n{x}^n$

6.2 常用生成函数

6.3 应用

例：用1元、2元、5元硬币凑出 $n$ 元的方案数。

生成函数： $G(x)=\frac{1}{1-x}\cdot \frac{1}{1-x^2}\cdot \frac{1}{1-x^5}$ $a_n$ 为 $G(x)$ 展开式中 $x^n$ 的系数。

6.4 指数生成函数

$E(x)={\sum }_{n=0}^{\infty }{a}_n\frac{x^n}{n!}$

适用于排列计数问题。

7. Catalan 数

7.1 定义

$C_n=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)=\frac{(2n)!}{(n+1)!n!}$

前几项：$C_0=1,C_1=1,C_2=2,C_3=5,C_4=14,C_5=42$

7.2 递推关系

$C_n={\sum }_{i=0}^{n-1}{C}_i{C}_{n-1-i},C_0=1$

7.3 组合意义

$C_n$ 计数的问题：

1. $n$ 对括号的合法匹配数
2. $n+1$ 个矩阵连乘的加括号方式数
3. 从 $(0,0)$ 到 $(n,n)$ 不越过对角线的路径数
4. $n$ 个节点的不同二叉搜索树个数
5. 凸 $n+2$ 边形的三角剖分数
6. 栈的合法出栈序列数

例：3对括号的合法匹配：$C_3=5$ 种。

((())), (()()), (())(), ()(()), ()()()

7.4 生成函数

$C(x)={\sum }_{n=0}^{\infty }{C}_n{x}^n=\frac{1-\sqrt{1-4x}}{2x}$

8. Stirling 数

8.1 第一类 Stirling 数

$s(n,k)$：将 $n$ 个不同元素排成 $k$ 个非空轮换的方案数。

递推：

$s(n,k)=s(n-1,k-1)+(n-1)\cdot s(n-1,k)$

边界：$s(0,0)=1$，$s(n,0)=0$（$n>0$），$s(n,n)=1$

与阶乘的关系：

$x^{\underline{n}}=x(x-1)(x-2)\cdots (x-n+1)={\sum }_{k=0}^{n}s(n,k)x^k$

8.2 第二类 Stirling 数

$S(n,k)$：将 $n$ 个不同元素分成 $k$ 个非空子集的方案数。

递推：

$S(n,k)=S(n-1,k-1)+k\cdot S(n-1,k)$

边界：$S(0,0)=1$，$S(n,0)=0$（$n>0$），$S(n,n)=1$，$S(n,1)=1$

与幂的关系：

$x^n={\sum }_{k=0}^{n}S(n,k)x^{\underline{k}}$

显式公式：

$S(n,k)=\frac{1}{k!}{\sum }_{j=0}^k(-1{)}^{k-j}(\genfrac{}{}{0ex}{}{k}{j})j^n$

例：$S(4,2)=7$。

4个元素分成2个非空子集：$\{1\}\{2,3,4\}$, $\{2\}\{1,3,4\}$, $\{3\}\{1,2,4\}$, $\{4\}\{1,2,3\}$, $\{1,2\}\{3,4\}$, $\{1,3\}\{2,4\}$, $\{1,4\}\{2,3\}$。

8.3 Bell 数

$B_n={\sum }_{k=0}^{n}S(n,k)$

$B_n$ 是 $n$ 个元素的划分总数。

前几项：$B_0=1,B_1=1,B_2=2,B_3=5,B_4=15,B_5=52$

递推：$B_{n+1}={\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)B_k$

指数生成函数：${\sum }_{n=0}^{\infty }{B}_n\frac{x^n}{n!}=e^{e^x-1}$