本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-07-21 16:15:04

$n\choose m$，从一个大小为 $n$ 的集合中选出 $m$ 个，不考虑选出顺序的方案数。

很明显，集合大小如果增加一，那么这个新元素要么选要么不选，即

$${n\choose m} = {n-1\choose m}+{n-1\choose m - 1}$$

插板法：

$n$ 个人，分成 $k$ 组的方案数量。

用插板法，相当于总共 $n - 1$ 个间隔中选出 $k$ 个，相邻两个间隔是一组，即 $n-1\choose k - 1$。

用 dp，设 $f(i, j)$ 为前 $i$ 个元素，分成 $j$ 组的方案数，有显然转移

$$f(i, j) = \sum\limits_{k=0}^{i-1} f(k, j - 1)$$