组合
\(\binom{n}{m} = \binom{n}{n - m}\)。
\(\binom{n}{m} = \binom{n - 1}{m} + \binom{n - 1}{m - 1}\)。这两个都很基础。
\(\binom{n}{m}\binom{m}{k} = \binom{n}{k}\binom{n - k}{m - k}\)。组合意义。
二项式定理：\((x + y) ^ n = \sum\limits_{i = 0} ^ n \binom{n}{i} x ^ i y ^ {n - i}\)。记住这个形式。
\(m\binom{n}{m} = n\binom{n - 1}{m - 1}\)。可以操作系数变换。
\(\sum\limits_{i = 0} ^ n i\binom{n}{i} = n2 ^ {n - 1}\)。可以求导解释。
\(\sum\limits_{i = 0} ^ n \binom{i}{k} = \binom{n + 1}{k + 1}\)。把 \(\binom{k}{k}\) 换成 \(\binom{k + 1}{k + 1}\) 就可以一直加出来了。
扩展：\(\sum\limits_{i = 0} ^ n \binom{i}{s}\binom{n - i}{t} = \binom{n + 1}{s + t + 1}\)。组合意义：在 \(n + 1\) 个里面选 \(s + t + 1\) 个，第 \(s + 1\) 个前面有 \(s\) ge
范德蒙德卷积：\(\sum\limits_{i = 0} ^ k \binom{n}{i} \binom{m}{k - i} = \binom{n + m}{k}\)。直接组合意义 \(n\) 和 \(m\) 个里选 \(k\) 个 / 二项式卷积。
\(\sum\limits_{i = 0} ^ n \binom{n}{i} \binom{i}{k} = \sum\limits_{i = 0} ^ n \binom{n}{k} \binom{n - k}{i - k} = \binom{n}{k} 2 ^ {n - k}\)。
二项式反演
老东西。然后证明方法大概就是直接代入？所以就直接写结论。
主要两种形式。这样观察出来应该更好死记硬背。
\(f_i\) 为至少 \(i\) 个元素，\(g_i\) 为恰好 \(i\) 个元素。
\[f_k = \sum\limits_{i = k} ^ n C(i, k) g_i \]\[g_k = \sum\limits_{i = k} ^ n (-1) ^ {i - k} C(i, k) f_i \]\(f_i\) 为至多 \(i\) 个元素，\(g_i\) 为恰好 \(i\) 个元素。
\[f_k = \sum_{i = 0} ^ k C(k, i) g_i \]\[g_k = \sum\limits_{i = 0} ^ k (-1) ^ {k - i} C(k, i) f_i \] 标签：组合,limits,sum,元素,抽象,binom,二项式 From： https://www.cnblogs.com/liuzimingc/p/18054867/maths