查看“︁反演”︁的源代码

本页面大量引用 [https://oiwiki.org/ OI Wiki]

组合数 <math>C_n^m</math> 常用符号 <math>\dbinom{n}{m}</math> 来表示，读作“<math>n</math> 选 <math>m</math>”。

==组合数经典性质==

选出 <math>m</math> 相当于选出 <math>n-m</math> 个排除。

<math>\dbinom{n}{m}=\dbinom{n}{n-m}</math>

组合数的递推式（杨辉三角）

<math>\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}</math>

基础性质（杨辉三角的一行、<math>(1+1)^n</math>）

<math>\dbinom{n}{0}+\dbinom{n}{1}+\dots+\dbinom{n}{n}=\sum_{i=0}^n\dbinom{n}{i}=2^n</math>

范德蒙德恒等式

<math>\sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{m+n}{k}</math>

==二项式定理==

<math>(a+b)^n=\sum_{i=0}^n\dbinom{n}{i}a^{n-i}b^i</math>

==二项式反演==

记 <math>f_n</math> 表示恰好使用 <math>n</math> 个不同元素形成特定结构的方案数，<math>g_n</math> 表示从 <math>n</math> 个不同元素中选出 <math>i \geq 0</math> 个元素形成特定结构的总方案数．

若已知 <math>f_n</math> 求 <math>g_n</math>，那么显然有：

<math>g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i</math>

若已知 <math>g_n</math> 求 <math>f_n</math>，那么：

<math>f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i</math>

上述已知 <math>g_n</math> 求 <math>f_n</math> 的过程，就称为“二项式反演”．

==狄利克雷卷积==

==莫比乌斯反演==