「反演」學習筆記

「反演」學習筆記

小聲bb：本來看skyh推的部落格，是來學容斥的，莫名其妙被強塞了反演

概念

好多童鞋還不知道啥是反演，反正聽起來挺牛逼的，誰會誰被膜。

比如說有兩個未知量 \(x,y\)，我們用 \(x\) 表達出來了 \(y\)，比如一個一次函數：

\[y=kx+b
\]

那麼我們用 \(y\) 表示 \(x\) 就是：

\[x=\frac{y-b}{k}
\]

\(emmmm\)，這差不多就是個反演。

然後我們就搞高級一點：

假設有兩個函數 \(f\) 和 \(g\) 滿足：

\[f[n] = \sum_{k}a_{n,k}\times g[k]
\]

已知 \(f\) 求 \(g\) 的過程就叫做「反演」。

二項式反演

例題

有 \(n\) 個小盆友，每個人有一個編號 \(1,2…,n\) 。

將這 \(n\) 個小盆友排成一列，編號為 \(i\) 的小盆友不能在第 \(i\) 個位置。

求出所能排隊的方案數，\(n\leq 10^5\) 。

簡單容斥（聽說小學生都會？？）

  • 假設 \(n=3\) 。

我們拿出高一老師（？？）常拿的韋恩影像：

定義：

\(A\) 集合：編號為 \(1\) 的小盆友站到 \(1\) 的方案數。

\(B\) 集合：編號為 \(2\) 的小盆友站到 \(2\) 的方案數。

\(C\) 集合：編號為 \(3\) 的小盆友站到 \(3\) 的方案數。

我們要求的就是 \(n! – |A\cup B\cup C|\)，用簡單的容斥可得：

\(ans=n! – (|A|+|B|+|C|-|A\cap B|-|B\cap C|-|A\cap C|+ |A\cap B\cap C|)\)

得出公式

我們可以大膽猜想：

\[ans = \sum_{k=0}^{n}(-1)^k\times \binom{n}{k}\times (n – k)!\;(假設 0!=1)
\]

  • 什麼意思？

\(\binom{n}{k}\times (n – k)!\) 表示強硬的將 \(k\) 個人放到自己應該放的位置（\(i\) 放到第 \(i\) 個位置），剩下 \(n-k\) 個人隨便放的方案數。

  • 為啥要加一個 \((-1)^k\)？

比如說你加上了一個 \(k=2\) 的方案數，強硬地將 \(2\) 個人，後面我們統計 \(k=3\) 時，我們會發現：在前面 \(k=2\) 時，可能有某個小盆友被放到了自己應該放的位置，所以要

減去這些被多餘統計的方案，加法同理。

新定義

定義 \(f[n]\) 表示 \(n\) 個人隨便站的方案數。

定義 \(g[n]\) 表示 \(n\) 個人都不站在自己應該在的位置的方案數。

這樣我們直接枚舉有多少個人站錯位置，便可求出 \(f[n]\)。

\[f[n]=\sum_{k=0}^{n}\times \binom{n}{k}\times g[k]
\]

但是我們會發現，我們可以直接用 \(f[n] = n!\) 求出 \(f[n]\)，而且我們還不會求出 \(g[n]\)，難受～～～

小鑰匙

我們會發現之前解決那個例題的公式中有一個這個東東：

\[\sum_{k=0}^{n}(-1)^k\times \binom{n}{k}
\]

易得：這個東東只有 \(n=0\) 時才為 \(1\)，否則即為 \(0\) 。

  • 我們再引進一個神犇數學符號：\([P]\)，表示條件 \(P\) 符合時，為 \(1\)；否則即為 \(0\)，（好像一個 \(bool\)）。

所以上面那個東東就可以化為：

\[\sum_{k=0}^{n}(-1)^k\times \binom{n}{k}=[n=0]
\]

反演

之前我們新定義里：

用 \(g[n]\) 表示出了 \(f[n]\)，然而我們並不知道 \(g[n]\)，反而知道 \(f[n]\)，我們就需要一些騷操作（繁衍呸，反演），來求出 \(g[n]\) 。

說一句廢話：

\[g[n] = \sum_{m=0}^{n}[n=m]\times \binom{n}{m}\times g[m]
\]

改一下這個廢話：

\[g[n] = \sum_{m=0}^{m}[n-m=0]\times \binom{n}{m}\times g[m]
\]

哦！！！中間那個條件，我們是不是可以用一下那個小鑰匙？

\[g[n] = \sum_{m=0}^{n} \sum_{k=0}^{n-m}(-1)^k\times \binom{n-m}{k}\times \binom{n}{m}\times g[m]
\]

看一看中間那兩個噁心的組合數：

可以考慮為從 \(n\) 個物品里，先選 \(m\) 個，再從 \(n-m\) 個裡選 \(k\) 個的方案數。

可以變為為從 \(n\) 個物品里，先選 \(k\) 個，再從 \(n-k\) 個裡選 \(m\) 個的方案數，組合數可以變為： \(\binom{n-k}{m}\times \binom{n}{k}\) 。

原式變為：

\[g[n] = \sum_{m=0}^{n} \sum_{k=0}^{n-m}(-1)^k\times \binom{n-k}{m}\times \binom{n}{k}\times g[m]
\]

交換一下：

\[g[n] = \sum_{m=0}^{n} \sum_{k=0}^{n-m}(-1)^k\times \binom{n-k}{m}\times g[m] \times \binom{n}{k}
\]

然後將 \(m\) 和 \(k\) 交換一下：

\[g[n] = \sum_{k=0}^{n} \sum_{m=0}^{n-k}(-1)^k\times \binom{n-k}{m}\times g[m] \times \binom{n}{k}
\]

再次交換：

\[g[n] = \sum_{k=0}^{n} (-1)^k\times \binom{n}{k} \sum_{m=0}^{n-k} \binom{n-k}{m}\times g[m]
\]

誒！！後面那個東東就是 \(f[n – k]\)，可，我們成功了！！！

\[g[n] = \sum_{k=0}^{n} (-1)^k\times \binom{n}{k} \times f[n-k]
\]

\(emmmm\)，好醜，寫好看一點：

\[g[n] = \sum_{k=0}^{n} (-1)^{n-k}\times \binom{n}{k} \times f[k]
\]

得出結果

\[f[n]=\sum_{k=0}^{n}\times \binom{n}{k}\times g[k]
\]

\[g[n] = \sum_{k=0}^{n} (-1)^{n-k}\times \binom{n}{k} \times f[k]
\]

這個好像就是二項式反演

可能與 \(A\) 層的巨佬們學的有點不同，有錯誤，請見諒我這個蒟蒻。

莫比烏斯反演

例題

小盆友學英語，他拿到 \(26\) 個小寫字母，他拼出若干個長度為 \(n\) 的字元串，求出有多少個字元串的循環節恰好為 \(n\)，\(n\leq 10^9\) 。

連小盆友都知道循環節是啥，不用我說吧….（最短的一個子串複製若干遍後拼起來跟原串相等的字元串）。

新定義

定義 \(f[n]\) 表示長度為 \(n\) 的字元串的個數，顯然是 \(26^n\) 。

定義 \(g[n]\) 表示長度為 \(n\) 且循環節長度為 \(n\) 的字元串的個數。

可以得出：

\[f[n] = \sum_{d|n}g[d]
\]

小鑰匙

上次我們用了一個條件表達式，打開了反演的關鍵，這個我們同樣搞一個：

定義一個 \(\mu[n]\) 滿足：（莫某某某搞的）

\[\sum_{d|n}\mu[d] = [n=1]
\]

其實這個就是莫比烏斯函數，至於性質，可以看一眼龍蝶的。

反演

同樣，我們說一句廢話：

\[g[n] = \sum_{m|n}[n=m]\times g[m]
\]

將條件表達式變一下：

\[g[n] = \sum_{m|n}[\frac{n}{m}=1]\times g[m]
\]

好，用我們的小鑰匙：

\[g[n] = \sum_{m|n}\sum_{d|\frac{n}{m}}\times \mu[d] \times g[m]
\]

上次我們將 \(m\) 和 \(k\) 進行了交換，這次怎麼處理呢？

我們會發現 \(n\) 能將 \(m\) 整除，\(\frac{n}{m}\) 能將 \(d\) 整除，所以我們可以得出 \(n\) 既能將 \(m\) 整除，又能將 \(d\) 整除，這樣我們就可以將 \(m\) 和 \(k\) 交換了。

\[g[n] = \sum_{d|n}\sum_{m|\frac{n}{d}}\times \mu[d] \times g[m]
\]

交換一下：

\[g[n] = \sum_{d|n} \times \mu[d]\sum_{m|\frac{n}{d}} \times g[m]
\]

不錯，後面那個東東又可以化為我們的 \(f\)，可

\[g[n] = \sum_{d|n} \times \mu[d]\times f[\frac{n}{d}]
\]

得出結果

\[f[n] = \sum_{d|n}g[d]
\]

\[g[n] = \sum_{d|n} \times \mu[d]\times f[\frac{n}{d}]
\]

這個好像就是莫比烏斯反演

其他反演敬請期待

Tags:

VirMach 便宜 VPS

QNews

QNews