Product and Sum Principles
加法原理（分类计数） 若一个任务可分解为若干个互斥的子类，第 $ i $ 类有 $ a_i $ 种方案，则总数为 $ \sum_i a_i $。 解释：互斥保证不重不漏，求和即“或”的计数。
乘法原理（分步计数） 若一个任务分为若干个有序步骤，步骤 $ i $ 有 $ b_i $ 种选择且相互独立，则总数为 $ \prod_i b_i $。 解释：有序步骤逐个做决定，“且”的计数对应乘法。
Constructing Maps
有些组合证明可以依赖于构造映射：
- 单射：不同原像映到不同像，用于证明下界或“可嵌入性”。
- 满射：像覆盖全体，用于证明上界可达或构造覆盖。
- 双射：建立集合 $ A $ 与 $ B $ 的一一对应，从而数 $ |A|=|B| $；这是“数某一个量 ⇒ 构造双射”的核心思想。
Twelvefoldway
将 $ n $ 个球放入 $ m $ 个盒子，球与盒子可“可区分/不可区分”，以及盒子容量约束“任意/至多 1/至少 1”。
| $ n $ | $ m $ | 任意 | $ \leq 1 $ | $ \geq 1 $ |
|---|---|---|---|---|
| 不同 | 不同 | $ m^{n} $ | $ m^{\underline{n}} $ | $ m!\left\{ {n \atop m} \right\} $ |
| 同 | 不同 | $ \binom{ n+m-1 }{ m-1 } $ | $ \binom{ m }{ n } $ | $ \binom{ n-1 }{ m-1 } $ |
| 不同 | 同 | $ \sum_{k=0}^{\min(n,m)} \left\{ {n \atop k} \right\} $ | $ [n \leq m] $ | $ \left\{ {n \atop m} \right\} $ |
| 同 | 同 | $ p_{\leq m}(n) $ | $ [n \leq m] $ | $ p(n,m) $ |
“把 $ n $ 个不同球分成 $ k $ 个非空无序盒”对应第二类斯特林数 $ \left\{ {n \atop k} \right\} $。
Stirling Numbers of the Second Kind
定义：$ \left\{ {n \atop k} \right\} $ 表示“将 $ n $ 个不同元素分成 $ k $ 个非空无序块”的方案数。
基本递推：$$ \left\{ {n \atop k} \right\} = \left\{ {n-1 \atop k-1} \right\} + k \left\{ {n-1 \atop k} \right\}, \quad \left\{ {0 \atop 0} \right\}=1 $$ 从组合意义上理解，元素 $ n $ 要么独自成新块（$ \left\{ {n-1 \atop k-1} \right\} $），要么加入已有 $ k $ 个块之一（$ k \left\{ {n-1 \atop k} \right\} $）。
与降阶阶乘的分层展开：$$ m^{n} = \sum_{k=1}^{n} \left\{ {n \atop k} \right\} m^{\underline{k}} $$ 组合证明：
- 将 $ n $ 个不同球先“分组”为 $ k $ 个非空无序块： $ \left\{ {n \atop k} \right\} $。
- 从 $ m $ 个可区分盒中选出并按顺序对应这 $ k $ 个块： $ m^{\underline{k}} $。 按 $ k $ 分层求和即得全部映射 $ [n] \to [m] $ 的总数 $ m^n $。
另一恒等式：$$ \left\{ {n \atop m} \right\} = \sum_{k=0}^{n-1} \binom{ n-1 }{ k } \left\{ {n-k-1 \atop k-1} \right\} $$
Vandermonde’s Convolution
范德蒙卷积： $$ \binom{ r+s }{ n } = \sum_{k=0}^{n} \binom{ r }{ k } \binom{ s }{ n-k } $$
组合证明：从 $ r+s $ 个元素中选 $ n $ 个。分类：从前 $ r $ 个元素选 $ k $ 个、从后 $ s $ 个元素选 $ n-k $ 个，$ k $ 遍历 $ 0 $ 至 $ n $，互斥且完备，故求和。
代数证明：用二项式定理展开 $ (1+x)^{r+s} = (1+x)^r (1+x)^s $，比对 $ x^n $ 的系数即得。
Binomial Coefficients
对称性： $ \binom{ n }{ k } = \binom{ n }{ n-k } $ 组合：选 $ k $ 个等价于弃 $ n-k $ 个。
Pascal 恒等式： $ \binom{ n }{ k } = \binom{ n-1 }{ k } + \binom{ n-1 }{ k-1 } $ 组合：考虑是否包含元素 $ n $。
总和： $ \sum_{k=0}^{n} \binom{ n }{ k } = 2^{n} $ 组合：每元素选/不选两种，乘法原理；或代数用 $ (1+1)^n $。
“曲棍球杆”恒等式： $ \sum_{i=r}^{n} \binom{ i }{ r } = \binom{ n+1 }{ r+1 } $ 组合：给定最大元素，按其值分类累加；或用 Pascal 叠加。
一阶矩： $ \sum_{k=0}^{n} k \binom{ n }{ k } = n 2^{n-1} $ 组合：双计数“选出子集并指定一个已选标记元素”；或代数对 $ (1+x)^n $ 求导令 $ x=1 $。
二项式定理： $ (x+y)^{n} = \sum_{k=0}^{n} \binom{ n }{ k } x^{k} y^{n-k} $ 代数：展开乘法；组合：从 $ n $ 个因子中选 $ k $ 次取 $ x $。
范德蒙卷积：见上一节。
凸性与对数凹性：
- 对于固定 $ n $，序列 $ \left( \binom{ n }{ 0 }, \binom{ n }{ 1 }, \dots, \binom{ n }{ n } \right) $ 是对称、单峰且对数凹：对所有可行 $ k $，有 $$ \binom{ n }{ k }^{2} \ge \binom{ n }{ k-1 } \binom{ n }{ k+1 } $$
- 计算比值 $$ \frac{ \binom{ n }{ k } }{ \binom{ n }{ k-1 } } = \frac{ n-k+1 }{ k }, \quad \frac{ \binom{ n }{ k+1 } }{ \binom{ n }{ k } } = \frac{ n-k }{ k+1 } $$ 由此得 $$ \frac{ \binom{ n }{ k }^{2} }{ \binom{ n }{ k-1 } \binom{ n }{ k+1 } } = \frac{ k (k+1) }{ (n-k+1)(n-k) } \cdot \frac{ (n-k+1)(n-k) }{ k (k+1) } = 1 $$
Catalan Numbers
第 $ n $ 个卡特兰数 $$ C_n = \frac{ 1 }{ n+1 } \binom{ 2n }{ n } $$
网格路径模型：从点 $ (0,0) $ 到 $ (n,n) $，每步向右 $ R $ 或向上 $ U $，要求路径始终不越过主对角线 $ y=x $。这等价于计数长度 $ 2n $ 的序列，任意前缀中 $ U $ 的数量不小于 $ R $ 的数量。
经典反射法证明（Ballot/Reflection）：
- 总路径数：不加限制，从 $ 2n $ 步中选出 $ n $ 步为 $ U $，共 $ \binom{ 2n }{ n } $ 条。
- 计“坏”路径：越界的路径。设首次越界的时刻为第 $ t $ 步，此时 $ R $ 比 $ U $ 多一。将前 $ t $ 步关于直线 $ y=x $ 反射（交换 $ U $ 与 $ R $），得到一条从 $ (0,0) $ 到 $ (n+1,n-1) $ 的路径；此构造是坏路径与“从 $ (0,0) $ 到 $ (n+1,n-1) $ 的任意路径”之间的双射。因此坏路径数为 $ \binom{ 2n }{ n-1 } $。
- 好路径数： $ \binom{ 2n }{ n } - \binom{ 2n }{ n-1 } = \frac{ 1 }{ n+1 } \binom{ 2n }{ n } $，即 $ C_n $。
本质抽象：两类操作 $ U $ 与 $ R $ 总数相等，且任意时刻“$ U $ 的累计数 ≥ $ R $ 的累计数”。同构到投票/括号配对/堆栈可行序等大量模型。