前言
计数的基本原理
考虑一个集合：\(S\)，求 \(|S|\)。
-
加法原理：\(S=S_1\cup S_2,|S|=|S_1|+|S_2|\)。
-
乘法原理：\(|{(a,b)|a\in S_1,b \in S_2}|=|s_1||s_2|\)
更浅显的说当两件事情无关时为加法，当前一件的结果影响后面时用乘法。
组合数基本公式及衍生公式
排列与组合
- 排列数：\(A_n^m= \dfrac{n!}{(n-m)!}\)。
相当与第一个可以选 \(n\) 个，第二个可以选 \(n-1\) 个，依次类推。
- 组合数：\(C_n^m=\binom{n}{m}=\dfrac{n!}{(n-m)!\times n!}\)。
在排列数中减去重复的 \(n!\) 项。
重要公式
- 递推式（杨辉三角）
感性愉悦：选不选最后一个。
理性愉悦：把式子拆开暴力计算。
- 二项式定理
感性愉悦：拆开相当于每个括号选 \(a\) 或选 \(b\)。
理性愉悦：数学归纳法。
- 组合式第 \(i\) 行的和：\(2^i\)。
用 \((1+1)^i\) 计算可证。
- 偶数项减奇数项：\([n=0]\)
用 \((1-1)^n\) 计算可证。
- 对称恒等式：
太显然就不证了。
- 链式恒等式（我们学长取的，没有专门的名字）
感性愉悦：等于先在 \(n\) 个中选 \(k\) 个，再选中间的 \(k\) 个。
理性愉悦：拆式子计算。
此等式很好证明但推式子时可能想不起。
- 吸收恒等式
感性愉悦：先选一个出来，然后再剩下的中选出 \(m-1\) 个，这样每个方案会被算 \(m\) 次，所以再除以 \(m\)。
理性愉悦：拆式子计算。
- 范德蒙德卷积式
感性愉悦：有两堆东西，总共选 \(k\) 个出来，等价于先枚举每堆选多少个，再在内部选。
理性愉悦：用二项式定理拆：\((x+1)^n(x+1)^m\)
十二重计数法
\(n\) 个有（无）标号的球放入 \(m\) 个有（无）标号的盒子，盒子无限制（至多一个球 / 至少一个球）的情况数：
| 球 | 盒子 | 无限制 | 至少一个 | 至多一个 |
|---|---|---|---|---|
| 可区分 | 可区分 | \(m^n\) | \(m! \begin{Bmatrix} n \\\\ m \end{Bmatrix}\) | \(A_m^n\) |
| 可区分 | 不可区分 | \(\sum_{i = 0}^m{\begin{Bmatrix} n \\\\ i \end{Bmatrix}}\) | \(\begin{Bmatrix} n \\\\ m \end{Bmatrix}\) | \([n \le m]\) |
| 不可区分 | 可区分 | \({n + m - 1 \choose m - 1}\) | \({n - 1 \choose m - 1}\) | \({m \choose n}\) |
| 不可区分 | 不可区分 | \(\sum_{i = 0}^m{p(n, i)}\) | \(p(n, m)\) | \([n \le m]\) |
卢卡斯定理
\[\binom{n}{m} \bmod p=\binom{\lfloor n / p\rfloor}{\lfloor m / p\rfloor}\binom{ n \bmod p}{m \bmod p} \bmod p \]主要应用为处理大范围模中等模数。
卡特兰数
\[\text{Cat}_n = {2n \choose n} - {2n \choose n + 1} = \frac{2n \choose n}{n + 1} \]求解从 \(n\times n\) 棋盘的一端走向另一端不超过对角线的方案数。
证明经典迷宫翻折法证明。
应用
-
个n行n列的棋盘,从左下角走到右上角，一直在对角线右下方走,不穿过主对角线,走法种数。
-
用 \(n\) 个左括号和 \(n\) 个右括号组成一串字符串,有多少种合法的组合?
例如,"()()(())”是合法的,而“())(()”是非法的。
显然,合法的括号组合是任意前 \(k\) 个括号组合,左括号的数量大于或等于右括号的数量。
定义左括号为 \(0\),右括号为 \(1\)。问题转换为 \(n\) 个 \(0\) 和 \(n\) 个 \(1\) 组成的序列,任意前 \(k\) 个序列中,\(0\) 的数量都大于或等于 \(1\) 的数量。模型和上面的棋盘问题一样。
- \(n\) 个节点构成的完全二叉树种类。