Median-Extremes Alternation

论文技术总结：中极交替排列 (MEA)

1. 问题背景与定义

本文研究了一类由确定性规则生成的排列族，称为中极交替排列 (Median-Extremes Alternation, MEA)，记为 $\pi_n \in S_n$。

• 构造过程：从有序列表 $R_0 = (1, 2, \dots, n)$ 开始，交替执行两种操作，直到列表为空：
  1. 中位步骤 (Median Step)：移除当前列表的中间元素（若长度为奇数则移除唯一中间值；若为偶数则移除中间两个值，按从左到右顺序）。
  2. 极值步骤 (Extreme Step)：移除当前列表剩余元素中的最小值和最大值（按先最小后最大的顺序）。
• 输出：按移除顺序记录的值构成排列 $\pi_n$。
• 初始性质：由于过程总是以中位步骤开始，随后的极值步骤总是作用于偶数长度的列表，因此每次极值步骤恰好移除两个值。

2. 方法论

作者采用递归分解作为核心证明工具。

• 递归结构分析：通过观察 $\pi_n$ 的前几个元素（前缀），发现剩余部分可以通过重新标记（rank-shifting）映射到规模更小的 MEA 排列（$\pi_{n-2}$ 或 $\pi_{n-4}$）。
• 奇偶性分类讨论：将 $n$ 分为奇数 ($n=2m+1$) 和偶数 ($n=2m$) 两种情况，分别推导递归公式。
• 归纳法证明：利用上述递归结构，对排列的交替性质、逆序数及逆排列进行数学归纳证明。

3. 主要贡献与结果

(1) 精确的递归结构 (Exact Recursive Structure)

文章建立了 $\pi_n$ 的递归分解公式，表明每个 MEA 排列由一个依赖于 $n$ 奇偶性的短前缀和一个经过秩偏移（rank-shifted）的较小 MEA 排列的尾部组成。

• 当 $n = 2m + 1$ (奇数)：
  $$\pi_{2m+1} = [m+1, 1, 2m+1] \parallel T_{2m+1}$$
  其中 $T_{2m+1}$ 是 $\pi_{2m-2}$ 的秩偏移版本（元素 $r \le m-1$ 映射为 $r+1$，否则映射为 $r+2$）。
• 当 $n = 2m$ (偶数)：
  $$\pi_{2m} = [m, m+1, 1, 2m] \parallel T_{2m}$$
  其中 $T_{2m}$ 是 $\pi_{2m-4}$ 的秩偏移版本。

(2) 交替排列性质 (Alternating Structure)

证明了所有 MEA 排列均为交替排列 (Alternating Permutations)，其类型完全由 $n$ 的奇偶性决定：

• 若 $n$ 为奇数：$\pi_n$ 为下 - 上型 (Down-Up)，即 $\pi_n(1) > \pi_n(2) < \pi_n(3) > \dots$。
• 若 $n$ 为偶数：$\pi_n$ 为上 - 下型 (Up-Down)，即 $\pi_n(1) < \pi_n(2) > \pi_n(3) < \dots$。
• 推论：$\pi_n$ 的下降集 (Descent Set) 被完全确定：
  • $n$ 为奇数时，$Des(\pi_n) = \{1, 3, 5, \dots, n-2\}$。
  • $n$ 为偶数时，$Des(\pi_n) = \{2, 4, 6, \dots, n-2\}$。

(3) 逆序数公式 (Inversion Number)

推导出了 $\pi_n$ 逆序数 $inv(\pi_n)$ 的精确闭式公式：
$$inv(\pi_n) = \left\lfloor \frac{(n-1)^2}{4} \right\rfloor$$
具体分为：

• $n = 2m+1 \implies inv(\pi_n) = m^2$
• $n = 2m \implies inv(\pi_n) = m(m-1)$
• 序列特征：该序列对应 OEIS A002620（四分之一平方数序列：0, 0, 1, 2, 4, 6, 9, ...）。

(4) 排列符号 (Sign of the Permutation)

基于逆序数公式，确定了 $\pi_n$ 的符号 $sgn(\pi_n) = (-1)^{inv(\pi_n)}$：

• $\pi_n$ 为奇排列当且仅当 $n \equiv 3 \pmod 4$。
• 其他情况下 ($n \equiv 0, 1, 2 \pmod 4$)，$\pi_n$ 均为偶排列。

(5) 逆排列的递归描述 (Recursive Description of the Inverse)

文章给出了逆排列 $\pi_n^{-1}$ 的精确递归构造方法。通过反转前缀元素的映射关系和尾部的秩偏移，可以递归地构建 $\pi_n^{-1}$。

• 例如，对于奇数 $n=2m+1$，前缀元素 $m+1, 1, n$ 分别位于位置 $1, 2, 3$，其余元素的位置由$\pi_{2m-2}^{-1}$ 经过偏移得到。

4. 示例数据

前几个 MEA 排列如下：

• $\pi_1 = [1]$
• $\pi_2 = [1, 2]$
• $\pi_3 = [2, 1, 3]$ (逆序数 1)
• $\pi_4 = [2, 3, 1, 4]$ (逆序数 2)
• $\pi_5 = [3, 1, 5, 2, 4]$ (逆序数 4)
• $\pi_6 = [3, 4, 1, 6, 2, 5]$ (逆序数 6)

5. 意义与展望

• 理论意义：尽管构造规则极其简单（仅涉及中位和极值的交替移除），但生成的排列族展现出惊人的刚性结构。它们自然地落入交替排列的范畴，且具有精确的递归结构和简单的逆序数公式。
• 研究价值：该工作为组合数学提供了一个新的确定性排列族，其逆序数与著名的“四分之一平方数”序列直接相关。
• 未来方向：
  • 寻找 $\pi_n$ 和 $\pi_n^{-1}$ 的非递归显式公式。
  • 研究 $\pi_n$ 的循环结构 (Cycle Structure) 及其迭代阶数。
  • 探索 MEA 排列的逆序图 (Inversion Graphs) 是否具有极值图论意义。
  • 与其他交替排列子类进行更深入的比较。

总结：David Carr 的这篇论文通过严格的递归分析，揭示了一个简单构造规则下隐藏的深刻组合规律，确立了 MEA 排列作为一类具有精确统计性质和递归结构的交替排列族在组合数学中的地位。