对受限排列上固定-固定点等分布方法的改进

《Discrete Applied Mathematics》：A refinement of the fixed–pixed points equidistribution on restricted permutations

　　摘要
受到Bsila、Cox、Hugo、Styron和Zhuang关于模式避免排列中固定点和pixed点的一个最新猜想的启发，我们证明了涉及下降统计的双变量细化结果。给定一组排列??，让?????(??)表示在对称群????中避免??中每个元素的排列集合。对于他们猜想中出现的每个排列集??，我们展示了统计对 `(des,fix)` 和 `(ides,pix)` 在?????(??)上是等分布的。我们的证明基于相应模式避免类的显式普通生成函数。

引言
设????表示集合[??]={1,2,…,??}的排列对称群。如果???(??)=??，则称??∈[??]为??∈????的固定点。让fix?(??)表示??的固定点数量。如果fix?(??)=0，则称排列??∈????为错排。关于固定点和错排的研究可以在[1], [2], [3], [4], [5], [6]中找到。如果对于??∈[???1]或??=??有???(??)
示例1
对于1≤??≤4，????中的desarrangements分别是?,{21},{213,312}, 和 {2134,2143,3124,3142,3241,4123,4132,4231,4321}。

在pixed点的定义基础上，进一步探索了错排和desarrangements之间的内在关系。作为排列上的组合统计量，pixed点最初由Foata和Han在超八面体群的背景下提出并进行了深入研究。Foata和Han [8]引入了排列的pixed分解，即每个排列??∈????都有一个唯一的分解??=?????，其中??是一个递增前缀，??是一个desarrangement。??的字母是??的pixed点，我们用pix?(??)表示??的pixed点数量。特别地，恒等排列有??个pixed点。根据这个术语，错排是没有固定点的排列，而desarrangements是没有pixed点的排列。

示例2
设??=135764829∈??9。那么??的pixed分解是??=1357????64829???。这里??=1357是??的最长递增前缀，而??的第一个上升元素64829出现在位置2。因此??是一个desarrangement，且pix?(??)=4。

模式避免是现代排列研究中的一个核心主题。给定两个排列??∈????和??∈????，如果存在索引1≤??1
模式避免排列的研究可以追溯到Knuth关于堆栈可排序排列的工作，其中通过单个堆栈可排序的排列被证明正是231-avoiding排列[9]。这些排列的数量由Catalan数计数，这一观察引发了排列模式与经典Catalan对象之间的丰富互动。后来，Simion和Schmidt [10]对避免长度为三的模式的一类排列进行了系统研究，特别是证明了所有长度为三的单模式都可以用Catalan数计数。在过去的几十年里，模式避免已成为研究精细计数、双射构造、排列统计和排列类结构分解的广泛框架；参见[11], [12]以获取概述。

最近，Bsila、Cox、Hugo、Styron和Zhuang从排列统计和模式避免的角度重新审视了desarrangements [1]。他们得到了关于某些排列统计量（包括下降、峰值、谷值、双上升和双下降）的desarrangements的几个生成函数，并且还给出了避免指定长度为三的模式集合的desarrangements的完整计数。他们的工作导致了对几个经典整数序列（包括Catalan数、Fine数、Jacobsthal数和Fibonacci数）的新解释，这些数可以从模式避免desarrangements的角度来看。

设??=?{ {?{ {?{132,312},{132,321},{213,231},{123,132,312},{123,213,231},{123,312,321},{213,231,312},{213,231,321}?{ {?{ {?。在他们的论文[1]的末尾，Bsila等人提出了以下猜想。

1. 猜想1.1
对于所有??≥0和每个模式集??∈??，排列统计量fix和pix在?????(??)上是等分布的。等价地，∑??∈?????(??)??fix?(??)=∑??∈?????(??)??pix?(??)。

本文的目的是证明这个猜想的细化。我们不仅考虑fix和pix的单变量分布，还包括下降统计量。如果对于??∈[???1]有???(??)>???(??+1)，则称??为??∈????的上升元素。我们用Des?(??)表示??的上升元素集合，并用des?(??)=|Des?(??)|表示其基数。如果对于??∈[???1]有???1?(??)>???1?(??+1)，则称??为??的逆上升元素，并用ides?(??)表示??的逆上升元素数量。等价地，如果??+1出现在??的左侧，则称??为??的逆上升元素。注意，ides?(??)简单来说就是满足??+1出现在??左侧的??∈[???1]的数量。

示例3
设??=314265∈??6。??的上升元素是1、3和5，因为3>1、4>2、6>5。因此des?(??)=3。此外，???1=241365，其上升元素是2和5。等价地，通过比较??和??+1的位置得到??的逆上升元素：这里3出现在2的左侧，6出现在5的左侧。因此，??的逆上升元素是2和5，ides?(??)=2。

对于每个模式集??∈??，我们定义以下两个枚举多项式
?????(??;??,??)?∑??≥0?? ??∑??∈?????(??)??des?(??)???fix?(??)?? ???????
和
?????(??;??,??)?∑??≥0?? ??∑??∈?????(??)??ides?(??)???pix?(??)?? ???????。
以下定理是我们的主要结果。

定理1.2
对于每个??∈??，我们有?????(??;??,??)=?????(??;??)。等价地，对于??≥0，统计对 `(des,fix)` 和 `(ides,pix)` 在?????(??)上是等分布的。

注1.1
对于一个模式集??∈??，让
?????(??)?|{??∈?????(??):fix?(??)=0}|
和
??????(??)?|{??∈?????(??):pix?(??)=0|。
因此?????(??)（分别是??????(??)）是?????(??)中的错排（分别是desarrangements）的数量。根据定理1.2中设置??=1和??=0的结果，对于所有??≥0和所有??∈??，我们有?????(??)=??????(??)。这些数?????(??)可以通过Robertson–Saracino–Zeilberger [14]和Mansour–Robertson [12]对模式避免排列的精细计数获得。对于??中的九个模式类，定理1.2通过结合下降统计量，细化了Bsila等人[1]中定理3.28中模式避免desarrangements的计数。注意，他们的定理中出现的额外情况??={132}没有包含在这个细化中，因为它不满足fix和pix的完全等分布。

注1.2
Stump在[15, Corollary 3.2]中证明了对于避免{132,213,231,312}中单个模式的每个排列??，都有des?(??)=ides?(??)。由于每个??∈??都至少包含这四个模式中的一个，因此对于每个属于??的??∈?????(??)，都有des?(??)=ides?(??)。因此，本文中建立的(des,fix)和(ides,pix)的等分布等同于Henke等人[13]最近证明的(des,fix)和(des,pix)的等分布。

我们将通过生成函数技术证明定理1.2。两部分分别讨论了两模式和三模式的情况：2.1部分讨论双避免类，2.2部分讨论三模式类。

定理1.2的证明
在证明定理1.2之前，我们回顾两个基本的排列运算符。对于任何??∈????，它的反转????由?????(??)=???(??+1???)给出；它的补数????由?????(??)=??+1????(??)给出。??的反转补数由????3???(????)??=(????)??给出。等价地，对于1≤??≤??，有????3???(??)=??+1????(??+1???)。

接下来，我们将重复使用以下基本事实。

引理2.1
反转补数映射???????3??保持统计量des和fix：
des?(????3??)=des?(??)
和
fix?(????3??)=fix?(??)。

证明
对于1≤??≤???1，根据????3??的定义，