Article ID Journal Published Year Pages File Type
4648098 Discrete Mathematics 2012 14 Pages PDF
Abstract

We extend the notion of an enumeration scheme developed by Zeilberger and Vatter to the case of vincular patterns (also called “generalized patterns” or “dashed patterns”). In particular we provide an algorithm which takes in as input a set BB of vincular patterns and search parameters and returns a recurrence (called a “scheme”) to compute the number of permutations of length nn avoiding BB or confirmation that no such scheme exists within the search parameters. We also prove that if BB contains only consecutive patterns and patterns of the form σ1σ2…σt−1−σtσ1σ2…σt−1−σt, 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 BB-avoiding permutations of length nn with kk inversions.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,