← 返回 PaperDaily
大模型与智能体
排列模式的终极分类就差一步！论文攻克两大猜想
见过给“排列”分门别类搞到只差最后一格就完美收官的数学难题吗？这篇论文就做到了！不仅武断地搞定两个纠结多年的猜想，还把整个分类棋盘压到了最后一个“未解之谜”。对搞理论的人来说，这简直是教科书级的“破局”示范，每一个证明技巧都值得点赞。
龙哥读论文
发布于 2026-08-14 09:10:37
阅读 3
查看原文
🐉 龙哥读论文知识星球来了！ 公众号每日8篇拆解不够看？星球 无上限更AI领域论文、资讯、招聘、招博、开源代码， 一站式干货，每日2分钟刷完即赚！ 👇扫码加入「龙哥读论文」知识星球，前沿干货、实用资源一站式拿捏～
龙哥推荐理由：
原论文信息如下：
排列（Permutation） ：简单说，就是1到n的一个打乱顺序，比如n=4时，2 1 4 3就是一个排列。经典模式（Classical Pattern） ：在一个较长的排列中，找出一段子序列，它们数值的相对大小顺序正好和某个较短排列一模一样。比如排列2 1 4 3里，子序列2 1 3就构成了一个“132”模式。网格模式（Mesh Pattern） ：这是经典模式的升级版。在排列的点阵图上，额外指定一些“禁止进入”的阴影区域。只有那些不触碰阴影区域的子序列才算有效出现。相当于给模式加了“规矩”，让匹配更严格。为了描述方便，论文中用下面这张图来展示一个长度为2的网格模式例子，其中黑色圆点代表排列中的两个数字，灰色格子表示“禁止区”。
Wilf等价 ：两个模式p1和p2，如果对于任意长度n，完全避免 这两个模式的排列个数相等，就说它们是Wilf等价的。粗一点说，就是“避免它们的排列数一样多”。分布等价（Equidistribution） ：比Wilf等价更强。不仅要求避免者的数量一样，而且对于任意出现次数k，包含恰好k个该模式的排列个数也要对应相等。也就是说，两个模式在整个排列集合上的计数分布完全一样。分布等价是Wilf等价的“豪华加料版”，证明起来也更难。目前长度2的网格模式共有2^12 = 4096种（因为每个阴影格有两种选择），但经过对称性简化后，等价类的个数是大家追逐的目标。
网眼模式分类的终极挑战：仅差最后一步！ 长度2的网格模式分类问题，已经有好几年的历史了。2015年Hilmarsson等人带头研究，后来不断完善，到最近Su、Kitaev、Zhang（2025年）的工作把分布等价类的上界降到了108，Wilf等价类的上界降到49，并下界分别猜为105和46。研究就像在迷雾中拼图，剩下几块最难啃的骨头。
重庆大学、斯特拉斯克莱德大学、天津师范大学的合作团队，在这篇论文中一口气砸下了两记重拳，分别搞定了一个2019年的猜想和一个2025年的最新猜想。这使得分布等价类的上界降到106，Wilf等价类的上界降到47，一下子和下界只差一个！
目前唯一的悬念就剩Class 69 （包含4个模式），如果证实它们也分布等价，那么所有分类就完美收官：dist = 105, wilf = 46。是不是很刺激？就差临门一脚！
构造巧妙对合，攻克多年猜想：两个长度2的网眼模式分布等价 第一个突破来自Class 54 ——它由8个模式组成，分成两个4模式子类，内部已经通过简单的对称操作（如逆、补、反）证明了等价。难的是跨越子类的等价。论文选取了两个代表性模式：p1和p2（见下面公式截图）。
这个对合的核心思想是找到排列中的“锚点”（anchor），即第一个能构成模式p1或p2的元素a。论文通过两个引理证明：一旦排列中出现了p1或p2，这个a是唯一确定的，并且必然在第一个位置。然后根据排列中“最大左部元素”（mla）与a的大小关系，分两种情况进行“值移位”：将区间内的数值进行平移，使得p1的阴影条件和p2的阴影条件互相转换。
论文用下面的图（Figure 1）展示了一个具体例子：σ = (10)821796453 通过φ变成τ = 4251(10)39786，并且p1在σ中的出现位置{7,10}正好对应p2在τ中的出现位置{7,10}。
这个构造直接证实了1999年Hilmarsson等人提出的猜想（后来由Su等人重新强调为Conjecture 2）。从此Class 54内部的8个模式全部分布等价，它们合并成一个等价类，不再成为疑点。
定义双射映射，统一六大模式：Class 71 全部等价 第二个突破是Class 71 ，它有6个模式，分为一个2模式子类和一个4模式子类。团队选取p3（来自第一子类）和p4（来自第二子类），设计了一个保持“从右到左最大值集合”的双射ψ。
从右到左最大值（RLMax）指的是：从排列最右边向左看，每次遇到比之前所有元素都大的元素，就记为一次。这些值构成一个递减列表。论文把排列按照RLMax分解成“N块+M块+r块”的结构，然后巧妙地将所有N块逆序排放到开头，同时保持M块和r块的顺序不变。
论文通过深入分析p3和p4的阴影约束，证明（a,b）构成p3出现当且仅当（a,b）在像中构成p4出现，并且保持RLMax不变。这个双射是满射且可逆，从而一次性统一了Class 71的全部6个模式。至此，2025年的最近猜想被直接攻克。
Figure 3给出了一个具体数值实例（σ=14 12 10 15 11 9 13 7 2 6 4 3 8 1 5），其中p3的出现{(14,15), (9,13), (7,8), (1,5)}对应到τ中的p4出现。
三管齐下，攻克遗留分布：Class 54, 60, 75 枚举完成 除了分类，论文还补上了三个重要模式的完整分布公式 （原来只已知避免计数，不知道出现次数分布）。
对于p5（Class 54的代表模式），分布生成函数通过分两种情形（C块是否包含模式“+”）得到双重求和公式。这里利用了长度1网格模式（即单点+阴影）已有的分布结果（Lemma 3.1来自[7]）。公式中T_m和S_k分别是长度1模式“+”的分布和避免序列。
对于p6（Class 60代表），论文发现一个简洁的计数公式：
Class 75的避免者超级简单：0个和1个排列，但分布却需要引入一个辅助变量h（表示“可容许位置个数”）来递归求解。递推关系如下：
分类近乎完美，仅剩一个未解之谜 经过本文的贡献，长度2网格模式的等价类边界被大幅收紧。表1总结了枚举贡献：
目前分布等价类的上下界分别为：105 ≤ dist ≤ 106；Wilf等价类的上下界：46 ≤ wilf ≤ 47。唯一的悬念就是Class 69 ，它包含四个模式，其中两个通过逆补操作已经等价，另两个也彼此对称，真正需要证明的是子类之间的分布等价。这个猜想最早在2019年提出，如果一旦解决，dist = 105, wilf = 46，分类完美收官。
论文作者也指出，这个猜想可能涉及更复杂的结构，或许需要引入新的组合工具。
未来方向：从全排列到对合，新的挑战与启发 论文在结尾处提出了深化方向：对于更小的对象——对合（involution） （即排列与自身逆序相同的特殊排列），相同的分类问题是否也能解决？作者猜测，Class 69的分布等价在对合中也成立。如果证实，意义不言而喻：模式分类从全排列延伸到更广的组合结构。
从方法论上看，本文的“值移位”对合和“RLMax保持”双射都是值得学习的思路。它们充分利用了网格模式特有的阴影约束来构造一一对应，这不仅适用于长度2，也可能为长度3的模式分类提供启发。
当然，目前最引人入胜的挑战就是证明或证伪Class 69的分布等价 。对这个难题感兴趣的朋友可以直接挑战，说不定下一个重大突破就是你！
龙迷三问 问题1：什么叫网格模式？和经典模式有什么不同？
问题2：分布等价和Wilf等价有什么区别？
问题3：Class 69为什么是最后的未解之谜？
如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~
龙哥点评 论文创新性分数： ★★★★★
对合和双射的构造非常巧妙，尤其是“值移位”思路一反常规，让人眼前一亮。解决了两个悬而未决的猜想，把分类推向只差一步的完美局面。
实验合理度（此处指理论证明严谨度）： ★★★★★
所有定理都有完整的形式化证明，引理支撑充分，组合论证清晰，没有漏洞。虽然是纯数学，但严谨性无可挑剔。
学术研究价值： ★★★★★
填补了网格模式分类的关键空白，建立了分类的几乎完整图景。对于组合数学中的模式回避理论有重要推进，为后续研究提供了经典范例。
稳定性（指理论结果的鲁棒性）： ★★★★★
数学结论是确定性的，不依赖随机性。一旦证明成立就永远成立，稳定性极高。
适应性以及泛化能力： ★★★☆☆
目前的证明紧紧针对长度2网格模式，推广到长度3可能需要全新工具。但思想（如值移位、RLMax分解）可以借鉴。
硬件需求及成本： ★★★★★
纯理论研究，不需要任何计算硬件，纸笔加头脑即可。
复现难度： ★★★★☆
证明已经写得很详细，但需要一定组合数学基础才能完整理解。可以复现但需要耐心。
产品化成熟度： ★☆☆☆☆
纯数学理论，不直接产生商业产品。但其分类结果可能间接影响算法设计中的模式匹配复杂度分析。
可能的问题： 唯一遗憾是Class 69的谜底仍未揭开，使得分类还差一步。对于非专业读者，理解证明细节的门槛较高。
主要参考文献
[1] Brandén, P., Claesson, A. (2011). Mesh patterns and the expansion of permutation statistics. European J. Combin., 32(6), 858-877. [2] Chen, Y., Fan, N., Ye, F. (2025). Zero-one Grothendieck polynomials and pattern avoidance. arXiv:2503.XXXXX. [5] Hilmarsson, J., Jónsdóttir, K., Sigurðardóttir, R., et al. (2015). Wilf-classification of mesh patterns of length 2. Discrete Math. Theor. Comput. Sci., 17(3), 75-100. [6] Kitaev, S. (2011). Patterns in Permutations and Words. Springer. [7] Kitaev, S., Zhang, Z. (2019). Distributions of mesh patterns of length 1 and 2. J. Combin. Theory Ser. A, 167, 1-35. [15] Su, X., Kitaev, S., Zhang, Z. (2025). On distribution and Wilf-equivalence of mesh patterns of length 2. Adv. in Appl. Math., 152, 102654. [9] Knuth, D. E. (1973). The Art of Computer Programming, Vol. 3: Sorting and Searching. Addison-Wesley. *本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～ 想了解更多原文细节的小伙伴，可以点击 "阅读原文"， 查看更多原论文细节哦！
