To boldly go where no one has gone before.

【学习笔记】组合数

2019-03-18 23:03:31


组合数

从$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$的结果。

之前的代码把表示方法搞错了,简直耻辱