论文标题
匹配图案poset中的模式避免
Pattern avoidance in the matching pattern poset
论文作者
论文摘要
集合$ [2n] = \ {1,2，\ ldots，2n \} $的匹配是$ [2n] $的分区，其中有两个元素，即$ [2n] $上的图形，使每个顶点都有一个学位。给定两次匹配$σ$和$τ$，我们说$σ$是$τ$的模式，当$σ$可以从$τ$中获得$τ$，通过删除其一些边缘并始终如一地重新标记其余的顶点。这是一个部分订单关系，将所有匹配的集合变成poset，这将称为匹配模式poset。在本文中，我们继续研究Chen，Deng，Du，Stanley和Yan（2007），Jelinek and Mansour（2010），Bloom和Elizalde（2012年）发起的避免匹配的类别的类别。特别是，我们制定明确的公式，以列举一类匹配类别，避免了两种新模式，通过并列较小的模式获得，并描述了一种递归公式，用于生成一系列匹配类别的搭配功能，避免了抬高模式和两个其他模式。最后，我们介绍了未标记的模式的概念，作为一种收集模式的组合方式，并为两类匹配提供了枚举公式，避免了第三顺序的未标记模式。在一种情况下，枚举是从班级和三元树的匹配项之间进行了有趣的两者。
A matching of the set $[2n]=\{ 1,2,\ldots ,2n\}$ is a partition of $[2n]$ into blocks with two elements, i.e. a graph on $[2n]$ such that every vertex has degree one. Given two matchings $σ$ and $τ$ , we say that $σ$ is a pattern of $τ$ when $σ$ can be obtained from $τ$ by deleting some of its edges and consistently relabelling the remaining vertices. This is a partial order relation turning the set of all matchings into a poset, which will be called the matching pattern poset. In this paper, we continue the study of classes of pattern avoiding matchings, initiated by Chen, Deng, Du, Stanley and Yan (2007), Jelinek and Mansour (2010), Bloom and Elizalde (2012). In particular, we work out explicit formulas to enumerate the class of matchings avoiding two new patterns, obtained by juxtaposition of smaller patterns, and we describe a recursive formula for the generating function of the class of matchings avoiding the lifting of a pattern and two additional patterns. Finally, we introduce the notion of unlabeled pattern, as a combinatorial way to collect patterns, and we provide enumerative formulas for two classes of matchings avoiding an unlabeled pattern of order three. In one case, the enumeration follows from an interesting bijection between the matchings of the class and ternary trees.
