先看子集反演，這是比較好理解的。

\[g(S)=\sum\limits_{T\subseteq S}f(T)\\
f(S)=\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}g(T)
\]

考慮選一堆物品，可以令?\(f(S)\)?表示恰好選取集合?\(S\)?的方案，\(g(S)\)?表示選取?\(S\)?子集的方案。

當所有物品等價的時候，\(f(S),g(S)\)?都只與?\(|S|\)?有關(guān)。此時可以設(shè)?\(f(S)=F(|S|)，g(S)=G(|S|)\)。（則?\(F(|S|),G(|S|)\)?的自變量是集合大?。?/p>

帶入子集反演，第一個式子：

\[\begin{align*}
g(S)&=\sum\limits_{T\subseteq S}f(T)\\
&=\sum\limits_{T\subseteq S}F(|T|)\\
&=\sum\limits_{|T|\le |S|}\binom{|S|}{|T|}F(|T|)\\
\Rightarrow G(|S|)&=\sum\limits_{|T|\le |S|}\binom{|S|}{|T|}F(|T|)\\
\Leftrightarrow G(k)&=\sum\limits_{i=0}^k \binom{k}{i}F(i)\\
\end{align*}
\]

注意中間增加的那個?\(\binom{|S|}{|T|}\)?是怎么來的呢？這是因為?\(\sum\)?的限制條件?\(|T|\le |S|\)?是不等價于?\(T\subseteq S\)?的，所以我們要求出?\(S\)?的子集中，有多少子集的大小為?\(|T|\)?，這個數(shù)就是?\(\binom{|S|}{|T|}\)。

帶入第二個式子，同理也可以得到

\[F(k)=\sum\limits_{i=0}^k (-1)^{k-i}\binom{k}{i}G(i)
\]

這樣我們就證明了二項式反演的一種形式。

至于另外一種形式，似乎不能用子集反演推出來。

鏈接：https://www.dianjilingqu.com/471480.html