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

本页面大量引用 [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> 的过程，就称为“二项式反演”．

==狄利克雷卷积==

==莫比乌斯反演==

===莫比乌斯函数===

莫比乌斯函数（Möbius 函数）定义为

<math>
\mu(n)=
\begin{cases}
1,&n=1,\\
0,&n\text{是某个质数平方的倍数}\\
(-1)^k,&n \text{是} k \text{个不同质数的乘积}.\\
\end{cases}
</math>

具体地，假设正整数 <math>n</math> 有素因数分解 <math>n=\prod_{i=1}^kp_i^{e_i}</math>，其中，<math>p_i</math> 是素数，<math>e_i</math> 是正整数．那么，三种情形分别对应：

# <math>\mu(1) = 1</math>；
# 当存在 <math>i</math> 使得 <math>e_i>1</math>，即存在任何素因数出现超过一次时，<math>\mu(n)=0</math>；
# 否则，对于所有 <math>i</math> 都有 <math>e_i = 1</math>，即任何素因数都只出现一次时，<math>\mu(n)=(-1)^k</math>，其中，$k$ 就是互异素因子的个数．

===莫比乌斯反演===
设 <math>f(n),g(n)</math> 是两个数论函数．那么，有
    
<math>
f(n) = \sum_{d\mid n}g(d) \iff g(n) = \sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)f(d).
</math>

====扩展====

<math>    
f(n) = \sum_{n\mid d}g(d) \iff g(n) = \sum_{n\mid d}\mu\left(\dfrac{d}{n}\right)f(d).
</math>