查看“︁06-数学相关/07-组合数与反演”︁的源代码


> 本页面大量引用 [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>\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>f(n)</math> 和 <math>g(n)</math> 的 Dirichlet 卷积，记作 <math>f \ast g</math>，定义为：

<math>(f \ast g)(n) = \sum_{k\mid n}f(k)g\left(\dfrac{n}{k}\right) = \sum_{k\ell=n}f(k)g(\ell)</math>

== 莫比乌斯反演 ==

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

莫比乌斯函数 <math>\mu(n)</math> 定义为：

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

=== 莫比乌斯反演 ===

设 <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>

== 组合数计算 ==

=== 递推求组合数 ===

<syntaxhighlight lang="cpp">
const int MAXN = 2000;
int C[MAXN + 5][MAXN + 5];

void init()
{
    for (int i = 0; i <= MAXN; i++)
    {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    }
}
</syntaxhighlight>

=== 阶乘逆元求组合数 ===

<syntaxhighlight lang="cpp">
// fact[i] = i! % MOD, invFact[i] = (i!)^-1 % MOD
int C(int n, int m)
{
    if (n < m || m < 0)
        return 0;
    return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}
</syntaxhighlight>


[[Category:数学相关]]
[[Category:三三文档]]