数学相关

• 子集反演

$$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}$$

• • 二项式定理：

$$\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}$$

• • 不知名恒等式（3）：

$$\sum_{0\le k\le n}\binom{k}{m}=\binom{n+1}{m+1}$$

• • 范德蒙德卷积

$$\sum_{k=0}^n\binom{r}{k}\binom{s}{n-k}=\binom{r+s}{n}$$