反演
我们再来看看容斥原理实质上发生了什么——根据定义我们有
\[N_\geq(S)=\sum\limits_{S \subseteq J}N_=(J) \]而容斥原理（一般形式）表明
\[N_=(S)=\sum\limits_{J:S \subseteq J \subseteq \mathscr{A}}(-1)^{|J|-|S|}N_\geq(J) \]也就是说，容斥原理其实是由\((1)\)式解出了\((2)\)式，这种本来由一个函数表示另一个函数，现在要反过来由另一个函数来表示原来的函数的变换称为“反演”。
并且我们注意到，这两个式子都是线性的，它们都是关于集合的线性组合。所以我们可以用矩阵乘法来紧凑地表示它们之间的关系。只要我们这样来定义矩阵\(Z\)使得\(N_\geq = ZN_=\)：它的大小应当为\(2^n \times 2^n\)（其中\(n\)是“坏事件”的个数，因此\(2^n\)就表示所有可能的集合\(S\)的总数），元素应当是0或1，分别表示集合的包含关系：我们把所有子集按照一定的顺序排列，那么一个子集就可以一一对应\(1\)到\(2^n\)中的一个数，\(Z(i,j)=1\)当且仅当\(i\)对应的集合包含于\(j\)对应的集合，否则\(Z(i,j)=0\)。比如当坏事件总数为\(3\)时（分别记为\(A,B,C\)），就有：
\[\begin{bmatrix}N_\geq(\{\empty\})\\N_\geq(\{A\})\\N_\geq(\{B\})\\N_\geq(\{C\})\\N_\geq(\{A,B\})\\N_\geq(\{A,C\})\\N_\geq(\{B,C\})\\N_\geq(\{A,B,C\})\\\end{bmatrix} = \begin{bmatrix} 1&1&1&1&1&1&1&1\\ 0&1&0&0&1&1&0&1\\ 0&0&1&0&1&0&1&1\\ 0&0&0&1&0&1&1&1\\ 0&0&0&0&1&0&0&1\\ 0&0&0&0&0&1&0&1\\ 0&0&0&0&0&0&1&1\\ 0&0&0&0&0&0&0&1\\ \end{bmatrix} \begin{bmatrix}N_=(\{\empty\})\\N_=(\{A\})\\N_=(\{B\})\\N_=(\{C\})\\N_=(\{A,B\})\\N_=(\{A,C\})\\N_=(\{B,C\})\\N_=(\{A,B,C\})\\\end{bmatrix} \]正是由于“子集”的性质使得\(Z\)呈现为上三角矩阵，所以\(Z\)可逆，所以我们能够写出
\[N_==Z^{-1}N_\geq \]这就是容斥原理的本质。并且根据容斥原理我们实际上已经求出了\(Z^{-1}\)：\(Z^{-1}(i,j)=(-1)^{k}\)，其中\(k\)为\(j\)对应的集合大小与\(i\)对应的集合大小的差值。\(Z^{-1}\)只会在\(-1,0,1\)间取值。
我们把\(Z\)称为zeta矩阵，\(Z^{-1}\)称为Mobius矩阵。
关联代数
我们知道，容斥原理讨论的“子集的包含关系”实际上是一种特殊的偏序集。因此我们想做推广，在一般的偏序集上实现“容斥原理”。
严格来看，我们只讨论过有限元素的偏序集。但为了方便讨论，我们想把有限偏序集推广到“局部有限的偏序集”，它可能是一个无穷元素的偏序集，但满足“如果任意给定\(x,y \in P\)，则满足\(x \leq z \leq y\)的\(z\)的个数是有限的”。
在无穷情形下，我们就无法再使用“矩阵”这个有限的概念。但我们有相似的概念：定义一个关联代数\(\mathscr{I}(P)\)是一系列\(P \times P \to \R\)的映射，那么对于\(\alpha\in \mathscr{I}(P),x,y \in P\)，定义\(\alpha(x,y) \neq 0 \Rightarrow x \leq y\)，这样\(\alpha(x,y)\)就对应着“矩阵”里的一个元素，\(\alpha\)就是一个无穷的矩阵。对于这个“矩阵”，我们同样可以定义加法和数乘法则，尤其是乘法法则：\((\alpha \beta)(x,y)=\sum\limits_{z}\alpha(x,z)\beta(z,y)\)。如果\(x>y\)或者\(x,y\)不可比较大小，则必须有\((\alpha \beta)(x,y)=0\)；而当\(x \leq y\)时，假如\(z\)与\(x,y\)不可比较大小或者\(x>z\)或\(z<y\)，那么这样的\(z\)产生的贡献一定为0，所以乘法法则的定义可以直接定义为\((\alpha \beta)(x,y)=\sum\limits_{x \leq z \leq y}\alpha(x,z)\beta(z,y)\)。
类似地定义“单位矩阵”\(\delta(x,y)=\mathbb{1}[x=y]\)，于是就可以定义“逆矩阵”\(\alpha^{-1}\)满足\(\alpha \alpha^{-1}=\delta\)。和线性代数中一样，我们可以证明左逆等于右逆，证明“逆”的唯一性——由于我们的“关联代数”是局部有限的，我们对每个取定的\(x,y\)进行证明时都只用到了有限的元素，因此其实本质上最终依然转化为了矩阵的问题，而这些都已经在线性代数中证明了。
莫比乌斯反演
我们在“关联代数”上仿照容斥原理定义zeta函数\(\zeta\)：\(\zeta(x,y)=\mathbb{1}[x \leq y]\)。定义莫比乌斯函数\(\mu=\zeta^{-1}\)。那么偏序集上的“容斥原理”其实就是，在给定函数\(P \to\R\)的两个\(f,g\)（可以看作列数为1的矩阵）满足\(f(x)=\sum\limits_{x \leq y}g(y)\)时，可以把它转化为\(f=\zeta g\)，那么就等价于\(\zeta^{-1}f=g\)，即\(g=\mu f\)。展开即为\(g(x)=\sum\limits_{y}\mu(x,y)f(y)\)。由于只有\(x \leq y\)时关联代数才不为0，因此可以进一步写为\(g(x)=\sum\limits_{x \leq y}\mu(x,y)f(y)\)。这就称为莫比乌斯反演！
关键是要找出\(\mu\)的表达式。因为\(\mu\zeta=\delta\)，因此\(\mu\zeta(x,x)=1\)\(=\sum\limits_{x \leq z\leq x}\mu(x,z)\zeta(x,z)\)\(=\mu(x,x)\zeta(x,x)=\mu(x,x)\)，所以\(\mu(x,x)=1\)。而对于\(x<y\)，\(\mu\zeta(x,y)=0\)\(=\sum\limits_{x \leq z \leq y}\mu(x,z)\zeta(z,y)=\sum\limits_{x \leq z \leq y}\mu(x,z)\)。所以得到\(\sum\limits_{x \leq z < y}\mu(x,z)+\mu(x,y)=0\)，因此\(\mu(x,y)=-\sum\limits_{x \leq z < y}\mu(x,z)\)。尽管这是递归定义，但我们也足够满意了。其余情况\(\mu\)都为\(0\)。这样我们就给出了莫比乌斯函数的表达式：
\[\mu(x,y) = \begin{cases} 0 & \mbox{ if }x\not\le y;\\ 1 & \mbox{ if }x=y;\\ -\sum\limits_{x\le z<y}\mu(x,z) &\mbox{ if }x<y . \end{cases} \]有的时候我们得到的关系不是\(f(x)=\sum\limits_{x \leq y}g(y)\)而是\(f(x)=\sum\limits_{x \geq y}g(y)\)，那么转化为\(\zeta\)函数就必须表示为\(f=\zeta^{\top}g\)，于是\(g=(\zeta^{\top})^{-1}f\)。因为\((\zeta^\top)^{-1}=(\zeta^{-1})^\top=\mu^\top\)，因此\(g=\mu^{\top} f\)，即\(g(x)=\sum\limits_{z}\mu^\top(x,y)f(y)=\sum\limits_{z}\mu(y,x)f(y)=\sum\limits_{y \leq x}\mu(y,x)f(y)\)。
偏序集的乘积
设\((P_1,\leq_1),(P_2,\leq_2)\)，那么定义偏序集的乘积\(P_1 \times P_2 = (P_1 \times P_2, \leq)\)（括号内的\(\times\)指的是笛卡尔积）。其中定义乘积偏序集中的元素\((x_1,y_1)\leq(x_2,y_2)\)当且仅当\((x_1 \leq_1 x_2) \and (y_1 \leq_2 y_2)\)。
可以证明：\(\mu((x_1,y_1),(x_2,y_2))=\mu_1(x_1,x_2) \cdot \mu_2(y_2,y_2)\)。如果\((x_1,y_1) \not\leq (x_2,y_2)\)，那么\(\mu=0\)，此时要么\(x_1 \not\leq_1 x_2\)要么\(y_1 \not\leq_2 y_2\)，因此要么\(\mu_1=0\)要么\(\mu_2 = 0\)，成立。其余情况直接依据定义代入，使用归纳法：\(\mu_1(x_1,x_2)\)\(=-\sum\limits_{x_1 \leq x<x_2}\mu_1(x_1,x)\)，\(\mu_2(y_1,y_2)\)\(=-\sum\limits_{y_1 \leq y<y_2}\mu_2(y_1,y)\)，而\(\mu((x_1,y_1),(x_2,y_2)) =-\sum\limits_{(x_1,y_1)\leq (x,y)<(x_2,y_2)}\mu((x_1,y_1),(x,y))\)。对\((x_1,y_1)\)到\((x_2,y_2)\)的链长归纳（定义为对应偏序集上\(x_1\)到\(x_2\)的链长与\(y_1\)到\(y_2\)的链长之和），那么运用归纳假设就得到上式中\(\mu((x_1,y_1),(x,y))=\mu_1(x_1,x)\cdot\mu_2(y_1,y)\)，因此\(\mu((x_1,y_1),(x_2,y_2)) =-\sum\limits_{(x_1,y_1)\leq (x,y)<(x_2,y_2)}\mu_1(x_1,x)\cdot\mu_2(y_1,y)\)\(=-\left[\left(\sum\limits_{x_1\leq x < x_2}\mu_1(x_1,x)\right)\left(\sum\limits_{y_1\leq y < y_2}\mu_2(y_1,y)\right)+\mu_1(x_1,x_2)\sum\limits_{y_1\leq y<y_2}\mu_2(y_1,y)+\mu_2(y_1,y_2)\sum\limits_{x_1\leq x<x_2}\mu_1(x_1,x)\right]\)\(=-\left[(-\mu_1(x_1,x_2)(-\mu_2(y_1,y_2))-\mu_1(x_1,x_2)\mu_2(y_1,y_2)-\mu_2(y_1,y_2)\mu_1(x_1,x_2)\right]\)\(=\mu_1(x_1,x_2)\cdot\mu_2(y_1,y_2)\)。
由此我们变得非常容易证明最开始的容斥原理：我们定义一个只有两个元素的偏序集\(P(\{0,1\},\leq)\)，其中\(0<1\)。我们对这个偏序集连着乘\(n\)次（这是有定义的，我们每次只乘2个偏序集），得到的偏序集记为\(P^n\)。于是在\(P^n\)中元素可以理解为一个01串，一个串小于等于另一个当且仅当后者为0的地方前者必须是0，后者为1的地方前者可以是0或1——它对应着一个\(2^{[n]}\)中集合的包含关系！那么根据莫比乌斯函数在偏序集乘法中的运算法则，对于两个二进制串（集合）\(x,y\)，就有\(\mu(x,y)=\mu_1(x_1,y_1)\cdots\mu_n(x_n,y_n)\)，而\(\mu_i(0,0)=1\)，\(\mu_i(0,1)=-\mu_i(0,0)=-1\)，因此\(\mu(x,y)=(-1)^k\)，其中\(k\)是\(x,y\)中不同的位数的个数，这恰好对应着我们曾经用二项式定理贡献证明的容斥原理\(N_=(S)=\sum\limits_{J:S \subseteq J \subseteq \mathscr{A}}(-1)^{|J|-|S|}N_\geq(J)\)中的系数\((-1)^{|J|-|S|}\)。
数论莫比乌斯函数
我们曾经看到过自然数上的“整除关系”也是一种偏序。所以我们对于特定的\(n\)可以定义一个偏序集\((D_n, \leq)\)，其中就是所有\(n\)的约数构成的集合，其中\(x \leq y\)当且仅当\(x|y\)。
假如\(n=p^\alpha\)，其中\(p\)是一个素数，那么\(D_n\)中的元素只有\(\{1,p,p^2,\cdots,p^\alpha\}\)。其中的任意两个都可以比较大小，因此这其实是一个全序集，它可以看作指数的序列\(\{0,1,2,\cdots,\alpha\}\)。在这个集合上的莫比乌斯函数\(\mu(x,y)\)满足\(\mu(x,x)=1\)，当\(x>y\)时\(\mu(x,y)=0\)，当\(x < y\)时\(\mu(x,y)=-\sum\limits_{x\leq z<y}\mu(x,z)\)。由于\(\mu(x,y+1)=-\sum\limits_{x \leq z < y+1}\mu(x,z)=-\sum\limits_{x \leq z < y}\mu(x,z)-\mu(x,y)=\mu(x,y)-\mu(x,y)=0\)，而\(\mu(x,x+1)=-\mu(x,x)=-1\)，因此有
\[\mu(x,y) = \begin{cases} 1 & \mbox{ if }x=y;\\ -1 & \mbox{ if }x+1=y;\\ 0 &\mbox{ otherwise}. \end{cases} \]于是对于任意的正整数\(n\)，它可以写成唯一的质因数分解的形式\(n=p_1^{\alpha_1}\cdots p_k^{\alpha_k}\)。它的所有可能的\(D_n\)就是每个\(p_i^{\alpha_i}\)中指数任意取值。这相当于每个\(p_i^{\alpha_i}\)对应的偏序集的笛卡尔积。所以整个偏序集就是这些小偏序集的乘积，要计算它的莫比乌斯函数也就只需要用小的莫比乌斯函数相乘。对于\(x<y\)，有\(\mu(x,y)=\mu_1(x_1,y_1)\cdots\mu_k(x_k,y_k)\)。根据\(p^\alpha\)中莫比乌斯函数的结果，我们需要考察\(y/x\)的质因数分解：\(y/x=p_1^{\beta_1}\cdots p_k^{\beta_k}\)。如果\(\beta_i>1\)，那么\(\mu_i(x_i,y_i)=0\)，直接得到\(\mu(x,y)=0\)。因此对于\(\mu(x,y) \neq 0\)的情况必然要求\(y/x\)只是某一些质数的乘积（指数都为1），当\(\beta_i=0\)时莫比乌斯函数贡献1（相当于没贡献），\(\beta=1\)贡献\(-1\)。综上，\(\mu(x,y)=(-1)^k\)，其中\(k\)为\(y/x\)质因数分解后不同质数的个数。即：
\[\mu(x,y) = \begin{cases} 1 & \mbox{ if } x=y;\\ (-1)^k & \mbox{ if } y/x \mbox{ is the product of } k \mbox{ distinct primes};\\ 0 & \mbox{otherwise.} \end{cases} \]结果表明，\(\mu(x,y)\)只与\(y/x\)有关，它实际上是一个一元函数。所以，我们也常常用\(\mu(x)\)来简记\(\mu(1,x)\)，它们的值是相同的。
由此，我们就可以在研究整除性的领域尝试莫比乌斯反演（容斥原理）。
例如，数论中的欧拉函数\(\varphi(n)\)定义为\(1\)到\(n-1\)中与\(n\)互质的数的个数（规定\(\varphi(0)=1\)）。我们有一个重要的关系\(\sum\limits_{d|n}\varphi(d)=n\)。这个结论可以通过真分数的约分来直观地理解：当\(n\)取12时，所有的真分数\(\dfrac{1}{12},\cdots,\dfrac{11}{12}\)约分后写作：
\(\dfrac{1}{12},\dfrac{1}{6},\dfrac{1}{4},\dfrac{1}{3},\dfrac{5}{12},\dfrac{1}{2},\dfrac{7}{12},\dfrac{2}{3},\dfrac{3}{4},\dfrac{5}{6},\dfrac{11}{12}\)
按分母归类：
\(\dfrac{1}{2};\dfrac{1}{3},\dfrac{2}{3};\dfrac{1}{4},\dfrac{3}{4};\dfrac{1}{6},\dfrac{5}{6};\dfrac{1}{12},\dfrac{5}{12},\dfrac{7}{12},\dfrac{11}{12}\)
由于真分数一定包括了所有与它互质的分子，而真分数的分母又取遍了所有\(n\)的约数（分子至少可以取1），所以这就是\(\sum\limits_{d|n}\varphi(d)=n\)这个关系的直接表达（还要加上\(\varphi(0)=1\)）。
那么，\(\sum\limits_{d|n}\varphi(d)=n\)用整除偏序集的语言来表达就写成\(I(y)=\sum\limits_{x \leq y}\varphi(x)\)，其中函数\(I\)表示自身到自身的映射，\(I(x)=x\)。注意此时是我们刚才提到的不等号方向相反的情况，所以我们要写\(\varphi(x)=\sum\limits_{y \leq x}\mu(y,x)I(y)\)。化简：\(\varphi(n)=\sum\limits_{d|n}\mu(d,n)d\)\(=\sum\limits_{d|n}\mu(\dfrac{n}{d})d\)
于是得到了欧拉函数的一个计算方法：
\[\varphi(n)=\sum\limits_{d|n}\mu(\dfrac{n}{d})\cdot d \] 标签：偏序,limits,leq,dfrac,sum,莫比,mu,反演,乌斯 From： https://www.cnblogs.com/qixingzhi/p/17330150.html