组合学笔记(五)分配格中的链

---

tags: Combinatorics

写在前面

这一部分主要是计数组合学中的第3.5和3.6节的内容.

分配格的简单性质

容易验证:

• $P$ 的$k$元序理想的个数等于$J(P)$中秩为$k$的元素个数.
• $P$ 中$k$元反链$(k\ge 1)$ 的个数等于 $J(P)$ 中恰好覆盖 $k$ 个元素的元素个数

命题1

设 $P$ 为有限偏序集并且 $m\in \mathbb{N}$, 则下面的数目相等:

1. 保序映射$\sigma :P\to \mathbf{m}$的个数,
2. $J(P)$ 中长为 $m$ 的可重链 $\hat{0}=I_0\le I_1\le \cdot \cdot \cdot \le I_m=\hat{1}$ 的条数,
3. $J(P\times \mathbf{m}-1)$中元素的个数.

证明: (构造双射)

$\sigma :P\to \mathbf{m}$,(偏序集$P$到$m$元链的映射) 定义$I_j={\sigma }^{-1}(\mathbf{j})$, 给定$\hat{0}=I_0\le I_1\le \cdot \cdot \cdot \le I_m=\hat{1}$, 定义$J(P\times \mathbf{m}-1)$的序理想为

$$I=\{(x,y)\in P\times \mathbf{m}-1:x\in I_{m-j}\},$$

定义上述的$\sigma$为: 如果存在$j$使得$(x,j)\in I$, 则$\sigma (x)=\min \{m-j:(x,j)\in I\}$, 若不存在, 则$\sigma (x)=m$. 这构成了满足上条件的双射. 或者直接由$1,3$得到:

$${\mathbf{m}}^P\cong (2^{\mathbf{m}-1}{)}^P\cong 2^{\mathbf{m}-1\times P}.$$

命题2

设 $P$ 为有限偏序集并且 $m\in \mathbb{N}$, 则下面的数目相等:

1. 保序满射$\sigma :P\to \mathbf{m}$的个数,
2. $J(P)$ 中长为 $m$ 的链 $\hat{0}=I_0<I_1<\cdot \cdot \cdot <I_m=\hat{1}$ 的条数.

• $P$到全序的扩张($P$的线性扩张): 如果$|P|=n$,则保序双射 $\sigma :P\to \mathbf{n}$.
• 扩张个数记为$e(P)$,显然等于$J(P)$中极大链的条数.

分配格与格路计数

可以将$P$到全序的扩张$\sigma :P\to \mathbf{n}$等同于$P$中元素的排列: ${\sigma }^{-1}(1),...,{\sigma }^{-1}(n)$, 或者将$J(P)$的极大链等同于下面欧式空间中的"格路".

假设$C_1,C_2,\cdots ,C_k$为$P$的一个链划分, (Dilworth定理推论指出$k$的最小可能值为$P$的反链的最大基数), 定义映射$\delta :J(P)\to {\mathbb{N}}^k$ ,$\delta (I)=(|I\cap C_1|,|I\cap C_2|,\cdots ,|I\cap C_k|)$.

赋予${\mathbb{N}}^k$乘积序, 则$\delta$为一个单的格同态, 且保持覆盖关系, ($J(P)$同构于${\mathbb{N}}^k$)的一个子格, 如果选择每一个$|C_i|=1$, 得到一个保秩的单的格同态$J(P)\to B_n$, 区中$|P|=n$.)

给定$\delta :J(P)\to {\mathbb{N}}^k$, 定义${\Gamma }_{\delta }={\bigcup }_{T}cx(\delta (T))$, 其中$cx$表示${\mathbb{R}}^k$中的凸包而$T$取遍$J(P)$中同构于布尔代数的区间. ${\Gamma }_{\delta }$是${\mathbb{R}}^k$的一个紧多面体子集.

$J(P)$中最长链的数目等于在${\Gamma }_{\delta }$中从原点$(0,0,...,0)=\delta (\hat{0})$到$\delta (\hat{1})$的格路的条数, 每步沿着坐标轴方向移动一个单位.

即, 扩张个数$e(P)$等于将$\delta (\hat{1})$表示为$\delta (\hat{1})=v_1+v_2+\cdots +v_n$的方法数, 其中每一个$v_i$是在${\mathbb{R}}^k$中的一个单位向量, 并且对所有的$i$, 有${\sum }_{k=1}^i{v}_k\in {\Gamma }_{\delta }$.

例1:(不交并)具体问题

对于下面的偏序集, 取$C_1=\{a,c\},C_2=\{b,d,e\}$.

利用前面一小节的方法, 可以容易的找出$J(P)$, 如下图所示, 进行了元素的标记:

通过上面的坐标标记, 可以得到:

从图中的$\varnothing$到$abcde$, 即从$(0,0)$到$(2,3)$,有$9$条可以选择的路, 所以$e(P)=9$.

例2:(不交并)一般的例子

设$P=C_1+C_2$, 且$|C_1|=m,|C_2|=n$, 则${\Gamma }_{\delta }$为一个$m\times n$长方形网格, 于是$e(P)=\left(\genfrac{}{}{0ex}{}{m+n}{n}\right)$, 从线性序扩张角度, 构造$\sigma :P\to \mathbf{m}+\mathbf{n}$, 完全由$\sigma (C_1)$确定, 为$\mathbf{m}+\mathbf{n}$ 的任意$m$元子集, 由此也可以得到$e(P)=\left(\genfrac{}{}{0ex}{}{m+n}{m}\right)$.

推广:

如果$P=P_1+\cdots +P_k,n_i=|P_i|$, 则

$$e(P)=\left(\genfrac{}{}{0ex}{}{n_1+\cdots +n_k}{n_1,\cdots ,n_k}\right)e(P_1)\cdots e(P_k).$$

例3: (笛卡尔积)

设$P=2\times \mathbf{n}$, 取$C_1=\{(2,j):j\in \mathbf{n}\}$, $C_2=\{(1,j):j\in \mathbf{n}\}$, 则$\delta (J(P))=\{(i,j)\in {\mathbb{N}}^2:0\le i\le j\le n\}$. 当$n=3$, 即$P=2\times 3$, 偏序集$P$如下所示:

容易得到$J(P)$如下图:

这等价于不穿过$y=x$且只往上和右走一个格的格路数, 显然图中为$5$. 一般地, $e(2\times \mathbf{n})=\frac{1}{n+1}\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$.

递推关系

将$e$看作$J(P)$上的函数, 即如果$I\in J(P)$, 则$e(I)$表示$I$作为$P$的偏序子集扩张到全序集的个数, 因此$e(I)$等于在$J(P)$中从$\hat{0}$到$I$ 的饱和链的条数. 于是

$$e(I)=\sum _{I^{\prime }}e(I^{\prime }),$$

其中$I^{\prime }$取遍$J(P)$中$I$所覆盖的所有元素, 类似于杨辉三角, $e(I)$就是恰好在$I$下面的$e(I^{\prime })$的和.

一个简单的例子就是$P=\mathbb{N}+\mathbb{N}$, 记$J_f(P)$为$P$的有限序理想构成的格, 则有$J_f(P)\cong \mathbb{N}\times \mathbb{N}$.