二项式系数定理总结

这篇文章主要记录一些基本二项式系数定理

定义

首先给出二项式系数的定义: ${n\choose m}=\dfrac{n!}{m!(n-m)!}$

有一种解释是 $n$ 个物品中选出 $m$ 个物品的方案数,同时也是杨辉三角中的第 $n$ 行 $m$ 列

基本恒等式

加法恒等式

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

用组合解释即:当前有 $n$ 个物品,选择 $m$ 个可以是不选第 $n$ 个,从 $n-1$ 个中挑 $m$ 个;也可以是选第 $n$ 个,从 $n-1$ 个中挑 $m-1$ 个

同时也是杨辉三角的计算公式

在OI中通常计算组合数有三种方式

  • 根据加法恒等式递推

  • 杨辉三角 $O(nm)$ 预处理出所有 $n,m$ 范围内的组合数

  • 使用定义式,首先预处理出 $n,m$ 范围内所有数的阶乘即逆元, $O(1)$ 计算

上指标求和法

$$
\sum_{k=0}^n{k\choose m}={n+1\choose m+1}
$$

用杨慧三角理解即求杨慧三角某一列的前缀和

平行求和法

$$
\sum_{k=0}^m{n+k\choose k}={n+m+1\choose m}
$$

用杨辉三角理解即某一个斜行的前缀和

范德蒙德卷积公式

$$
\sum_{k=0}^n{r\choose k}{s\choose n-k}={r+s\choose n}
$$

即从 $r+s$ 个物品中挑出 $n$ 个物品的方案数为从 $r$ 中挑出 $k$ 个乘上 $s$ 中挑出 $n-k$ 个的和