Colex 编码与组合的秩

记 $ℕ$ 为非负整数集合，并固定正整数 $𝑚$ 。长度为 $𝑚$ 的 index set 是 $ℕ$ 的一个 $𝑚$ 元子集；全体这样的集合记为 ${ℐ︀}_{𝑚}$ 。

每个 $𝐴 \in {ℐ︀}_{𝑚}$ 都可以唯一地按严格递减的顺序写成

𝐴 = (𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑚}), 𝑎_{1} > 𝑎_{2} > \dots > 𝑎_{𝑚} \geq 0 .

反过来，每个满足上述条件的序列也唯一确定一个 index set

{𝑎_{1}, 𝑎_{2}, \dots, 𝑎_{𝑚}} .

因此， ${ℐ︀}_{𝑚}$ 与所有长度为 $𝑚$ 的严格递减非负整数序列之间存在一个自然的双射。下文将通过这个双射把二者视为同一个对象：讨论集合运算时使用集合的观点，书写编码时则使用递减序列的观点。

两个集合 $𝐴, 𝐵$ 的对称差 $𝐴 △ 𝐵$ ，是所有只属于其中一个集合的元素组成的集合。对于两个不同的 index set，定义

𝐵 \underset{colex}{<} 𝐴 当且仅当 max (𝐴 △ 𝐵) \in 𝐴 .

也就是说，从最大的整数向下检查两个集合，第一个只属于其中一个集合的整数在哪个集合中，哪个集合就在 colex 序中靠后。这等价于从最大下标开始，按字典序比较两个集合的 0–1 特征序列，因此给出了一个全序。

定义 colex 编码

𝜌_{𝑚 (𝐴)} ≔ \sum_{𝑖 = 1}^{𝑚} (\binom{𝑎_{𝑖}}{𝑚 - 𝑖 + 1}) .

这个公式最直接的解释是： $𝜌_{𝑚 (𝐴)}$ 恰好等于 $𝐴$ 在 colex 序中的前驱数量。

记 $𝒫︀ (𝐴)$ 为 $𝐴$ 的前驱集合。按照对称差最大元素的不同，将它划分为

{𝒫︀}_{𝑖 (𝐴)} ≔ {𝐵 \in 𝒫︀ (𝐴) | max (𝐴 △ 𝐵) = 𝑎_{𝑖}}, 1 \leq 𝑖 \leq 𝑚 .

这个分组条件可以画成下面的形式：

图中，浅绿色表示与 $𝐴$ 一致的固定前缀，浅蓝色表示可变部分。若 $𝐵 \in {𝒫︀}_{𝑖 (𝐴)}$ ，那么 $𝐵$ 在所有大于 $𝑎_{𝑖}$ 的整数上都与 $𝐴$ 一致，并且不包含 $𝑎_{𝑖}$ 。因此，它具有唯一的递减表示

𝐵 = (𝑎_{1}, \dots, 𝑎_{𝑖 - 1}, 𝑏_{𝑖}, \dots, 𝑏_{𝑚}), 𝑎_{𝑖} > 𝑏_{𝑖} > \dots > 𝑏_{𝑚} \geq 0 .

反过来，根据开头建立的双射，每个满足上述条件的递减序列都唯一确定一个 index set $𝐵$ ；它与 $𝐴$ 在 $𝑎_{𝑖}$ 以上完全一致，却不包含 $𝑎_{𝑖}$ ，所以

max (𝐴 △ 𝐵) = 𝑎_{𝑖}

并且 $𝐵 \in {𝒫︀}_{𝑖 (𝐴)}$ 。因此， ${𝒫︀}_{𝑖 (𝐴)}$ 与从

{0, 1, \dots, 𝑎_{𝑖} - 1}

中选取 $𝑚 - 𝑖 + 1$ 个元素的方法一一对应，于是

| {𝒫︀}_{𝑖 (𝐴)} | = (\binom{𝑎_{𝑖}}{𝑚 - 𝑖 + 1}) .

这些集合彼此不交，并且恰好覆盖 $𝒫︀ (𝐴)$ 。由加法原理，

| 𝒫︀ (𝐴) | = \sum_{𝑖 = 1}^{𝑚} | {𝒫︀}_{𝑖 (𝐴)} | = \sum_{𝑖 = 1}^{𝑚} (\binom{𝑎_{𝑖}}{𝑚 - 𝑖 + 1}) = 𝜌_{𝑚 (𝐴)} .

因此，colex 编码并不是一个偶然的组合数公式：它就是 index set 在 colex 序中的秩。

对于固定的 $𝑚$ ，每个 index set 都只有有限多个前驱：若 $𝐵 \underset{colex}{<} 𝐴$ ，则 $𝐵$ 不可能含有大于 $𝑎_{1}$ 的元素。另一方面，固定其余各项并让 $𝑎_{1}$ 增大， $𝜌_{𝑚 (𝐴)}$ 中的

(\binom{𝑎_{1}}{𝑚})

趋于无穷，所以前驱数量没有上界。

现在任取 $𝑛 \in ℕ$ ，选一个至少有 $𝑛$ 个前驱的 $𝐴$ 。有限初始区间

𝒫︀ (𝐴) \cup {𝐴}

中的第 $𝑛 + 1$ 个元素恰好有 $𝑛$ 个前驱，因而编码为 $𝑛$ 。这说明 $𝜌_{𝑚}$ 不会跳过任何非负整数。

此外，若 $𝐵 \underset{colex}{<} 𝐴$ ，那么 $𝐵$ 的所有前驱以及 $𝐵$ 本身都是 $𝐴$ 的前驱，所以

𝜌_{𝑚 (𝐵)} < 𝜌_{𝑚 (𝐴)} .

因此编码保持 colex 序，并且不会重复。

换言之，

𝜌_{𝑚} : ({ℐ︀}_{𝑚}, \underset{colex}{<}) \to (ℕ, <)

是一个序同构。这个结论同时表达了 colex 编码的全部关键性质：编码从 $0$ 开始、没有空缺、没有重复、没有上界，并且编码的数值顺序与 colex 序完全一致。