【学习笔记】组合数

# 组合数 从$n$个元素中选出$m$个元素的方案数，常用$C_n^m$或$C(n,m)$表示。 **注意$C_n^m$是从$n$个元素里选$m$个元素的方案数！** # 定理一 $$C^m_n=C^{n-m}_{n}$$ **解释：** 互补原理，从$n$个元素中选$m$个元素等价于从$n$个元素中选$(n-m)$个元素。 # 定理二 $$C_n^m=C_{n-1}^{m-1}+C_{n-1}^{m}$$ **解释：** 考虑从$n$个元素当中选一个特殊元素出来，对于这个元素由两种情况： 1. 该元素被包含在选出的$m$个元素当中，因此这种情况的方案数是$C_{n-1}^{m-1}$。 2. 该元素不被包含在选出的$m$个元素当中，因此这种情况的方案数是$C_{n-1}^m$。 将这两种情况的方案数相加，就得到了$C_n^m$的结果。因此可以用**记忆化搜索**实现计算$C_n^m$的结果。 ~~之前的代码把表示方法搞错了，简直耻辱~~