再谈莫比乌斯反演

待解决问题：偏序集笛卡尔积的时候，为什么莫比乌斯函数可以直接乘起来？ 已解决

摘抄 参考资料: 《组合数学》，机械工业出版社

前面讲了狄利克雷卷积和偏序函数，但都没有讲到莫比乌斯函数是怎么来的。
广义的莫比乌斯函数能在偏序集中定义出来。
哪天搞个构造莫比乌斯函数的题出来玩玩

前置知识: 偏序
一些定义：
$\subset$ 代表真子集，$\subseteq$ 代表子集
用[]括起来的表达式返回内部式子是否成立，成立为1,不成立为0
$\delta(x,y)$表示单位元，即$\delta(x,y)=[x=y]$

从具体的开始考虑。
现在返回容斥原理，这时候偏序的关系为子集关系。
现在有两个函数$F(x),G(x)$(x是集合)，而且有着下面的这种关系：

$$G(x)=\sum_ {k\subseteq x} F(k)$$

现在需要通过$G(x)$求出$F(x)$(比如$G(x)$很好求)
现在我们假设有一个神奇的偏序函数$\mu(x,y)$能够满足以下要求（待会再求解）：

$$F(x)=\sum_ {k \subseteq x} G(k) \times \mu(k,x)$$

代入$G(x)$并化简式子。

$$F(x)=\sum_ {k \subseteq x} (\sum_ {l \subseteq k} F(l))\times \mu(k,x)$$

$$F(x)=\sum_ {k \subseteq x} \sum_ {l \subseteq k} F(l)\times \mu(k,x)$$

$$F(x)=\sum_ {l \subseteq x} F(l) \sum_ {l \subseteq k \subseteq x}\mu(k,x)$$

在普通情况下，左边＝右边时会有以下限制:

$$\sum_ {l \subseteq k \subseteq x}\mu(k,x)=[l==x]$$

这时候会发现$\mu$实际上时可以求出来的。
首先$\forall x,\mu(x,x)=1$
对于某个$x$，满足$|l|=|x|-1)$的集合$l$，他由两个$\mu$加起来并且和为0，而$\mu(l,x)=1$，得到另外一个$\mu(k,x)=-1$
对于满足$|l|=|x|-2)$的集合$l$，因为$k$在遍历$l\subset k,|k|=|x|-1$时有两种情况被减了两次，必须加回一个1才能变回0，所以$\mu(l,x)=1$
…
依次求下去发现$\mu(k,x)$有一个规律：

$$\mu(k,x)=(-1)^ {|x|-|k|}$$

这个就是子集版的莫比乌斯函数，人称容斥系数。

---

考虑把一开始$G(x)=\sum_ {k \subseteq x}F(k)$中的$\subseteq$换成另外一种偏序关系,看看能不能定义出来。
（其实这个就是线性有序集的莫比乌斯函数啦）
换成$\leq$，得到以下式子：

$$G(x)=\sum_ {k \leq x}F(k)$$

现在继续假设有这种$\mu$能够得到以下式子

$$F(x)=\sum_ {k \leq x}G(k)\mu(k,x)$$

按照刚才的套路，带回$G(x)$并化简

$$F(x)=\sum_ {k \leq x} (\sum_ {l \leq k}F(k))\mu(k,x)$$

$$F(x)=\sum_ {l \leq x} F(l)\sum_ {l \leq k \leq x}\mu(k,x)$$

同理$\sum_ {l \leq k \leq x}\mu(k,x)=[l=x]$
根据上面的推法得到$\mu(k,x)$的值:
当$k=x$时,$\mu(k,x)=1$
当$k+1=x$时，$\mu(k,x)=-1$
其他时候$\mu(k,x)=0$
这个是小于等于（线性）版的莫比乌斯函数，人称差分。

---

实际上对于任意的抽象关系$R$，只要存在以下的式子，就可以构造出莫比乌斯函数$\mu$，并根据这个从$G$推回$F$。

$$G(x)=\sum_ {kRx}F(k)$$

把偏序集中的每个元素想象成一个点，若$xRy$，则$x$向$y$连一条边，形成一个DAG。
当$\mu(x,y)$中的y确定时，对于某个能遍历到$y$的点$x$，设$x$能遍历到的集合为$z$，存在一个方程：

$$\sum_ {k \in z} \mu(k,y)=0$$

当$\forall k \in z,\mu(k,y)$确定时，$\mu(x,y)$总是有唯一解。
所以根据拓扑序一定能而且仅能构造出一组$\mu$。

本文到此结束，谢谢大家！
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

别急着拿板砖啊，这的确是莫比乌斯反演，还讲了莫比乌斯函数的来源和构造方法……
国情不对
下面讲另一种理解与构造方式，这次会讲到平常用的数论版本。

---

这里定义两个偏序集$(A,\leq_ A)(B, \leq_ B)$的笛卡尔积为:

$$(\lbrace (A_ 1,B_ 1),(A_ 1,B_ 2),\cdots,(A_ 1,B_ {|B|}),(A_ 2,B_ 1),\cdots,(A_ {|A|},B_ {|B|}) \rbrace, \leq_ A and \leq_ B )$$

就是把A中元素和B中元素组成$|A| \times |B|$个二元组，并将偏序定义为:
对于两个二元组，原来的$A$元素满足$\leq_ A$，原来的$B$元素满足$\leq_ B$时满足此二元组的偏序。

偏序集笛卡尔积起来，莫比乌斯函数是可以直接乘起来的：
($\delta(a,b)$表示单位元$[a=b]$)

$$\begin{aligned} &\sum_{(x_1,x_2)\leq(z_1,z_2)\leq(y_1,y_2)}\mu((z_1,y_1),(z_2,y_2))\\ =&\delta((x_1,x_2),(y_1,y_2))\\ =&\delta(x_1,y_1)\delta(x_2,y_2)\\ =&\left(\sum_{x_1\leq z_1\leq y_1}\mu(x_1,z_1)\right)\left(\sum_{x_2\leq z_2\leq y_2}\mu(x_2,z_2)\right)\\ =&\sum_{x_1\leq z_1\leq y_1,x_2\leq z_2\leq y_2}\mu(x_1,z_1)\mu(x_2,z_2)\\ =&\sum_{(x_1,x_2)\leq(z_1,z_2)\leq(y_1,y_2)}\mu(z_1,y_1)\mu(z_2,y_2)\\ \end{aligned}$$

可以扩展到多个偏序集一起笛卡尔积的情况。
事实上，很多莫比乌斯函数能被构造成多个线性有序集的笛卡尔基，所以可以考虑用笛卡尔积构造莫比乌斯函数。
（这里线性有序集其实是前面讲的$\leq$版的莫比乌斯。）

先考虑容斥的情况。
关于容斥的偏序集中的元素是集合。
设这些集合中出现的元素为$a_ k(1 \leq k \leq n)$
现在把偏序集中的每一个集合想像成一个n维的向量，每一维用01表示该元素是否在这个集合中出现过，如：
$\lbrace a_ 2,a_ 3,a_ 5 \rbrace$写成$[0,1,1,0,1]$
用向量代替原来的集合。
这时候，可以想象成有n个线性有序集笛卡尔积起来构成了这个向量。
这些向量是独立的，根据乘法原理可以得到笛卡尔积起来后的$\mu$
现在有两个向量$a,b$，求$\mu(a,b)$。考虑第$k$维:

• 若$a_ k>b_ k$，则这一维$\mu$是0，使得$\mu(a,b)$总会是0，对应集合$a \not \subseteq b$的情况。
• 若$a_ k=b_ k$，则这一维$\mu$是1,对乘积没有影响。
• 若$a_ k<b_ k$，则这一维$\mu$是-1,对乘积有-1的贡献。

综上，$\mu(a,b)$为0$(a \not \subseteq b)$或-1的【属于b但不属于a的元素个数】次方。
即$\mu(a,b)=(-1)^ {|b|-|a|}$(当a是b子集的时候)，和流传世面的完全一样。

---

现在考虑数论情况。
一个数$x$总是可以被表示成$p_ 1^ {k_ 1}p_ 2^ {k_ 2}\cdots$(p是质数)的形式。
现在想象有一个无限维的向量，第i维的值表示$x$质因数分解后第$i$个质数的幂。
同样地，用向量代替偏序集里的元素，并考虑$\mu$。
现在有两个向量$a,b$，求$\mu(a,b)$。考虑第$k$维:

• 若$a_ k>b_ k$，则这一维$\mu$是0，使得$\mu(a,b)$总会是0，对应元素$a \not | b$的情况。
• 若$a_ k=b_ k$，则这一维$\mu$是1,对乘积没有影响。
• 若$a_ k=b_ k-1$，则这一维$\mu$是-1,对乘积有-1的贡献。
• 若$a_ k<b_ k-1$，则这一维$\mu$也是0。

会发现这里的关系都是相对关系，所以可以令一个新的向量c=b-a（在数值上看就是b/a)，而且只要c某一维<0或>1，$\mu(a,b)$立刻变零。
c上为0的维度是不影响的，为1的维度都会对答案有-1的贡献。

综上，$\mu(a,b)$不为令当且仅当$a|b$且b/a中的每个质因子幂不超过1。
在上述条件下，$\mu(a,b)$为-1的【c的质因子个数】次方。

发现许多$\mu(a,b)$本质上是相同的，可以定义一个新的函数$\mu'$，使得$\mu(a,b)=\mu'(\frac ba)$
这时的$\mu'$就是平常说的莫比乌斯函数。