排列、匹配和部分有向自回避路的统计量

摘要

自回避路径，即不会两次经过同一个点的格路径，是随机路径中的典型模型.对称部分有向自回避路和非对称部分有向自回避路作为两类特殊的自回避路径。分别和匹配、排列有着密切的关系，近年来在计数组合学的研究中受到广泛关注.本文主要研究了这两类路径与匹配、排列的统计量之间的一一对应关系.
　　 本文的主要结果是给出了排列和非对称部分有向自回避路之间的两个双射x1和x2.双射x1给出了排列和非对称部分有向自回避路上七组统计量的一一对应关系，如排列中的逆序数对应非对称部分有向自回避路与直线u=-x所围区域中的方格数，排列中上升的个数对应非对称部分有向自回避路中拐角的个数等.双射x2将排列的主指标对应到非对称部分有向自回避路中的方格数.由此我们给出了排列中逆序数和主指标对称分布关系的一个新的证明.
　　 另外我们用类似方法给出了匹配和对称部分有向自回避路的四组统计量间的一一对应关系.最后，综合相关的结论，提出三个可以继续研究和讨论的问题.