- 子集反演
\[g(S)=\sum_{T\subseteq S}f(T) \Leftrightarrow f(S)=\sum_{T\subseteq S}g(T)\cdot (-1)^{|S|-|T|}
\]
\[h(S)=\sum_{T\supseteq S}f(T) \Leftrightarrow f(S)=\sum_{T\supseteq S}h(T)\cdot (-1)^{|T|-|S|}
\]
- 二项式反演
\[g(n)=\sum_{i=0}^n\binom{n}{i}f(i)\Leftrightarrow f(n)=\sum_{i=0}^n(-1)^{n-i}\binom{n}{i}g(i)
\]
\[h(n)=\sum_{i=n}^m\binom{i}{n}f(i)\Leftrightarrow f(n)=\sum_{i=n}^m(-1)^{i-n}\binom{i}{n}h(i)
\]
- 莫比乌斯反演
\[[\gcd(x,y)=1]=\sum_{d|x,d|y}\mu(d)
\]
-
组合恒等式
-
- 组合递推式：
\[\binom{n}{k}=\binom{n-1}{k-1}+\binom{n-1}{k}
\]
-
- 不知名恒等式：
\[\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}
\]
Proof.
\[\binom{n}{m}\binom{m}{k}=\frac{n!m!}{m!(n-m)!k!(m-k)!}=\frac{n!(n-k)!}{(n-m)!k!(m-k)!(n-k)!}=\binom{n}{k}\binom{n-k}{m-k}
\]
-
- 二项式定理：
\[\sum_{i=0}^n\binom{n}{i}x^iy^{n-i}=(x+y)^n
\]
-
- 不知名恒等式（2）：
\[\sum_{k\le n}\binom{m+k}{k}=\binom{m+n+1}{n}
\]
Proof.
\[\begin{aligned}
&\sum_{k\le n}\binom{m+k}{k}\\
=&\binom{m}{0}+\binom{m+1}{1}+\binom{m+2}{2}+\dots+\binom{m+n}{n}\\
=&\binom{m+1}{0}+\binom{m+1}{1}+\binom{m+2}{2}+\dots+\binom{m+n}{n}\\
=&\binom{m+2}{1}+\binom{m+2}{2}+\dots+\binom{m+n}{n}\\
=&\dots\\
=&\binom{m+n}{n-1}+\binom{m+n}{n}\\
=&\binom{m+n+1}{n}
\end{aligned}
\]
-
- 不知名恒等式（3）：
\[\sum_{0\le k\le n}\binom{k}{m}=\binom{n+1}{m+1}
\]
Proof.
\[\begin{aligned}
&\binom{n+1}{m+1}\\
=&\binom{n}{m}+\binom{n}{m+1}\\
=&\binom{n}{m}+\binom{n-1}{m}+\binom{n-1}{m+1}\\
=&\dots\\
=&\left(\sum_{1\le k\le n}\binom{k}{m}\right)+\binom{0}{m+1}\\
=&\sum_{0\le k\le n}\binom{k}{m}
\end{aligned}
\]
-
- 范德蒙德卷积
\[\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}
\]
Proof.
直接考虑组合意义，假设有 \(r\) 个黑球与 \(s\) 个白球，一共要选 \(n\) 个球，前者相当于枚举了选择了几个黑球。