\(P(A|B)=\frac{P(B|A)}{P(B)}P(A)\)
贝叶斯定理，不多谈
\(f(n)=\sum_{i=0}^n \binom i n \times g(i) \Leftrightarrow g(n)=\sum_{i=0}^n \binom i n (-1)^{n-i} f(i)\)
二项式反演,g(i)表示恰好有i,而f(i)表示至多有i
\(f(n)=\sum_{i=n}^m \binom n i \times g(i) \Leftrightarrow g(n)=\sum_{i=n}^m \binom n i(-1)^{i-n} f(i)\)
二项式反演,g(i)同上,f(i)表示至少有i
判定一个数 \(x\) 是否是 \(p\) 的原根： 将 \(p-1\) 分解为 \(p_1^{c_1}p_2^{c_2}\dots p_k^{c_k}\) 的形式，
若对于任意 \(i\) 均满足 \(x^{\frac{p-1}{p_i}} \not≡1\) ，则 \(x\) 是 \(p\) 的原根
\(\begin{bmatrix}n\\ m\end{bmatrix}=\begin{bmatrix}{n-1}\\ {m-1}\end{bmatrix}+(n-1) \times \begin{bmatrix}{n-1}\\ {m}\end{bmatrix}\)
其中 \(\begin{bmatrix}n\\ m\end{bmatrix}\) 表示第一类斯特林数，即 \(n\) 个元素组成 \(m\) 个非空圆排列的方案数。
简略证明：从组合意义上考虑，\(n\) 个元素组成若干圆排列的方案总数就是循环置换的个数，即 \(n!\)
其中 $ \left{ \begin{matrix} n \ m \end{matrix} \right}$ 表示第二类斯特林数，即 \(n\) 个元素划分成 \(m\) 个非空集合的方案数。
略证：从组合意义的角度上进行考虑。
\(\operatorname{m}^{\operatorname{n}}\) 表示 \(\operatorname{n}\) 个格子染色为 \(\operatorname{m}\) 种颜色的方案总数，
枚举染色的颜色个数，后面显然正确
\(\sum_{i=0}^k \binom n i \binom m {k-i}=\binom {n+m}{k}\)
上式即范德蒙德卷积。组合意义证明显然...
\(f(n)=\sum_{i=1}^n \left\{ \begin{matrix} n \\ i \end{matrix} \right\}g(i) \Leftrightarrow g(n)=\sum_{i=1}^n \begin{bmatrix}n\\i\end{bmatrix}(-1)^{n-i}f(i)\)
斯特林反演。证明不会
\(B_{n+1}=\sum_{i=0}^n B_{n-i} \binom n i\)
其中 \(B_i\) 表示贝尔数，即将 \(i\) 个不同数字划分为任意非空集合的方案总数。
至于这个式子可以从组合意义的角度去理解，即枚举第 \(1\) 个数字所在的集合大小，结果就十分显然。
原文：https://www.cnblogs.com/limit-ak-ioi/p/13215293.html