OI常用数学公式大全

莫比乌斯反演

$[n=1] = \sum_{d|n}\mu(d)$

$G(n) = \sum_{d|n}F(d) \Leftrightarrow F(n) = \sum_{d|n}\mu(\frac{n}{d})G(d)$

二项式反演

$G(n) = \sum_{i=0}^{n}\tbinom{n}{i}(-1)^{i}F(i) \Leftrightarrow F(n) = \sum_{i=0}^{n}\tbinom{n}{i}(-1)^{i}G(i)$

$G(n) = \sum_{i=0}^{n}\tbinom{n}{i}F(i) \Leftrightarrow F(n) = \sum_{i=0}^{n}\tbinom{n}{i}(-1)^{n-i}G(i)$

$G(n) = \sum_{i=n}\tbinom{i}{n}F(i) \Leftrightarrow F(n) = \sum_{i=n}\tbinom{i}{n}(-1)^{i-n}G(i)$

Min-Max反演

$\max(S) = \sum_{T \subseteq S} (-1)^{|T|+1}\min(T)$

$\min(S) = \sum_{T \subseteq S} (-1)^{|T|+1}\max(T)$

Kth反演

$kthmax(S) = \sum_{T\subseteq S} (-1) ^{|T|-k}\tbinom{|T|-1}{k - 1}\min(T)$

$kthmin(S) = \sum_{T\subseteq S} (-1) ^{|T|-k}\tbinom{|T|-1}{k - 1}\max(T)$

斯特林反演

$F(n) = \sum_{i=0}^{n} \begin{Bmatrix}n\\i\end{Bmatrix} G(i) \Leftrightarrow G(n) = \sum_{i=0}^{n} (-1)^{n-i}\begin{bmatrix}n\\i\end{bmatrix}F(i)$

$F(n) = \sum_{i=0}^{n} (-1)^{n-i}\begin{Bmatrix}n\\i\end{Bmatrix} G(i) \Leftrightarrow G(n) = \sum_{i=0}^{n} \begin{bmatrix}n\\i\end{bmatrix}F(i)$

$F(n) = \sum_{i=n}^{} \begin{Bmatrix}i\\n\end{Bmatrix} G(i) \Leftrightarrow G(n) = \sum_{i=n}^{} (-1)^{i-n}\begin{bmatrix}i\\n\end{bmatrix}F(i)$

$F(n) = \sum_{i=n}^{}(-1)^{i-n} \begin{Bmatrix}i\\n\end{Bmatrix} G(i) \Leftrightarrow G(n) = \sum_{i=n}^{} \begin{bmatrix}i\\n\end{bmatrix}F(i)$