二项式定理二项式反演

内容

二项式定理

即 \((a+b)^n = \sum\limits_{i=0}^{n}a^{i}b^{n-i}\binom{n}{i}\)。

二项式反演

将 \(a=1, b=-1\) 代入二项式定理可得推论式 \(\sum\limits_{i=0}^{n} (-1)^{n-i}\binom{n}{i} = [n=0]\)。

分离式：\(\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}\)，根据组合意义易证。

现有反演： \(f(n) = \sum\limits_{i=0}^{n} \binom{n}{i} g(i) \Leftrightarrow g(n) = \sum\limits_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)\)。

证明

利用推论式与分离式进行证明。

\[\begin{array}{c} \sum\limits_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)\\ =\sum\limits_{i=0}^{n} (-1)^{n-i} \binom{n}{i} \sum\limits_{j=0}^{i} \binom{i}{j} g(j)\\ =\sum\limits_{j=0}^{n} \sum\limits_{i=j}^{n} (-1)^{n-i} \binom{n}{i} \binom{i}{j} g(j)\\ =\sum\limits_{j=0}^{n} \sum\limits_{i=j}^{n} (-1)^{n-i} \binom{n}{j} \binom{n-j}{i-j} g(j)\\ =\sum\limits_{j=0}^{n} \binom{n}{j} g(j)\sum\limits_{i=j}^{n} (-1)^{n-i} \binom{n-j}{i-j}\\ =\sum\limits_{j=0}^{n} \binom{n}{j} g(j)\sum\limits_{i+j=j}^{n} (-1)^{n-i-j} \binom{n-j}{i+j-j}\\ =\sum\limits_{j=0}^{n} \binom{n}{j} g(j)\sum\limits_{i=0}^{n-j} (-1)^{n-j-i} \binom{n-j}{i}\\ =\sum\limits_{j=0}^{n} \binom{n}{j} g(j)[n = j]\\ = g(n) \end{array} \]

两个基本形式：

1. 恰好转换为至多：\(f(n) = \sum\limits_{i=0}^{n} \binom{n}{i} g(i) \Leftrightarrow g(n) = \sum\limits_{i=0}^{n} (-1)^{n-i} \binom{n}{i} f(i)\)。

2. 恰好转换为至少：\(f(m) = \sum\limits_{i=m}^{n} \binom{i}{m} g(i) \Leftrightarrow g(m) = \sum\limits_{i=m}^{n} (-1)^{i-m} \binom{i}{m} f(i)\)。

例题（持续补充）

ABC423F Loud Cicada

1. \(g(m)\) 表示恰好 \(m\) 只蝉。
2. \(f(m)\) 表示至少 \(m\) 只蝉。

有 \(f(m) = \sum\limits_{i=m}^{n} \binom{i}{m} g(i) = \sum_{\mathrm{popcount(S)} = m} \lfloor \frac{Y}{\mathrm{lcm}_{u \in S} a_u} \rfloor\)