← 返回 PaperDaily 大模型与智能体

南开大学最新组合数学：6ℓ对模式全分类，Qiu-Remmel猜想被证

这是一篇热度很高的纯数学新作。南开大学与思克莱德大学团队把“同时避开一个长度三经典模式与一个平偏序模式”的6ℓ对配置完整分类，顺手证明了Qiu-Remmel猜想，还修正了原文关键错误。最令人拍案的是：排除等价类居然动用了素数定理级别的数论工具，组合与数论在同一个舞台相遇。

龙哥读论文发布于 2026-08-25 00:20:00 阅读 2 查看原文

#人工智能 #AI科研

paperdaily_reaction_gif

原论文信息如下：

论文标题:
Wilf Equivalence for Length-Three Patterns and Flat POPs, and a Conjecture of Qiu and Remmel

发表日期:
2026年08月

发表单位:
南开大学（组合数学中心、LPMC）、思克莱德大学（数学与统计系）

原文链接:
https://arxiv.org/pdf/2608.18461v1.pdf

引言

先问一个简单的问题：把1到n这n个数字排成一排，有多少种排法？答案当然是n!。但如果加上一条规矩：不允许出现某种“小规模相对顺序”，结果会变成什么样？这就是组合数学里著名的“模式避免排列”问题。

考虑长度为3的模式τ。如果某个排列中能找到三个位置，它们之间的相对大小关系和τ一模一样，就说这个排列“包含”模式τ；如果找不到，就说它“避免”模式τ。那么问题来了：长度为n的排列中，有多少个避免123的？又有多少个避免132的？

答案是同一个数：第n个卡特兰数。无论τ是123、132还是别的什么长度3模式，避免它的排列数量全都一样多。这组经典结果是排列模式理论中最著名的定理之一，当年由高德纳（Knuth）在他的《计算机程序设计艺术》中系统整理过。卡特兰数本身也非常有意思：1, 2, 5, 14, 42, 132……它出现在括号配对、二叉树计数、多边形三角剖分等一大堆看似毫不相干的场景里。

既然避免不同模式得到的计数相同，人们自然要问：这些“长得不一样但计数一样”的模式之间，到底有什么关系？于是就有了Wilf等价的概念：如果两个模式集合对应的避免排列数量对每个n都相等，就说它们是Wilf等价的。经典结果告诉我们，所有6个长度3的模式，反演、补、逆这些对称操作已经给出了两大类；而两个大类之间也存在着非平凡的计数等价，对应的双射工具数不胜数。

本文讨论的问题，是把“只避免一个模式”升级成“同时避免两个模式”：一个经典长度3模式τ，加上一个叫做“平偏序模式”的新对象P_{ℓ,x}。这样的组合一共有6ℓ对，看似杂乱的6ℓ对配置，最终被证明恰好分成2ℓ−1个Wilf等价类（ℓ≥4时）。这个“完全分类”的结果本身已经很漂亮，更精彩的是证明过程——双射、精确枚举、卡特兰三角数、甚至素数论里的素数定理轮番上阵。

组合数学中的Wilf等价：一个完整的分类框架

本文的核心对象是排列、经典模式、偏序模式（POP）以及Wilf等价。先梳理这几个基本概念，再进入具体证明，会更清晰。

一个长度为n的排列，就是把{1,2,…,n}重新排个序。例如π=24153就是一个长度为5的排列。排列之间有几种自然的对称操作：逆（reverse）把整个序列倒过来写；补（complement）把每个数字k变成n+1−k；还有逆序（inverse）操作。这些操作都不会改变“是否包含某个模式”的性质，所以它们天然地给出Wilf等价。

经典的偏序模式（POP）把“模式”的概念大大推广了。传统模式要求选出的子序列各元素之间满足一个全序关系，而POP只要求满足一个偏序关系。也就是说，有些元素之间必须满足大小关系，有些则无所谓。本文研究的P_{ℓ,x}是一类特殊的“平POP”：ℓ个位置里，第x个位置上的数必须比其他所有数都小，其他位置之间没有任何约束。这个“唯一指定最小”的结构虽然看起来简单，却蕴含着非常丰富的计数行为。

$图1：平偏序模式P_{ℓ,x}的示意图$

图1：平偏序模式P_{ℓ,x}的示意图

前面说到，避免任意一个长度3经典模式的排列数都等于卡特兰数，这是排列模式理论最经典的风景。但真正的数学乐趣，往往从“加码”开始：如果要求一个排列同时避开两个模式，情况会怎样？

本文研究的正是这个“加码”版本：排列要同时避开一个经典长度3模式τ和一个平偏序模式Pℓ,x。这里τ有6种，而Pℓ,x由两个参数决定——长度ℓ和特殊位置x（1≤x≤ℓ），因此总共有6ℓ种组合。对一个组合(τ,Pℓ,x)，用sn(τ,Pℓ,x)表示长度为n且同时避开这两个模式的排列个数。所谓Wilf等价，就是两个组合对所有n的计数都相等。

这6ℓ对配置，看似一大盘散沙。但论文给出了一个极其干脆的主定理：当ℓ≥4时，6ℓ对恰好分成2ℓ−1个Wilf等价类；当ℓ=3时，特殊地只有4个类。为什么ℓ=3这么特殊？后面会专门解释。

对于ℓ≥4的完整分类，论文用一张表就讲清楚了。表中的符号看起来有点多，但拆开看非常漂亮：Eℓ是单元素类；Aℓ,2是个四元素类；Aℓ,r（3≤r≤ℓ）每个类含两个元素；Bℓ,r（1≤r≤ℓ−1）则全部是单元素类。数一下：1 + (ℓ−1) + (ℓ−1) = 2ℓ−1，正好对上。

$表1：ℓ≥4时(τ,P_{ℓ,x})对的Wilf等价类$

表1：ℓ≥4时(τ,Pℓ,x)对的Wilf等价类

注意最后一列还贴心地标出了每个等价类的出处定理。想要验证的同学可以直接去论文里对号入座。

从经典模式到偏序模式：研究问题的自然延伸

要理解这个分类的价值，先得理解Pℓ,x这个“平偏序模式”到底是个什么来头。传统经典模式在选出的子序列上强加的是一个全序关系——任意两个元素之间都必须满足确定的大小方向。而偏序模式（partially ordered pattern，简称POP）则温和得多：它只要求其中一部分元素对满足大小关系，其余元素对可以“摆烂”，不做任何约束。经典模式其实是POP的一个特例，对应的是一个全序链。

Pℓ,x的定义用一句话说就是：在一个长度为ℓ的子序列中，第x个位置上的数必须是所有ℓ个数中最小的，其他位置之间没有任何关系。论文把这种恰好指定一个最小者的POP称为“平POP”（flat POP）。别小看这个看似“放了水”的约束——它把经典模式那种严格的“形状匹配”变成了更具几何意味的“象限条件”。

$Q_{II}(i)定义：第i个点第二象限中的点数$

QII(i)的定义：第i个点左上方（第二象限）所包含的点数。这里用Pπ(j)表示数值j在排列π中的位置。

看到这个公式，很多熟悉组合计数的读者会心一笑：这不就是逆序表（inversion table）的变体嘛。确实如此。论文把这层几何联系点破之后，Pℓ,x的避开条件就有了一个干净的翻译：π避开Pℓ,x，当且仅当不存在任何点i同时满足QII(i) ≥ x−1 且 QI(i) ≥ ℓ−x。换句话说，禁止某个点上方的两个象限同时“太挤”。一个本来看起来很“代数”的模式避免问题，就此转换成一个可以用几何直观看图说话的统计问题。

更有意思的是，Pℓ,x还与一类叫做象限标记网格模式（quadrant marked mesh patterns，简称MMP）的对象一一对应。MMP是Kitaev、Remmel和Tiefenbruck等人系统研究过的一套统计工具，用四个象限各自应满足的点数条件来定义一种“局部几何约束”。平POP的“第x位最小”条件，恰好就是MMP(a,b,0,0)中参数取特殊值的产物。于是，避开Pℓ,x的计数问题，就翻译成了MMP统计量取值为0的计数问题。这种翻译看似只是换了个马甲，却为后面用生成函数和分布理论打开了一扇门。

双射构造与精确枚举：分类证明的核心技术

确定了分类目标之后，接下来的问题就是：怎么证明两个组合真的Wilf等价？又怎么证明它们真的不等价？对于前者，最令人信服的工具当然是双射——直接构造两个避免类之间的一一对应。论文在这部分展现了相当精巧的“手艺活”。

先看最简单的一类等价。由于逆（reverse）、补（complement）和逆序（inverse）这三种对称操作天然保持模式包含关系，所以它们能自动生成一批Wilf等价。比如把排列倒过来写，避开(231,Pℓ,1)的排列就一一对应到避开(213,Pℓ,ℓ)的排列——本质上就是把Pℓ,x的“最小位”从左边翻到右边。这些“免费午餐”直接构成了表1中的若干等价关系。

真正考验功力的是那些不依赖对称操作的等价。比如(231,Pℓ,1)和(231,Pℓ,2)这对——它俩在表1中同属于Aℓ,2类。论文构造了一个非常直观的双射：如果排列π中QII(1)≤ℓ−3，说明整体“左上角压力”不大，那么π已经自动避开Pℓ,ℓ−1（经逆补操作转化为Pℓ,2），直接原样返回；如果QII(1)=ℓ−2，则说明1的左上角恰好卡在临界值。此时可以证明1,2,…,k会形成一个连续的递增块，排列被唯一分解为π = A 1 2 ⋯ k B（其中|A|=ℓ−2）。双射的核心操作就是把这块连续递增块“摘下来”，倒序放到B的后面，得到σ = A B k(k−1)⋯2 1。

图2：从π到σ的映射φ。左边是原排列π，右边是映射后的排列σ。直观上，就是把左上角“顶着压力”的那段递增区块拆下来，倒着放到末尾。

这个映射妙在“一刀切”：它把π中唯一违反Pℓ,ℓ−1的隐患——那个左上角积压了ℓ−2个点的位置1——通过翻转整块连续递增序列，把“压力”转化成了对Pℓ,ℓ−1的安全避让。论文随后用引理2.2中的QII单调性作为桥梁，证明σ仍然避开132（逆补后对应231），同时也避开了Pℓ,ℓ−1。逆映射可以完全对称地定义回去，于是双射成立。这种“把局部结构的压力释放到全局”的构造思路，在双射证明里可以说是教科书级别的示范。

再看另一组关键等价：(321,Pℓ,x)和(231,Pℓ,x)（2≤x≤ℓ）。论文定义了两个看起来很“暴力”的映射Φ和Ψ：对每个i，把排列中点i的第二象限里的所有元素分别按递减序（φ⟨i⟩）或递增序（ψ⟨i⟩）重新排列，然后按i=1,2,…,n依次作用，复合得到Φ和Ψ。

Φ和Ψ的定义：逐点重排第二象限元素的复合映射。

这个操作看起来像在“洗牌”，但它有一个漂亮的解释：一个排列避开231，当且仅当每个点的第二象限子词都是递减的；避开321，当且仅当每个点的第二象限子词都是递增的。Φ做的事情，就是把一个321-避开排列中所有“不够递减”的局部子词统统掰成递减序，从而把它送进231-避开类；Ψ则是反方向操作。论文还证明了这两个映射是互逆的双射，并且揭示了一个更深的联系：rev ∘ Φ ∘ rev 恰好等于经典的Simion-Schmidt双射（后者是连接123-避开排列与132-避开排列的著名构造）。也就是说，这个看似新造的Φ，其实是经典Simion-Schmidt双射在镜像下的化身。能看出这一层，说明作者对经典文献的理解相当通透。

后半段“不存在其他等价”的证明，走的是另一条路：精确枚举。只要能算出每个候选类的计数，并且发现它们在某个长度n处不相等，就能干净利落地排除等价关系。论文推导了一堆递推关系：例如aℓ,x(n)满足一个把问题分解成首元素位置的递推方程，在n=ℓ时得到简洁的闭合公式，n=ℓ+1时又得到另一个公式。这些公式里卡特兰数Ck的卷积随处可见，组合直觉敏锐的同学一眼就能看出这些递推背后的“首元素分解”结构：按排列中最小元素1所在的位置切开，左右两边的子排列各自独立满足约束。

$a_{ℓ,x}(n)的递推关系$

aℓ,x(n)的递推关系：按最小元素1的位置，将问题分解为左右两个子问题。

这里有一个值得注意的细节：为了避免歧义，论文在处理长度3模式时经常改用其逆序、补运算后的等价形态。比如研究(123,Pℓ,ℓ)时，利用对称操作转化成(321,Pℓ,ℓ−1)等更顺手的形式。这种“怎么方便怎么来”的变形，恰恰体现了对称工具在模式避免研究中的杠杆作用。

素数因子论证：区分等价类的关键工具

如果只是推公式算计数，这篇论文固然扎实，但还算不上惊艳。真正让龙哥拍大腿的，是最后用来区分两类“顽固候选”的工具——素数因子论证。

故事是这样的：有些候选等价类之间的计数非常接近，常规的递推和闭合公式只能在某个区间内区分它们。比如要证明(213,Pℓ,1)和(321,Pℓ,r)（r≥3）不等价，需要证明某个形如CaCℓ−1−a = (y/ℓ)·C(2ℓ−y−1, ℓ−1)的方程在特定参数范围内没有整数解。这种方程看起来简单，真证起来却非常棘手。

论文的思路是：假设方程有解，把等式两边关于某个关键变量做大素数因子分析——具体来说，就是考察等式两边在“局部”的素因子分解结构是否匹配。如果能找到一个大素数p，它整除左边却无论如何不可能整除右边，矛盾就出现了。论文巧妙地把问题转化成一个Diophantine方程无解的问题，并把这个无解性的验证范围压缩到一个界：ℓ≥3,274。这个数不是拍脑袋来的，它来自对素数分布下界的精细估计。

素数分布下界公式：X到X(1+1/(2(ln X)²))之间必有素数。这个由素数定理推出的估计，正是素数因子论证能“锁死”区间的原因。

这个上界3,274被作者自己“不客气”地指出未必是紧的。也就是说，他们选了一个方便证明的界，而不是最优的。这种“我明知道界可以改进，但这样一个界就足够完成证明”的坦诚，在数学论文里显得格外清爽——人家根本不打算硬凑一个漂亮的数，够用就好。

可以想象，当评审人第一次看到组合等价类的证明里突然冒出一个“素数定理”和一个“3,274”时，内心大概也是这个表情——毕竟组合数学里动用解析数论工具的情形并不多见。这也正是这篇论文最有“反差感”的地方：前半段还是双射和卡特兰数你侬我侬的古典风景，后半段画风一转，直接搬出素数分布的大炮来打蚊子，关键是还真打着了。

这种跨领域的“降维打击”不是炫技，而是被问题逼出来的：当所有常规的组合计数手段都用尽之后，素数因子论证提供了唯一能区分某些候选类的途径。它本质上是在说：如果不能从计数上区分两个类，那就从数论上区分——很多看似势均力敌的组合等式，在素因子层面立刻露出马脚。

从回避问题到分布问题：Qiu-Remmel猜想的解决

分类定理本身已经足够撑起一篇好论文，但这篇的野心显然不止于此。论文的后半部分把问题从“回避计数”升级到了“分布理论”。所谓分布，就是不仅关心MMP统计量是否为0，还要关心它取每个非负整数k时各有多少排列。用生成函数的话说，就是要研究

$Q_{n,τ}^{(a,b,c,d)}(q)的定义：统计量为k的排列数作为q的系数$

Qn,τ(a,b,c,d)(q)的定义：统计量为k的排列数作为q的系数。

$回避计数到分布生成函数的联系：s_n(τ,P_{ℓ,x})是q^0的系数$

回避计数到分布生成函数的联系：sn(τ,Pℓ,x)正是分布生成函数中q⁰的系数。这个等式把回避问题和分布理论无缝对接。

沿着这个方向，论文解决了一个悬而未决的猜想：Qiu-Remmel猜想。Qiu和Remmel在2021年前后研究123-避开排列上的象限标记网格模式分布时，提出了一个大胆猜测：对每个k≥1，两种参数设置(0,k,∅,0)和(1,k−1,∅,0)产生的MMP统计量在132-避开排列上有完全相同的分布。用前文的记号写出来就是：

Qiu-Remmel猜想公式：两种MMP参数的分布在132-避开排列上相同。

这个猜想直觉上很“反直觉”：参数(0,k,∅,0)考察的是左上象限里至少k个点，而(1,k−1,∅,0)考察的是左上象限至少1个点、上方象限（第一象限）至少k−1个点——这两套约束听起来完全不像一回事，但Qiu和Remmel在大量数值证据的支撑下大胆猜测它们分布相同。

本文不仅证明了这一猜想，还在过程中发现了Qiu-Remmel原论文中的一处关键错误。这个错误出现在他们推导的核心引理中，直接影响猜想证明的可靠性。论文先修正了这个错误——注意是“修正”而不是“回避”——然后在修正后的框架上完成了完整证明。这一波操作堪称“打补丁式研究”的正面案例：没有因为原论文有错就绕道而行，而是直接下场把地基修好，再在地基上盖楼。

更妙的是，Qiu-Remmel猜想的证明反过来给出了(231,Pℓ,1)和(231,Pℓ,2) Wilf等价的一个非双射证明——而论文在前文已经用双射独立证明了同一件事。同一事实，两条路径，一条靠构造，一条靠生成函数，互相印证。这种“双保险”的安排让读者对结论的信心直接拉满。

研究启示与未来方向

这篇论文的价值远不止于“把一个分类问题做完了”。它展示了模式避免领域里一种越来越重要的研究范式：经典模式与推广模式（POP、MMP等）混合配对，然后系统枚举所有组合的等价类。这类问题有两个天然的难点——一是等价性的正向证明需要足够精巧的双射；二是不等价性的反向证明通常需要精细的计数。而本文在后者上更进一步，引入了数论工具，为这类“计数卡脖子”的困境提供了一种新解法。

素数因子论证的适用范围并不局限于平POP。任何涉及卡特兰数（或更一般的组合数）等式的Wilf等价判定问题，都可以尝试用类似的手段：把等式两边的素因子结构摊开对比，寻找“不可调和的素数”。当然，这个方法也有客观限制——它依赖于具体组合数的分解性质，不是万能钥匙。

另外，ℓ=3的例外情形也值得玩味。为什么其他ℓ都是2ℓ−1个类，偏偏ℓ=3只有4个类？因为长度3的排列空间实在太小，一些在更大长度下“应该”不同的计数撞在了一起。这提示我们：在探索这类分类问题时，小参数边界的“异常现象”往往不是错误，而是通往更深结构的线索。计算一下就知道，ℓ=3时2ℓ−2=4和2ℓ−1=5只差1个类，差的那个类正是在Pℓ,x和经典模式(312)、(321)的交互中“吞并”了。

未来还有几个自然的方向：一是把经典模式从长度3扩展到长度4甚至更长——复杂度会指数级上升，但分类框架应该仍然适用；二是把平POP换成其他结构的POP——比如允许同时指定多个“最小位”或“最大位”；三是把素数因子论证的界3,274改进到更优，虽然作者自己说“不追求sharp”，但一个更紧的界对这个方法在其他问题上的应用可能会产生实际帮助；第四，Qiu-Remmel猜想被证明后，一个更广泛的猜想网络也随之浮现——不同MMP参数在各类避开类上的分布等价关系，是否会形成某种统一的规律？这些都是值得后续研究者接力的开放命题。

最后说一句大实话：这篇论文的阅读门槛不算低，它面向的是组合数学特别是模式避免方向的读者。如果读者只是好奇卡特兰数是什么，那么引言部分已经足够；但如果想完整走一遍6ℓ对分类的核心证明，需要一定的排列模式和生成函数功底。龙哥的建议是：先读第2节的三个关键双射（Theorems 2.1、2.3、2.8），理解“怎么证等价”；再读第3节的计数递推，理解“怎么证不等价”；最后再看素数因子论证如何收尾。这样一条路线走下来，既能感受到古典双射之美，也能体会到现代数论工具的锋利，绝对值回票价。

龙迷三问

下面是龙哥对于大家可能的一些问题的解答：

这篇论文到底在解决什么问题？南开与思克莱德团队完成同时避开长度三经典模式与平偏序模式的全部6ℓ对配置的Wilf等价分类，ℓ≥4时恰好2ℓ−1个等价类，并顺带解决Qiu-Remmel猜想、修正原文错误。素数论证与双射方法同台，过程十分精彩。

这篇工作最值得看的点是什么？论文通过严格的数学证明完成了对6ℓ个配对的完整Wilf等价分类，对于ℓ≥4得到2ℓ-1个等价类，对于ℓ=3得到4个等价类，并解决了Qiu-Remmel猜想。

这篇工作的边界或风险在哪里？优点：1) 问题定义清晰，分类结果完整且具有一般性；2) 证明方法多样，结合了双射构造、精确枚举、递推关系和素数因子论证等多种技术；3) 解决了领域内的公开猜想。缺点：1) 论文中使用的素数因子论证中的界限3,274并非最优，可能可以通过更精细的分析改进；2) 部分证明依赖计算机辅助验证，缺乏纯理论证明。

如果你还有哪些想要了解的，欢迎在评论区留言或者讨论~

龙哥点评

论文创新性分数：★★★★☆

通过双射构造、精确枚举、递推关系及素数因子论证，对长度为3的经典模式与平坦偏序模式(POP)组成的6ℓ个配对进行完整的Wilf等价分类，并解决Qiu-Remmel猜想。

实验合理度：★★★☆☆

现有材料未完整覆盖数据划分、基线公平性和统计显著性，因此按中性评价处理。

学术研究价值：★★★★☆

通过双射构造、精确枚举、递推关系及素数因子论证，对长度为3的经典模式与平坦偏序模式(POP)组成的6ℓ个配对进行完整的Wilf等价分类，并解决Qiu-Remmel猜想；更关键的是问题定义是否可复用到同类任务。

稳定性：★★★☆☆

现有材料未提供充分的极端条件、重复运行或扰动测试，稳定性暂按中性评价。

适应性以及泛化能力：★★★☆☆

现有材料未完整展示跨数据集、跨场景或分布外实验，泛化能力仍需进一步验证。

硬件需求及成本：★★★☆☆

现有材料缺少完整训练资源、参数量、显存和推理时延信息，成本暂按中性评价。

复现难度：★★★☆☆

现有材料未确认完整代码、配置、数据处理脚本和权重是否齐备，复现难度暂按中性评价。

产品化成熟度：★★★☆☆

论文验证以研究实验为主，真实部署中的时延、成本、维护和异常场景仍需补充验证。

可能的问题：定义清晰，分类结果完整且具有一般性；2) 证明方法多样，结合了双射构造、精确枚举、递推关系和素数因子论证等多种技术；3) 解决了领域内的公开猜想。缺点：1) 论文中使用的素数因子论证中的界限3,274并非最优，可能可以通过更精细的分析改进；2) 部分证明依赖计算机辅助验证，缺乏纯理论证明。

*本文仅代表个人理解及观点，不构成任何论文审核或者项目落地推荐意见，具体以相关组织评审结果为准。欢迎就论文内容交流探讨，理性发言哦～想了解更多原文细节的小伙伴，可以点击"阅读原文"，查看更多原论文细节哦！

引言