数学笔记

标签：dbinom limits sum 笔记 kS 反演 iff 数学

反演和容斥

反演本质

反演形如 \(f(n)=\sum\limits_{i=0}^na_ig(i)\iff g(n)=\sum\limits_{i=0}^nb_if(i)\)。实质是：两个函数（数列）之间的双向（求和）关系。

如果定义一个关系矩阵 \(\mathcal A\)，满足 \(f(n)=\sum\limits_{i=0}^ng(i)\mathcal A_{i,n}\)，考虑其实质是向量 \([f_0,f_1,\dots,f_n]=[g_0,g_1,\dots,g_n]\times\mathcal A\)，即 \(F=G\times\mathcal A\)。此时不难逆向的推出 \(G=F\times\mathcal A^{-1}\)。

于是我们就得到了反演的通项，若 \(A\times B=I\)，则 \(f(n)=\sum\limits_{i=0}^ng(i)A_{i,n}\iff g(n)=\sum\limits_{i=0}^nf(i)B_{i,n}\)。

集合反演

\[f(S)=\sum\limits_{T\subseteq S}g(T)\iff g(S)=\sum\limits_{T\subseteq S}(-1)^{|S|-|T|}f(T) \]

\[f(S)=\sum\limits_{T\supseteq S}g(T)\iff g(S)=\sum\limits_{T\supseteq S}(-1)^{|T|-|S|}f(T) \]

二项式反演

\[f(n)=\sum\limits_{i=0}^n\dbinom{n}{i}g(i)\iff g(n)=\sum\limits_{i=0}^n(-1)^{n-i}\dbinom{n}{i}f(i) \]

\[f(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}g(i)\iff g(n)=\sum\limits_{i=0}^n(-1)^i\dbinom{n}{i}f(i) \]

莫比乌斯反演

\[f(n)=\sum\limits_{d|n}g(d)\iff g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d}) \]

其中 \(\mu(n)=\begin{cases}0&\exists p\in\mathbb{P},p^2|n\\(-1)^m&otherwise\end{cases}\)，\(m\) 为 \(n\) 的不同质因子数。

Min-Max 容斥

\[\max\limits_kS=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-k}{k-1}\min\limits_kS \]

\[\min\limits_kS=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-k}{k-1}\max\limits_kS \]

\[E(\max\limits_kS)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-k}{k-1}E(\min\limits_kS) \]

\[E(\min\limits_kS)=\sum\limits_{T\subseteq S}(-1)^{|T|-k}\dbinom{|T|-k}{k-1}E(\max\limits_kS) \]

标签：dbinom,limits,sum,笔记,kS,反演,iff,数学
From： https://www.cnblogs.com/BingAD/p/17359758.html