反演公式总结

##定义

$$G_n=\sum _{i=0}^n{a}_{n,i}{F}_i$$
$$F_n=\sum _{i=0}^n{b}_{n,i}{G}_i$$

可认为$a$、$b$是两个下三角矩阵，且$a\cdot b=I$

###二项式反演
$$G_n=\sum _{i=0}^n\left(\genfrac{}{}{0ex}{}{n}{i}\right)F_i⟺G_n=\sum _{i=0}^n(-1{)}^{n-i}(\genfrac{}{}{0ex}{}{n}{i})F_i$$

###斯特林反演
$$G_n=\sum _{i=0}^n\left\{\begin{array}{c}n\\ i\end{array}\right\}{F}_i⟺F_n=\sum _{i=0}^n\left[\begin{array}{c}n\\ i\end{array}\right]G_i$$

###莫比乌斯反演
$$f_n=\sum _{d|n}{g}_d⟺g_n=\sum _{d|n}{\mu }_{\frac{n}{d}}{f}_d$$

###集合形式

$$g_S=\sum _{T\subseteq S}{f}_T⟺f_S=\sum _{T\subseteq S}(-1{)}^{|S|-|T|}{g}_T$$

###最值反演
max ⁡ { S } = ∑ T ⊆ S ( − 1 ) ∣ T ∣ − 1 min ⁡ { T } max{S}=sum_{Tsubseteq S}(-1)^{|T|-1}min{T} max{S}=T⊆S∑​(−1)∣T∣−1min{T}
###推广
$$kth\max (S)=\sum _{T\subseteq S}(-1{)}^{|T|-k}(\genfrac{}{}{0ex}{}{|T|-1}{k-1})\min (T)$$

最后

以上就是听话曲奇为你收集整理的反演公式总结的全部内容，希望文章能够帮你解决反演公式总结所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。