Emerging consecutive pattern avoidance

基本信息

• 论文ID: 2511.02442
• 标题: Emerging consecutive pattern avoidance
• 作者: Nathanaël Hassler, Sergey Kirgizov (Université Bourgogne Europe)
• 分类: math.CO (组合数学), cs.DM (离散数学)
• 发表时间: November 5, 2025 (arXiv预印本)
• 论文链接: https://arxiv.org/abs/2511.02442

摘要

本文研究了渐近流行度(asymptotic popularity)问题，即在避免至少两个长度为3的连续模式的18类排列中，在随机排列的随机位置找到给定连续模式的极限概率。研究表明，对于10类排列，这种流行度可以直接从排列结构推导出来。通过结合解析和双射方法，作者详细研究了两个更复杂的情况。问题对于5类排列仍然开放。

研究背景与动机

研究问题

本文研究排列中连续模式避免(consecutive pattern avoidance)的渐近行为。具体而言：

• 给定避免某些长度为3的连续模式的排列类
• 研究在这些排列类中，其他未被避免的模式的渐近流行度
• 渐近流行度定义为：在大小为n的随机排列的随机位置找到特定模式p的概率，当n趋向无穷时的极限

问题重要性

1. 理论意义：揭示了一个"迷人的事实"——某些模式在渐近意义下会消失（概率趋于0）
2. 扩展经典问题：将Bóna和Homberger关于经典模式（非连续）的研究扩展到连续模式
3. 连接不同组合对象：通过双射建立排列与其他组合结构（如Dyck路径、对合）之间的联系

现有方法局限性

• Bóna和Homberger的工作仅针对经典（非连续）模式
• Kitaev和Mansour虽然给出了18类避免排列的枚举，但未研究渐近流行度
• 缺乏系统的方法处理所有18类排列

研究动机

源于Baril, Burstein和Kirgizov在4中对Class 7的研究，他们使用排列与分散Dyck路径之间的双射来转移模式，这启发了本文的工作。

核心贡献

1. 系统研究18类排列：完整分析了Kitaev-Mansour提出的避免至少两个长度3连续模式的18类排列
2. 解决10个简单类：对10类排列（Classes 1,2,3,5,6,8,9,16,18及已解决的Class 7），直接从结构推导出渐近流行度
3. 深入分析2个复杂类：
   • Class 11 (Av(123,132,321))：结合解析和组合方法
   • Class 17 (Av(123,132))：利用Foata变换与对合的双射
4. 提出开放问题：明确指出5类排列（Classes 10,12,13,14,15）的问题仍然开放
5. 发现模式消失现象：证明在某些类中，特定模式的渐近流行度为0（模式消失）

方法详解

任务定义

输入：

• 排列类 $A_n = \text{Av}_n(p_1, \ldots, p_m)$，避免连续模式 $p_1, \ldots, p_m$
• 未被避免的长度为3的连续模式 $p$

输出：

• 渐近流行度 $\text{pop}_A(p) := \lim_{n \to \infty} \frac{p_n^A}{n|A_n|}$

其中 $p_n^A$ 是模式p在 $A_n$ 中所有排列中的总出现次数。

核心概念

连续模式：排列π包含连续模式p，如果存在连续子序列 $a_i a_{i+1} \cdots a_{i+r-1}$ 与p序同构。

对称操作：

• 反转 R(π)：将排列倒序
• 补 C(π)：将每个元素a替换为n+1-a
• 这些操作保持连续模式的出现

方法分类

1. 结构分析法（简单类）

对于结构简单的排列类，直接从排列形式推导：

Class 1 (Av(123,132,312,321))：

• 仅包含2个交替排列
• 对称性直接给出 pop(213) = pop(231) = 1/2

Class 18 (Av(132,231))：

• 排列形式：$a_1 \cdots a_k 1 b_1 \cdots b_{n-k-1}$
• 其中 $a_1 \cdots a_k$ 递减，$b_1 \cdots b_{n-k-1}$ 递增
• 计数：321的出现次数 = $\sum_{k=1}^{n-1} \binom{n-1}{k}(k-1) = (n-1) \cdot 2^{n-2} - 2^{n-1} + 1$
• 结论：pop₁₈(321) = pop₁₈(123) = 1/2，pop₁₈(213) = pop₁₈(312) = 0

Class 16 (Av(123,321))：

• 利用对称性：类在R, C, R∘C下稳定
• 四个未避免模式通过这些双射一一对应
• 结论：pop₁₆(132) = pop₁₆(231) = pop₁₆(312) = pop₁₆(213) = 1/4

2. 解析方法（Class 11）

Class 11 (Av(123,132,321))：

步骤1：结构分析

• 排列是交替或反交替的
• 从右向左跳过一个元素得到递增序列
• 分为两个子集：$A_n^r$ (最后元素为1) 和 $A_n^l$ (倒数第二元素为1)
• $|A_n^r| = (n-2)!!$，$|A_n^l| = (n-1)!!$

步骤2：模式231的计数 直接观察位置结构： $231_n = (n-1)!! \left\lceil \frac{n-3}{2} \right\rceil + (n-2)!! \left\lceil \frac{n-2}{2} \right\rceil$

步骤3：模式312的递推 建立递推关系（Lemma 3.2）：

• $312_n^r = 312_{n-1}^l$
• $312_n^l = (n-1)(312_{n-2}^l + (n-3)!!) - (n-5)!! \frac{(n-3)(n-2)}{2}$

步骤4：生成函数求解 设 $u_n := \frac{312_n^l}{(n-1)!!}$，得到生成函数： $f(z) = \frac{z(2(z-1)\ln(1-z) + z^3 + 3z^2 - 2z)}{4(1-z)^2(1+z)}$

结论： $312_n^l = (n-1)!! \left( \frac{(-1)^{n-1} + n - 3}{4} + \frac{1}{2} \sum_{\substack{k=1\\k \neq n \bmod 2}}^{n-1} \frac{1}{k} \right)$

渐近结果：pop₁₁(231) = 1/2，pop₁₁(213) = pop₁₁(312) = 1/4

3. 双射方法（Class 17）

Class 17 (Av(123,132))：

核心工具：Foata变换 Claesson证明Foata变换在Av_n(123,132)和对合集合I_n之间建立双射。

标准形式：

1. 每个循环以最小元素开始
2. 循环按最小元素递减排序
3. 去掉括号得到排列

模式对应（Table 2）：

• Av(123,132)中的321 ↔ I_n中的(c)(b)(a)或含不动点的形式
• 231 ↔ (bc)(a⋆)（无不动点）
• 213 ↔ (⋆b)(ac)（无不动点）
• 312 ↔ (⋆c)(ab)（无不动点）

关键引理：

• Lemma 4.2：不动点数量的渐近行为 $\frac{\text{fp}_n}{|I_n|} \sim_{n \to \infty} \sqrt{n}$ 这表明不动点在对合中很稀疏，可忽略含不动点的模式。
• Lemma 4.3：只需计算无不动点模式的流行度

模式231分析（Proposition 4.4）：

• 模式α = (bc)(a⋆)对应两个连续对换
• 每对连续对换恰好产生一个α和一个β或γ
• 结论：pop₁₇(231) = 1/2，pop₁₇(321) = 0

模式213分析（最复杂）：

• 对应Av(123,132)中的模式2314
• 建立递推关系（Lemma 4.5）： $2314_n = 2314_{n-1} + (n-1) \cdot 2314_{n-2} + \binom{n-2}{2}|I_{n-4}|$
• 指数生成函数（Proposition 4.6）： $G(z) = \frac{e^{\frac{(1+z)^2}{2}}}{2} \int_0^z e^{-\frac{(1+t)^2}{2}} dt + \frac{z(z-2)e^{z+\frac{z^2}{2}}}{4}$
• 渐近分析：
  • 第一项：$[z^n]z(z-2)e^{z+\frac{z^2}{2}} \sim \frac{n|I_n|}{n!}$
  • 第二项：使用鞍点方法证明 $[z^n]F(z) = o(\frac{n|I_n|}{n!})$
  • 选择鞍点 $\zeta = \sqrt{n}$ 得到充分的上界

结论：pop₁₇(312) = pop₁₇(213) = 1/4

技术创新点

1. 混合方法：首次系统地结合结构分析、生成函数和双射方法研究连续模式渐近流行度
2. 鞍点方法的创新应用：在Class 17中，通过选择近似鞍点 $\zeta = \sqrt{n}$ 而非精确鞍点，简化了分析
3. 模式转移：利用Foata变换将排列中的模式问题转化为对合中的循环结构问题
4. 不动点稀疏性：证明不动点的 $O(\sqrt{n})$ 增长率使其在渐近分析中可忽略

实验设置

数据来源

本文是纯理论工作，主要基于：

• Kitaev和Mansour关于18类排列的枚举结果
• 已知的生成函数和渐近公式

验证方法

虽然没有传统意义的实验，但作者提到：

• 对Classes 10,12,13,14,15进行了数值实验
• 收敛速度很低，难以形成可信的猜想

实验结果

主要结果（Table 1总结）

关键发现

1. 模式消失现象：
   • 在多个类中，某些模式的渐近流行度为0（如Class 2中的231，Class 17中的321）
   • 这是一个"相当迷人的事实"
2. 对称性结果：
   • Class 16展示了完美的四重对称性（所有四个模式流行度均为1/4）
   • 许多类展示了1/2的对称分布
3. 理性流行度：
   • 所有已解决的情况中，流行度都是有理数（0, 1/4, 1/2, 1）
   • 提出开放问题：是否存在无理数流行度？

相关工作

经典模式避免

• Bóna & Homberger 1,2,3：研究避免一个长度3经典模式的排列类
  • 证明在Av(123)和Av(132)中，321的渐近流行度为1
• Janson 15,16：研究Av(132)和Av(321)中长度3经典模式的极限分布

连续模式研究

• Kitaev & Mansour 17,18,19：给出18类避免排列的枚举（本文的基础）
• Elizalde & Noy 9,10：
  • 基于递增树和盒积的方法
  • Goulden-Jackson簇方法的改编

双射和模式转移

• Barnabei, Bonetti, Silimbani 5：
  • 研究Av(312)中大小3连续模式的联合分布
  • 使用Krattenthaler双射和Deutsch对合
• Baril, Burstein, Kirgizov 4：
  • 研究faro词和排列中的模式统计
  • 本文的直接前驱和动机来源

渐近正态性

• Borga 6：基于生成树研究避免某些模式的排列中连续模式出现的渐近正态性

结论与讨论

主要结论

1. 完整性：系统解决了18类中的13类（10个简单+2个复杂+1个已有）
2. 方法论：展示了结构分析、生成函数和双射方法的有效结合
3. 理论洞察：揭示了模式消失和对称性等有趣现象

局限性

1. 未完成的工作：5类排列（Classes 10,12,13,14,15）仍然开放
2. 数值困难：这些开放类的收敛速度很低，难以通过数值实验提出猜想
3. 方法限制：现有方法似乎不足以处理剩余的复杂情况

未来方向

作者在Section 5提出了若干开放问题：

1. Conjecture 5.1：如果popₐ(p) = 0，那么对于避免p的子类B，有popB(q) = popₐ(q)
   • 这在已解决的情况中成立
2. 扩展问题：
   • 仅避免一个长度3连续模式时会发生什么？
   • 能否找到产生无理数渐近流行度的模式集？
   • 极限(1.1)是否总是存在？如何刻画存在性？
3. 方法论问题：
   • 如何用枚举或概率方法解决剩余5类？
   • 是否存在统一的框架处理所有情况？

深度评价

优点

1. 系统性强：
   • 首次系统研究18类排列的渐近流行度
   • 清晰的分类和方法论（简单vs复杂）
2. 方法多样：
   • 灵活运用结构分析、生成函数、双射、鞍点方法
   • Class 17的分析特别精巧，展示了多种技术的有机结合
3. 理论深度：
   • Lemma 4.2关于不动点稀疏性的证明优雅
   • 生成函数的推导严谨（特别是Class 11的微分方程）
4. 写作清晰：
   • 结构良好，从简单到复杂
   • Table 1提供了清晰的总览
   • 图示（Figures 1-2）帮助理解

不足

1. 完整性：
   • 5类问题未解决（占总数的28%）
   • 没有提供这些困难情况的深入分析或部分结果
2. 数值支持：
   • 虽然提到数值实验，但未展示具体数据
   • 缺少收敛速度的量化分析
3. 猜想验证：
   • Conjecture 5.1仅在已解决情况验证，缺乏更广泛的证据
4. 技术细节：
   • Class 17中鞍点选择 $\zeta = \sqrt{n}$ 的动机可以更详细
   • 某些计算步骤跳跃较大

影响力

1. 理论贡献：
   • 开辟了连续模式渐近流行度的系统研究
   • 为模式避免理论提供了新视角
2. 方法论价值：
   • 展示了多种技术的有效结合
   • 模式转移思想可应用于其他组合结构
3. 启发性：
   • 提出的开放问题明确且有趣
   • 可能激发新的研究方向
4. 局限性：
   • 主要是理论结果，实际应用不明显
   • 剩余问题的困难可能限制短期影响

适用场景

1. 组合数学研究：
   • 排列模式理论
   • 渐近枚举
   • 生成函数方法
2. 算法设计：
   • 受限排列生成
   • 模式匹配算法
3. 相关领域：
   • 可能对统计物理中的受限模型有启发
   • 与基因组学中的模式避免问题相关

参考文献

关键参考文献：

1. 4 Baril, Burstein, Kirgizov (2021)：本文的直接动机来源
2. 17 Kitaev (2003)：18类排列的枚举基础
3. 7 Claesson (2001)：Foata变换双射（Class 17的关键）
4. 1-3 Bóna & Homberger (2010-2012)：经典模式的先驱工作
5. 11 Flajolet & Sedgewick (2005)：解析组合学的标准参考

总体评价：这是一篇扎实的组合数学论文，系统地研究了一个自然且有趣的问题。方法论上展示了多种技术的有效结合，特别是Class 11和17的分析体现了深厚的技术功底。虽然有5类问题未解决，但已完成的工作为该领域建立了坚实基础。论文写作清晰，结果有趣（特别是模式消失现象），提出的开放问题明确且富有挑战性。对于组合数学特别是排列模式理论的研究者，这是一篇值得深入阅读的论文。