On a question about pattern avoidance of cyclic permutations

本文通过结合循环形式结构分析与迪尔沃斯定理，解决了 Archer 等人提出的关于在循环形式中避免模式 1432 的循环排列计数这一未决问题，并推导出了显式公式。

要点

这篇论文就像是在解决一个**“数学乐高积木”**的难题。

想象一下，你有一堆编号为 $1$到$n$ 的积木块。你的任务是把它们排成一队（这叫**“一行表示”），或者把它们首尾相接围成一个圈（这叫“循环表示”**）。

这篇论文研究的是：在满足两个“游戏规则”的情况下，有多少种合法的排列方式？

1. 游戏规则是什么？

这篇论文设定了两个必须遵守的“禁令”：

• 规则一（一行表示的禁令）： 在排成一队时，不能出现“倒序”的长龙。
  • 比如，如果 $k=3$，你就不能看到像 3, 2, 1 这样越来越小的三个数字连在一起。如果 $k=4$，就不能有 4, 3, 2, 1。这就像是在排队时，不允许出现“高个子、中个子、矮个子”这样连续递减的队形。
• 规则二（循环表示的禁令）： 当你把这些积木围成一个圈，并且从圈里任何位置开始读（就像旋转一个转盘），都不能出现特定的“坏图案”。
  • 这篇论文专门针对的坏图案是 1432。想象一下，你在圈里找四个数字，它们的大小关系要是“小、大、中、中下”（即 $1 < 4 > 3 > 2$ 的相对顺序）。如果不管怎么转圈都找不到这个形状，才算合格。

2. 之前的研究卡在哪里？

之前的数学家（Archer 等人）已经解决了两个类似的“坏图案”（1324 和 1342）的情况，算出了有多少种合法的排法。

但是，对于 1432 这个图案，他们卡住了，留下了一个“未解之谜”。这就好比他们解开了两道数学题，但第三道题的最后一行答案怎么也算不出来。

3. 这篇论文做了什么？

这篇论文的作者（张作如和赵宏宽）成功解开了这个谜题！他们做了一件很酷的事情：

• 拆解结构： 他们发现，如果一个排列要避开"1432"这个坏图案，它的内部结构其实非常严格，就像乐高积木只能按特定的方式拼接一样。
• 引入“尺子”（Dilworth 定理）： 为了处理“规则一”（不能出现太长的倒序），他们借用了一个数学界的强力工具——Dilworth 定理。
  • 通俗比喻： 想象你要把一堆乱序的数字排好。Dilworth 定理告诉你，如果你能把这些数字分成很少的几组“递增序列”（就像把乱书按大小分进几个书架），那么你就一定找不到很长的“递减序列”（倒序）。作者用这个定理证明了：只要结构符合特定要求，就不可能出现太长的倒序。
• 分类讨论： 他们根据第二个数字是谁（比如是 2，是 3，还是更大的数），把问题分成了几个小情况，像剥洋葱一样一层层算出来。

4. 最终结果是什么？

他们不仅解开了谜题，还给出了精确的公式。这就好比你以前只能猜“大概有多少种摆法”，现在他们给了你一把万能钥匙：

• 如果你想知道 $n$ 个积木有多少种摆法，只要把 $n$ 代入他们推导出的公式，就能立刻得到准确答案。
• 对于不同的“倒序长度”限制（$k=3, 4, 5...$），他们分别给出了不同的公式。
  • 当限制比较宽松（$k \ge 5$）时，公式变得非常简洁漂亮。
  • 当限制比较严格（$k=3$ 或 $4$）时，公式稍微复杂一点，但也完全算得出来。

总结

简单来说，这篇论文就像是在**“排列组合”**的迷宫里，找到了一条通往出口的捷径。

• 以前： 面对"1432"这个迷宫，大家只能绕路或者迷路。
• 现在： 作者画出了一张精确的地图（公式），告诉我们只要遵守特定的结构规则，就能轻松避开所有陷阱，并算出总共有多少条路可以走。

这不仅解决了一个具体的数学问题，还展示了如何巧妙地结合结构分析（看积木怎么搭）和经典定理（Dilworth 定理这把尺子）来解决复杂的计数问题。

技术摘要

这是一份关于论文《On a question about pattern avoidance of cyclic permutations》（循环置换的模式避免问题）的详细技术总结。

1. 研究背景与问题定义

核心问题：
该论文旨在解决由 Archer 等人提出的一个未解决的组合计数问题。具体而言，研究的是**循环置换（Cyclic Permutations）**在同时满足以下两个条件时的计数：

1. 单行表示（One-line notation）：避免递减模式 $\delta_k = k(k-1)\cdots 21$（即不存在长度为 $k$ 的递减子序列）。
2. 标准循环形式（Standard cycle form）：其所有循环移位（即所有循环形式）均避免长度为 4 的模式 $\tau = 1432$。

符号定义：

• 设 $A^\circ_n(\delta_k; 1432)$ 为满足上述条件的 $n$ 元循环置换集合。
• 设 $a^\circ_n(\delta_k; 1432)$ 为该集合的大小。
• 作者特别关注 $k \in \{3, 4\}$ 以及 $k \ge 5$ 的情况。

研究动机：
Archer 等人此前已经解决了 $\tau = 1324$ 和 $\tau = 1342$ 的情况，但 $\tau = 1432$ 的情况一直是一个开放问题。Pan 等人曾对此提出过相关猜想并研究了部分特例（涉及 Pell、Tetranacci 和 Padovan 数列），但缺乏通项公式。本文的目标就是彻底解决 $\tau = 1432$ 这一情形。

---

2. 方法论与核心工具

论文采用了结构分析与偏序集理论相结合的方法：

1. 循环形式的结构刻画：

   • 作者首先证明了关键命题（Proposition 2.1）：一个循环置换 $\pi$ 的所有循环形式避免 $1432$，当且仅当其**标准循环形式**$C(\pi)$ 同时避免模式 321 和 2143。
   • 这一转化将复杂的“所有循环移位”条件简化为对单一标准形式的两个模式避免条件，极大地降低了分析难度。

2. Dilworth 定理的应用：

   • 为了处理单行表示中避免 $\delta_k$（递减子序列）的条件，作者引入了偏序集 $S_\pi$。定义 $i \le_\pi j$ 当且仅当 $i \le j$ 且 $\pi_i \le \pi_j$。
   • 根据 Dilworth 定理，一个偏序集中最大反链的大小等于覆盖该集合所需的最小链数。
   • 在单行表示中，长度为 $k$ 的递减子序列对应于偏序集 $S_\pi$ 中大小为 $k$ 的反链。因此，若 $S_\pi$ 能被 $k-1$ 条链覆盖，则 $\pi$ 避免 $\delta_k$。这一工具被用于证明 $k \ge 5$ 时的冗余性。

3. 分类讨论与递推构造：

   • 作者根据标准循环形式 $C(\pi) = (1, j, c_3, \dots, c_n)$ 中第二个元素 $j$ 的值进行分类讨论。
   • 利用双射（Bijection）技术，建立了 $n$ 阶与 $n-1$ 阶置换集合之间的对应关系（例如 Lemma 2.3 和 Lemma 3.1），从而建立递推公式。
   • 对于特定的 $j$ 值，通过构造具体的循环形式并验证其链覆盖性质，计算满足条件的置换数量。

---

3. 主要贡献与定理结果

论文给出了 $n \ge 5$ 时，$a^\circ_n(\delta_k; 1432)$ 的显式公式，分为三种情况：

定理 1.1：当 $k=3$ 时（避免 $\delta_3 = 321$）

• 公式：$a^\circ_n(\delta_3; 1432) = \lfloor \frac{n^2+7}{2} \rfloor - 2n$。
• 对应 OEIS：A061925。
• 推导过程：
  • 将 $j=2$ 的情况归约为 $n-1$ 的情况。
  • 对 $j=3$ 和 $j \ge 4$ 的情况分别进行计数，发现 $j=3$ 时数量为 $\lfloor \frac{n-1}{2} \rfloor$，而 $j \ge 4$ 时数量为 $\lfloor \frac{n-3}{2} \rfloor$。
  • 求和得到最终二次多项式结果。

定理 1.2：当 $k=4$ 时（避免 $\delta_4 = 4321$）

• 公式：$a^\circ_n(\delta_4; 1432) = 2^{n-1} - \lfloor \frac{3n-5}{2} \rfloor$。
• 推导过程：
  • 同样基于 $j$ 的分类。
  • $j=3$ 的情况较为复杂，涉及 $2^{n-4}$ 项以及奇偶性修正项。
  • $j \ge 4$ 的情况通过递推关系和组合数求和得出，最终化简为指数形式减去线性项。

定理 1.3：当 $k \ge 5$ 时

• 公式：$a^\circ_n(\delta_k; 1432) = 2^n + 1 - 2n - \binom{n}{3}$。
• 对应 OEIS：A088921。
• 关键发现（Lemma 4.1）：
  • 作者证明了一个强有力的引理：如果标准循环形式 $C(\pi)$ 避免 $321$和$2143$，那么其单行表示自动避免$\delta_5$（进而避免所有$k \ge 5$ 的递减模式）。
  • 这意味着对于 $k \ge 5$，单行递减限制是冗余的。
  • 计数问题简化为仅考虑循环形式避免 $321$和$2143$ 的循环置换总数，该结果由 Callan 和 Vella 此前给出。

---

4. 研究意义

1. 解决开放问题：成功解决了 Archer 等人留下的关于 $\tau = 1432$ 的开放猜想，完善了循环置换模式避免领域的分类图谱。
2. 方法创新：展示了如何将循环置换的“所有循环移位避免模式”这一全局约束，转化为标准形式的局部模式约束（$321$和$2143$），并结合 Dilworth 定理处理单行表示的递减限制。这种结合偏序集理论与组合结构分析的方法具有推广价值。
3. 揭示结构性质：
   • 揭示了当 $k \ge 5$ 时，避免 $1432$的循环置换在结构上天然地避免了长度为 5 的递减子序列。这一发现简化了高$k$ 值情况下的计数问题。
   • 给出了精确的显式公式，涵盖了二次多项式、指数函数与多项式混合、以及纯组合数形式等多种增长模式，丰富了该领域的序列库（OEIS）。

总结

该论文通过严谨的结构分析和组合论证，彻底解决了循环置换在特定模式组合下的计数问题。其核心贡献在于建立了标准循环形式与所有循环移位避免模式之间的等价性，并利用 Dilworth 定理证明了高长度递减模式限制的冗余性，最终给出了 $k=3, 4$ 及 $k \ge 5$ 三种情况下的精确闭式解。