二项式反演

一、二项式反演组合意义

在组合数学中，二项式反演是一种重要的技巧。假设有两个函数 $f(n)$ 和 $g(n)$，它们之间满足以下的形式。

$$ g(n)=\sum_{i=0}^{n}{\binom {n}{i}}f(i) $$

反演之后，我们可以得到下面的公式：

$$ f(n)=\sum_{i=0}^{n}(-1)^{i}\binom {n}{i}g(i) $$

这里的组合意义是：$f(n)$ 表示选出 $n$ 个对象中特定的一些对象的方案数，$g(n)$ 表示选出 $n$ 个对象中至少一个对象的方案数。从 $g(n)$ 转换到 $f(n)$ 就相当于把至少一个对象变为特定的一个对象；而从 $f(n)$ 转换到 $g(n)$ 就相当于把特定的一个对象变为至少一个对象。因此，在组合意义上，二项式反演被描述为一种从计数至多的对象到计数恰好的对象的映射。

二、二项式反演公式证明

要证明二项式反演公式，我们需要使用排列组合的思想以及 Taylor 展开式。

假设有两个函数 $f(x)$ 和 $g(x)$ 满足以下的形式：

$$ g(x)=\sum_{i=0}^{\infty}{\binom {x}{i}}f(i) $$

现在，我们对 $f(x)$ 进行 Taylor 展开：

$$ f(x)=\sum_{i=0}^{\infty}{\frac {f^{(i)}(0)}{i!}}x^{i} $$

其中，$f^{(i)}(0)$ 表示 $f(x)$ 在 $x=0$ 处的 $i$ 阶导数。将上述式子代入到 $g(x)$ 中，可以得到：

$$ g(x)=\sum_{i=0}^{\infty}\binom {x}{i}\sum_{j=0}^{\infty}\frac {f^{(j)}(0)}{j!}i^{j}x^{i} $$

将 $i^{j}$ 和 $\binom {x}{i}$ 展开，并且互换求和符号，可以得到：

$$ g(x)=\sum_{j=0}^{\infty}\frac {f^{(j)}(0)}{j!}\sum_{i=j}^{\infty}(i)_{j}\binom {x}{i}(-1)^{i-j} $$

其中，$(i)_{j}$ 表示 $i$ 的 $j$ 阶下降幂。

最后，我们将 $(i)_{j}$ 转换为 $(-1)^{j}\binom {-n}{j}$，并把 $\binom {x}{i}$ 展开为幂级数，可以得到：

$$ g(x)=\sum_{j=0}^{\infty}(-1)^{j}\binom {-x}{j}\frac {f^{(j)}(0)}{j!} $$

这就是二项式反演公式的证明。

三、二项式反演公式

根据以上的推导，我们可以得到二项式反演公式：

$$ f(n)=\sum_{i=0}^{n}(-1)^{i}\binom {n}{i}g(i) $$

其中，$f(x)$ 和 $g(x)$ 表示两个函数，$n$ 是一个非负整数。

四、二项式反演公式的对偶形式

二项式反演公式还有一种形式，它被称为二项式反演公式的对偶形式。它的形式如下：

$$ g(n)=\sum_{i=0}^{n}(-1)^{i}\binom {i-1}{n-1}f(i) $$

这个公式和原始的二项式反演公式非常相似，只是 $f(i)$ 和 $g(i)$ 的位置调换了一下，并且 $\binom {n}{i}$ 变成了 $\binom {i-1}{n-1}$。

五、二项式反演多项式

二项式反演还可以扩展到多项式形式。具体地，假设有两个多项式 $f(x)$ 和 $g(x)$ 满足以下的形式：

$$ g(x)=\sum_{i=0}^{n}\binom {x}{i}f(i) $$

那么，我们可以得到以下的多项式：

$$ f(x)=\sum_{i=0}^{n}(-1)^{i}\binom {x}{i}g(i) $$

这个多项式被称为二项式反演多项式。

六、二项式反演证明

二项式反演的证明一般涉及到生成函数和递推式的技巧。下面是一个关于二项式反演的证明示例。

// 给出一个数列 a，计算另外一个数列 b，使得：
// b[n]=sum(a[i]*(-1)^(i-n)*C(n,i), i=0..n)
for (int n = 0; n < N; ++n) {
    b[n] = a[n];
    for (int i = 0; i < n; ++i) {
        b[n] -= a[i] * binom(n, i) * ((n - i) & 1 ? -1 : 1);
    }
}

七、二项式反演知乎

可以在知乎上搜索“二项式反演”，可以找到很多关于二项式反演的问题和答案，其中包括一些非常好的解释和应用。

八、二项式反演公式应用

二项式反演在组合计数和概率计算中有很多重要的应用。以下是一些常见的应用方式。

1. 求解组合计数问题，特别是一些计数恰好的问题。例如，计算长度为 $n$ 的排列中包含恰好 $k$ 个逆序对的方案数。

2. 在算法竞赛中，二项式反演可以用于解决一些经典问题，例如莫队算法中的区间逆序对问题。

3. 在群论中，二项式反演可以用于计算对称群、阿贝尔群和扭结群的某些特征函数。

4. 二项式反演在组合设计中也有广泛的应用，例如在设计含矩阵或线性码的系统时，可以利用二项式反演来设计符合条件的矩阵或码字。