二项式反演

二项式反演

有函数 $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)$）之间的对应关系。）

证明

（更多…）