本页面大量引用 OI Wiki

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

组合数经典性质

选出 $m$ 相当于选出 $n-m$ 个排除。

$\dbinom{n}{m}=\dbinom{n}{n-m}$

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

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

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

$\dbinom{n}{0}+\dbinom{n}{1}+\dots+\dbinom{n}{n}=\sum_{i=0}^n\dbinom{n}{i}=2^n$

范德蒙德恒等式

$\sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{m+n}{k}$

二项式定理

$(a+b)^n=\sum_{i=0}^n\dbinom{n}{i}a^{n-i}b^i$

二项式反演

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

若已知 $f_n$ 求 $g_n$，那么显然有：

$g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i$

若已知 $g_n$ 求 $f_n$，那么：

$f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i$

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

狄利克雷卷积

数论函数 $f(n)$ 和 $g(n)$ 的 Dirichlet 卷积（Dirichlet convolution），记作 $f \ast g$，定义为数论函数

(f \\ast g)(n) = \\sum_{k\\mid n}f(k)g\\left(\\dfrac{n}{k}\\right) = \\sum_{k\\ell=n}f(k)g(\\ell).

莫比乌斯反演

莫比乌斯函数

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

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

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

$\mu(1) = 1$；

当存在 $i$ 使得 $e_i>1$，即存在任何素因数出现超过一次时，$\mu(n)=0$；

否则，对于所有 $i$ 都有 $e_i = 1$，即任何素因数都只出现一次时，$\mu(n)=(-1)^k$，其中，$k$ 就是互异素因子的个数．

莫比乌斯反演

设 $f(n),g(n)$ 是两个数论函数．那么，有

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

扩展

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

缩略图|替代=莫比乌斯反演|莫比乌斯反演