2020-2021:teams:intrepidsword:zhongzihao:some_antichain
差别
这里会显示出您选择的修订版和当前版本之间的差别。
|
2020-2021:teams:intrepidsword:zhongzihao:some_antichain [2020/06/12 21:15] admin 创建 |
2020-2021:teams:intrepidsword:zhongzihao:some_antichain [2021/09/16 21:11] (当前版本) toxel fix |
||
|---|---|---|---|
| 行 3: | 行 3: | ||
| 给定一个非负整数数列 $\{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}$ 的整数解的个数。 | 给定一个非负整数数列 $\{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{n}{2}\rfloor\}$。我们证明，$S$ 的最大反链大小为 $|C|$，其中 $C$ 显然是一个满足要求的解。 | + | **证明**：将该问题用整除来描述：设有整数 $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$ 可被划分为若干条对称链。 | 定义对称链为一个序列 $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$ 可被划分为若干条对称链。 | ||
2020-2021/teams/intrepidsword/zhongzihao/some_antichain.1591967741.txt.gz · 最后更改: 2020/06/12 21:15 由 admin
