组合记录
__ryp__
·
·
个人记录
很明显，集合大小如果增加一，那么这个新元素要么选要么不选，即
$${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)$$