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

---

tags: Combinatorics写在前面

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

分配格的简单性质

容易验证:

的元序理想的个数等于中秩为的元素个数.中元反链的个数等于中恰好覆盖命题1

设 为有限偏序集并且 , 则下面的数目相等:

保序映射的个数,中长为的可重链中元素的个数.

证明: (构造双射)

,(偏序集到元链的映射) 定义, 给定, 定义的序理想为

定义上述的为: 如果存在使得, 则, 若不存在, 则. 这构成了满足上条件的双射. 或者直接由得到:

命题2

设 为有限偏序集并且 , 则下面的数目相等:

保序满射的个数,中长为的链到全序的扩张(的线性扩张): 如果,则保序双射.扩张个数记为,显然等于中极大链的条数.分配格与格路计数

可以将到全序的扩张等同于中元素的排列: , 或者将的极大链等同于下面欧式空间中的"格路".

假设为的一个链划分, (Dilworth定理推论指出的最小可能值为的反链的最大基数), 定义映射 ,.

赋予乘积序, 则为一个单的格同态, 且保持覆盖关系, (同构于)的一个子格, 如果选择每一个, 得到一个保秩的单的格同态, 区中.)

给定, 定义, 其中表示中的凸包而取遍中同构于布尔代数的区间. 是的一个紧多面体子集.

中最长链的数目等于在中从原点到的格路的条数, 每步沿着坐标轴方向移动一个单位.

即, 扩张个数等于将表示为的方法数, 其中每一个是在中的一个单位向量, 并且对所有的, 有.

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

对于下面的偏序集, 取.

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

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

从图中的到, 即从到,有条可以选择的路, 所以.

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

设, 且, 则为一个长方形网格, 于是, 从线性序扩张角度, 构造, 完全由确定, 为 的任意元子集, 由此也可以得到.

推广:

如果, 则

例3: (笛卡尔积)

设, 取, , 则. 当, 即, 偏序集如下所示:

容易得到如下图:

这等价于不穿过且只往上和右走一个格的格路数, 显然图中为. 一般地, .

递推关系

将看作上的函数, 即如果, 则表示作为的偏序子集扩张到全序集的个数, 因此等于在中从到

其中取遍中所覆盖的所有元素, 类似于杨辉三角, 就是恰好在下面的的和.

一个简单的例子就是, 记为的有限序理想构成的格, 则有.