---

tags: Combinatorics

写在前面

前面铺垫了很多偏序集和格,分配格等的基本知识, 下面开始以这些代数结构为研究对象, 探寻其上的一些性质与关系, 我们先以关联代数的定义开始说起.

关联代数简介

定义

• 令$\mathrm{Int}(P)$表示$P$上所有的区间的集合, (空集不是区间)
• 令$K$为一个域, 定义$f:\mathrm{Int}(P)\to K$, 用$f(x,y)$表示$f([x,y])$.

$P$在$K$上的关联代数$I(P,K)$定义为: 由所有的函数$f:\mathrm{Int}(P)\to K$构成的$K$-代数, 其中乘法(卷积)定义为:

$$(fg)(x,y)=\sum _{x\le {}_{\stackrel{{}_z}{{}^{\cdot }}}\le y}f(x,z)g(z,y).$$

且关联代数$I(P,K)$有双侧单位元的结合$K$-代数, 单位元记为$\delta$或者$1$,定义为

KaTeX parse error: Undefined control sequence: \mbox at position 34: …in{cases} 1, & \̲m̲b̲o̲x̲{if}\ x=y,\\ 0…

取数域$K=\mathbb{C}$即可, 可将$I(P,\mathbb{C})$简记为$I(P)$.

---

另一种表达:

将$I(P,K)$视为由所有的形式表达式:

$$f=\sum _{[x,y]\in \mathrm{Int}(P)}f(x,y)[x,y]$$

组成的, 其中卷积定义如下:

KaTeX parse error: Undefined control sequence: \mbox at position 39: …{cases} [x,w],&\̲m̲b̲o̲x̲{if }y=z,\\[5pt…

并且通过双线性(允许$[x,y]$的无限线性组合)扩展到所有的$I(P,K)$.

有限情形的例子

如果$P$有限, 其中元素记为$x_1,\cdots ,x_n$, 其中$x_i<x_j\Rightarrow i<j$, 于是$I(P)$同构于$\mathbb{C}$上满足: 若$x_i\nleqq x_j$则$m_{ij}=0$的上三角矩阵$M=(m_{ij}),1\le i,j\le n$构成的代数. (可以从$m_{ij}$到$f(x_i,x_j)$建立映射关系)

如果$P$由下图给出, 则$I(P)$同构于形式为

的矩阵构成的代数.

性质

设$f\in I(P)$, 则下面的条件等价:

• $f$有一个左逆元;
• $f$有一个右逆元;
• $f$有一个双侧逆元(必然是唯一的左逆元和右逆元);
• $f(x,x)\ne 0,\forall x\in P$成立.

进一步, 如果$f^{-1}$存在, 则$f^{-1}(x,y)$仅取决于偏序集$[x,y]$.

证明:

设$fg=\delta$, 等价于$\forall x\in P$, 有$f(x,x)g(x,x)=1$, $\forall x,y\in P$, 且满足$x<y$, 有

KaTeX parse error: Limit controls must follow a math operator at position 35: …-1}{\large\sum}\̲l̲i̲m̲i̲t̲s̲_{x

于是$f$有右逆元$g⟺\forall x\in P,f(x,x)\ne 0$, 并且此时$f^{-1}(x,y)$仅取决于$[x,y]$.

同理, 设$hf=\delta$, 即得到$f$有右逆元$⟺\forall x\in P,f(x,x)\ne 0⟺f$有右逆元.

另外, 由$fg=\delta ,hf=\delta$, 得到$g=h$.

关联代数中有用的函数

zeta函数

$\zeta (x,y)=1,\forall x,y\in P,x\le y$. 所以有

KaTeX parse error: Undefined control sequence: \mbox at position 52: …{x\le z\le y}1=\̲m̲b̲o̲x̲{card}[x,y],\\[…

即从$x$到$y$的长度为$k$的可重链的条数. 类似有

( ζ − 1 ) ( x , y ) = { 1 , x < y , 0 , x = y . (\zeta-1)(x,y)=

(ζ−1)(x,y)={1,0,​x<y,x=y.​

于是$(\zeta -1{)}^k(x,y)$是从$x$到$y$的长度为$k$的链$x=x_0<x_1<\cdots <x_k=y$的条数.

下面是$(2-\zeta )(x,y)\in I(P)$,

( 2 − ζ ) ( x , y ) = { 1 , x = y , − 1 , x < y . (2-\zeta)(x,y)=

(2−ζ)(x,y)={1,−1,​x=y,x<y.​

Möbius反演

由上述讨论, 局部有限偏序集$P$的zeta函数$\zeta$可逆, 其逆称为$P$的Möbius函数, 记为$\mu$(或者${\mu }_P$). 通过归纳定义, 可得到:

KaTeX parse error: Expected group after '_' at position 111: … \mu(x,y)=-\sum_̲\limits{x\le z<…

第二个式子可以直接通过$(1)$式代入后展开得到.

Möbius反演公式

设$P$为所有主序理想有限的偏序集, 令$f,g:P\to \mathbb{C}$, 有

$$g(x)=\sum _{y\le x}f(y),\forall x\in P,\text{\hspace{1em}(2)}$$

当且仅当

$$f(x)=\sum _{y\le x}g(y)\mu (y,x),\forall x\in P.$$

这个证明看原版英文书中有一个通过平凡计算证明的方法, 感觉要更好理解一些.(子空间作用有点抽象) 假定$(2)$成立, 则有

∑ y ≤ x g ( y ) μ ( y , x ) = ∑ y ≤ x μ ( y , x ) ∑ z ≤ y f ( z ) = ∑ z ≤ x f ( z ) ∑ z ≤ y ≤ x μ ( y , x ) = ∑ z ≤ x f ( z ) δ ( z , x ) = f ( x )

y≤x∑​g(y)μ(y,x)​=y≤x∑​μ(y,x)z≤y∑​f(z)=z≤x∑​f(z)z≤y≤x∑​μ(y,x)=z≤x∑​f(z)δ(z,x)=f(x)​

其中倒数第二个等号成立是因为:

$$\delta (z,x)=(\zeta \mu )(z,x)=\sum _{z\le y\le x}\zeta (z,y)\mu (y,x)=\sum _{z\le y\le x}\mu (y,x)$$

对偶形式

设$P$为一个所有主对偶序理想$V_x$均有限的偏序集, 令$f,g\in {\mathbb{C}}^P$, 则有

$$g(x)=\sum _{y\ge x}f(y),\forall x\in P,$$

当且仅当

$$f(x)=\sum _{y\ge x}\mu (x,y)g(y),\forall x\in P.$$

一个例子: Möbius反演公式的意义

回忆本章开头的一个例子: 有限集合$A,B,C,D$, 满足:

$$D=A\cap B=A\cap C=B\cap C=A\cap B\cap C,$$

通过容斥原理得到:

∣ A ∪ B ∪ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ − ∣ A ∩ B ∣ − ∣ A ∩ C ∣ − ∣ B ∩ C ∣ + ∣ A ∩ B ∩ C ∣ = ∣ A ∣ + ∣ B ∣ + ∣ C ∣ − 2 ∣ D ∣

∣A∪B∪C∣​=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣=∣A∣+∣B∣+∣C∣−2∣D∣​

下面通过Möbius反演解释上述等式:

给定$n$个有限集合$S_1,...,S_n$, 令$P$为它们所有的交集在包含关系下构成的偏序集, 其中包括空交$S_1\cup \cdots \cup S_n=\hat{1}$, 若$T\in P$, 令$f(T)$表示$P$中属于$T$但不属于任何$T^{\prime }<T$的元素的个数, 令$g(T)=|T|$.

下面通过上述的反演公式找出关于

$$|S_1\cup \cdots \cup S_n|=\sum _{T\le \hat{1}}f(T)=g(\hat{1}),$$

的表达式, 已知:

$$g(T)=\sum _{T^{\prime }\le T}f(T^{\prime }),$$

由$P$上的Möbius反演得到

0 = f ( 1 ^ ) = ∑ T ∈ P g ( T ) μ ( T , 1 ^ ) = ∑ T ≤ 1 ^ g ( T ) μ ( T , 1 ^ ) = g ( 1 ^ ) μ ( 1 ^ , 1 ^ ) + ∑ T < 1 ^ ∣ T ∣ μ ( T , 1 ^ ) ⇒ g ( 1 ^ ) = − ∑ T < 1 ^ ∣ T ∣ μ ( T , 1 ^ ) .

0=f(1^)⇒g(1^)​=T∈P∑​g(T)μ(T,1^)=T≤1^∑​g(T)μ(T,1^)=g(1^)μ(1^,1^)+T<1^∑​∣T∣μ(T,1^)=−T<1^∑​∣T∣μ(T,1^).​

于是, 上面的例子就可以直接由反演公式给出(Hasse图如下), 其中

0 = δ ( A , 1 ^ ) = ( μ ζ ) ( A , 1 ^ ) = ∑ A ≤ z ≤ 1 ^ μ ( A , z ) ζ ( z , 1 ^ ) = μ ( A , A ) ζ ( A , 1 ^ ) + μ ( A , 1 ^ ) ζ ( 1 ^ , 1 ^ ) = 1 + μ ( A , 1 ^ ) ⇒ μ ( A , 1 ^ ) = μ ( B , 1 ^ ) = μ ( C , 1 ^ ) = − 1

0⇒​=δ(A,1^)=(μζ)(A,1^)=A≤z≤1^∑​μ(A,z)ζ(z,1^)=μ(A,A)ζ(A,1^)+μ(A,1^)ζ(1^,1^)=1+μ(A,1^)μ(A,1^)=μ(B,1^)=μ(C,1^)=−1​

0 = δ ( D , 1 ^ ) = ( μ ζ ) ( D , 1 ^ ) = ∑ D ≤ z ≤ 1 ^ μ ( D , z ) ζ ( z , 1 ^ ) = μ ( D , D ) ζ ( D , 1 ^ ) + μ ( D , A ) ζ ( A , 1 ^ ) + μ ( D , B ) ζ ( B , 1 ^ ) + μ ( D , C ) ζ ( C , 1 ^ ) + μ ( D , 1 ^ ) ζ ( 1 ^ , 1 ^ ) = 1 + ( − 3 ) + μ ( D , 1 ^ ) ⇒ μ ( D , 1 ^ ) = 2

0⇒​=δ(D,1^)=(μζ)(D,1^)=D≤z≤1^∑​μ(D,z)ζ(z,1^)=μ(D,D)ζ(D,1^)+μ(D,A)ζ(A,1^)+μ(D,B)ζ(B,1^)+μ(D,C)ζ(C,1^)+μ(D,1^)ζ(1^,1^)=1+(−3)+μ(D,1^)μ(D,1^)=2​