一些有用的结论。
二项式反演
$$
F(n) = \sum _ {i = 0} ^ n (-1) ^ i \binom n i G(i) \Longleftrightarrow G(n) = \sum _ {i = 0} ^ n (-1) ^ i \binom n i F(i) \tag 1
$$
$$
F(n) = \sum _ {i = 0} ^ n \binom n i G(i) \Longleftrightarrow G(n) = \sum _ {i = 0} ^ n (-1) ^ {n - i} \binom n i F(i) \tag 2
$$
$$
F(n) = \sum _ {i = n} (-1) ^ i\binom i n G(i) \Longleftrightarrow G(n) = \sum _ {i = n} (-1) ^ i \binom i n F(i) \tag 3
$$
$$
F(n) = \sum _ {i = n} \binom i n G(i) \Longleftrightarrow G(n) = \sum _ {i = n} (-1) ^ {i - n} \binom i n F(i) \tag 4
$$
可以拓展到高维，以第四个式子为例：
$$
F(n, m) =\sum _ {i = n} \sum _ {j = m} \binom i n \binom j m G(i, j) \Longleftrightarrow G(n, m) = \sum _ {i = n} \sum _ {j = m} (-1) ^ {i + j - n - m} \binom i n \binom j m F(i, j)
$$
二项式定理：
$$
(a + b) ^ n = \sum _ {i = 0} ^ n \binom n i a ^ i b ^ {n - i}
$$
有关组合数和幂的形式可以考虑构造二项式定理消去组合数。
组合恒等式
$$
\binom{n}{m}=\binom{n}{n-m}\tag{1}
$$
$$
\binom{n}{k} = \frac{n}{k} \binom{n-1}{k-1}\tag{2}
$$
$$
\binom{n}{m}=\binom{n-1}{m}+\binom{n-1}{m-1}\tag{3}
$$
$$
\binom{n}{0}+\binom{n}{1}+\cdots+\binom{n}{n}=\sum_{i=0}^n\binom{n}{i}=2^n\tag{4}
$$
$$
\sum_{i=0}^n(-1)^i\binom{n}{i}=[n=0]\tag{5}
$$
$$
\sum_{i=0}^m \binom{n}{i}\binom{m}{m-i} = \binom{m+n}{m}\ \ \ (n \geq m)\tag{6}
$$
$$
\sum_{i=0}^n\binom{n}{i}^2=\binom{2n}{n}\tag{7}
$$
$$
\sum_{i=0}^ni\binom{n}{i}=n2^{n-1}\tag{8}
$$
$$
\sum_{i=0}^ni^2\binom{n}{i}=n(n+1)2^{n-2}\tag{9}
$$
$$
\sum_{l=0}^n\binom{l}{k} = \binom{n+1}{k+1}\tag{10}
$$
$$
\binom{n}{r}\binom{r}{k} = \binom{n}{k}\binom{n-k}{r-k}\tag{11}
$$
$$
\sum_{i=0}^n\binom{n-i}{i}=Fibonacci_{n+1}\tag{12}
$$