Enumeration schemes for vincular patterns

详细信息	查看全文 | 推荐本文 |

• 作者：Andrew M. Baxter^a ; ¹ ; ^{baxter@math.psu.edu} ; Lara K. Pudwell^b ; ^{Lara.Pudwell@valpo.edu}
• 关键词：Pattern avoidance ; Restricted permutation ; Enumeration scheme ; Vincular pattern ; Generalized pattern ; Dashed pattern
• 刊名：Discrete Mathematics
• 出版年：2012
• 期刊代码：47_0012365x
• 类别：cp
• 出版时间：28 May, 2012
• 卷：312
• 期：10
• 页码：1699-1712
• 文件大小：288 K

摘要

We extend the notion of an enumeration scheme developed by Zeilberger and Vatter to the case of vincular patterns (also called 鈥済eneralized patterns鈥?or 鈥渄ashed patterns鈥?. In particular we provide an algorithm which takes in as input a set of vincular patterns and search parameters and returns a recurrence (called a 鈥渟cheme鈥? to compute the number of permutations of length avoiding or confirmation that no such scheme exists within the search parameters. We also prove that if contains only consecutive patterns and patterns of the form , then such a scheme must exist and provide the relevant search parameters. The algorithms are implemented in Maple and we provide empirical data on the number of small pattern sets admitting schemes. We make several conjectures on Wilf-classification based on this data. We also outline how to refine schemes to compute the number of -avoiding permutations of length with inversions.