Enumeration schemes for vincular patterns

Details Enumeration schemes for vincular patterns Enumeration schemes for vincular patterns

2011-08-12

arxiv.org/abs/1108.2642v2

Mathematics

Combinatorics

25 pages. Presented at Permutation Patterns 2011. Associated Maple package posted at http://www.math.rutgers.edu/~baxter/paper

Scientific paper

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 $B$ of vincular patterns and search parameters and returns a recurrence (called a "scheme") to compute the number of permutations of length $n$ avoiding $B$ or confirmation that no such scheme exists within the search parameters. We also prove that if $B$ contains only consecutive patterns and patterns of the form $\sigma_1\sigma_2 ... \sigma_{t-1}-\sigma_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 $B$-avoiding permutations of length $n$ with $k$ inversions.

Affiliated with

Also associated with

No associations

Rating

Enumeration schemes for vincular patterns does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Enumeration schemes for vincular patterns, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Enumeration schemes for vincular patterns will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-16614