$ C_n^m $ 在组合数学中的意义:在 n 个元素选 m 个元素的方案数。

公式

公式 1

$$ C_n^m = \frac{n!}{m! * (n-m)!} $$

组合数的通项公式。

当要求组合数模一般模数时 ,通项公式的分母可能没有逆元导致不可行。

公式 2

$$ C_n^m = C_n^{n-m} $$

基本性质,可以由通项公式得出。

公式 3

$$ C_n^m * C_m^k = C_n^k * C_{n-k}^{m-k} $$

公式 4

$$ C_n^m = C_{n-1}^{m-1} + C_{n-1}^m $$

组合数的基本递推式。

当要求组合数模一般模数时 ,常用这种方法预处理组合数。

公式 5

$$ \sum_{i=0}^n C_n^i = 2^n $$

组合意义: n 个元素选任意元素的方案数。
每个数都可以选或不选,所以方案数为 $ 2^n $ 。

同样可以由二项式定理: $ (x + 1)^n = \sum_{i=0}^n C_n^i * x^i $ 得出。

公式 6

$$ \sum_{i=0}^n (C_n^i)^2 = C_{2n}^n $$

公式 7

$$ C_{n+m}^k = \sum_{i=0}^k C_n^i * C_m^{k-i} $$

从组合数学上的定义出发,在 n + m 个元素中选 k 个,
相当于先在前 n 个元素中选 i 个再在后 m 个元素中选 k – i 个。
枚举这个 i 把方案数相加就能得到最终方案数。

Lucas 定理

$$ C_n^m = C_{n/p}^{m/p} * C_{n \; mod \; p}^{m \; mod \; p} (mod \; p) $$

常用于模数较小的组合数取模。


发表评论

电子邮件地址不会被公开。 必填项已用*标注