二項式反演

一、二項式反演組合意義

在組合數學中，二項式反演是一種重要的技巧。假設有兩個函數 $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. 二項式反演在組合設計中也有廣泛的應用，例如在設計含矩陣或線性碼的系統時，可以利用二項式反演來設計符合條件的矩陣或碼字。