某个最大反链问题

给定一个非负整数数列 $\{t_{i}\}$,定义偏序集 $S=\prod_{i=1}^{n}\{x|0\le x\le t_{i},x\in\mathbb{Z}\}$,其中 $\vec{x}\preceq\vec{y}$ 当且仅当 $\forall 1\le i\le n,x_{i}\le y_{i}$。那么 $S$ 的最大反链的大小等于关于 $x_{i}$ 的不定方程 $\displaystyle{\sum_{i=1}^{n}x_{i}=\lfloor\frac{\sum_{i=1}^{n}t_{i}}{2}\rfloor}$ 满足 $\forall 1\le i\le n, 0\le x_{i}\le t_{i}$ 的整数解的个数。

证明:将该问题用整除来描述:设有整数 $n$,考虑其所有约数组成的集合 $S$,定义 $x\preceq y$ 当且仅当 $x\mid y$。定义 $\deg x$ 为其(可重)质因子数。设 $\deg n=m$。定义 $C=\{x|\deg x=\lfloor\frac{m}{2}\rfloor\}$。我们证明,$S$ 的最大反链大小为 $|C|$,其中 $C$ 显然是一个满足要求的解。

定义对称链为一个序列 $d_{1},d_{2},\cdots,d_{h}$,其中 $\deg d_{1}+\deg d_{h}=m$,$\forall 1\le i<h,\frac{d_{i+1}}{d_{i}}$ 为质数。下面证明一个引理:$S$ 可被划分为若干条对称链。

对 $n$ 的质因子数量进行归纳。$n=1$ 时结论显然成立。考虑 $n'=np^{k}$。对于 $S$ 的每条链与 $p^{0},p^{1},\cdots,p^{k}$ 做笛卡尔积,考虑构造出若干条新对称链:

$$ \begin{matrix} d_{1}&d_{2}&\cdots&d_{h}\\ d_{1}p&d_{2}p&\cdots&d_{h}p\\ \vdots&\vdots&\ddots&\vdots\\ d_{1}p^{k}&d_{2}p^{k}&\cdots&d_{h}p^{k} \end{matrix} $$

在上面的矩形中,每次取第一列和最后一行拼接成一条新链,即 $d_{1},d_{1}p,\cdots,d_{1}p^{k},d_{2}p^{k},\cdots,d_{h}p^{k}$,显然这是一条对称链。引理证毕。

在每一条对称链中,至多含有一个 $C$ 中的元素,由于 $\deg$ 对称且连续,至少含有一个 $C$ 中的元素。因而对称链的数量恰为 $|C|$。根据 Dilworth 定理,原命题成立。