二项式反演及其证明

二项式反演

有函数 $f,g$，则 $\forall n \in \mathbb{N},$ $$\begin{aligned} f(n)=\sum\limits_{x=0}^{n}\dbinom{n}{x}g(x) &\iff g(n)=\sum\limits_{x=0}^{n}(-1)^{n-x}\dbinom{n}{x}f(x) && (1)\\ f(n)=\sum_{x=0}^{n}(-1)^x\dbinom{n}{x}g(x) &\iff g(n)=\sum\limits_{x=0}^{n}(-1)^x\dbinom{n}{x}f(x) && (2)\\ f(n)=\sum_{x=n}^{+\infty}\dbinom{x}{n}g(x) &\iff g(n)=\sum_{x=n}^{+\infty}(-1)^{x-n}\dbinom{x}{n}f(x) && (3) \end{aligned}$$

（6月22日追记：式 $(1),(3)$ 在OI中是最常用的。尤其是 $(3)$，阐述了在计数类问题中钦定 $x$ 个元素满足某种属性（$f(x)$），其他元素任意，与恰好有 $x$ 个元素满足某种属性（$g(x)$）之间的对应关系。）

证明

给出对式 $(1)$ 的证明。式 $(2),(3)$ 采用类似方法可证。

$$\begin{aligned} g(n) & =\sum_{x=0}^{n}(-1)^{n-x}\dbinom{n}{x}f(x)\\ & =\sum_{x=0}^{n}(-1)^{n-x}\sum_{y=0}^{x}{\color{blue}\dbinom{n}{x}\dbinom{x}{y}}g(y)\\ & =\sum_{x=0}^{n}(-1)^{n-x}\sum_{y=0}^{x}{\color{blue}\dbinom{n}{y}\dbinom{n-y}{x-y}}g(y) \end{aligned}$$

（蓝字转化可以考虑其组合意义：在 $n$ 个元素中选 $x$ 个再在其中选择 $y$ 个，等价于在 $n$ 个元素中钦定 $y$ 个，再在剩余 $(n-y)$ 个元素中选择 $(x-y)$ 个与之组合成为 $x$ 个元素。）

考虑转化贡献，统计对于每个 $g(y), y \in \{0, 1, \cdots, n\}$ 被累加了多少次。则有 $$\begin{aligned} g(n) & =\sum_{y=0}^{n}\dbinom{n}{y}g(y)\sum_{x=y}^{n}(-1)^{n-x}\dbinom{n-y}{x-y}\\ & =\sum_{y=0}^{n}\dbinom{n}{y}g(y){\color{red}\sum_{x=0}^{n-y}(-1)^{(n-y)-x}\dbinom{n-y}{x}}\\ & =\sum_{y=0}^{n}\dbinom{n}{y}g(y){\color{red}[n-y=0]}\\ & =g(n) &\square \end{aligned}$$

（红字转化为二项式定理在 $(a+b)^{n-y}, a=-1, b=1$ 系数展开的特殊情况。）