Processing math: 100%

Dun Qiu ; Jeffrey B. Remmel - Quadrant marked mesh patterns in 123-avoiding permutations

dmtcs:3297 - Discrete Mathematics & Theoretical Computer Science, August 3, 2018, Vol. 19 no. 2, Permutation Patterns 2016 - https://doi.org/10.23638/DMTCS-19-2-12
Quadrant marked mesh patterns in 123-avoiding permutationsArticle

Authors: Dun Qiu ; Jeffrey B. Remmel

    Given a permutation σ=σ1σn in the symmetric group Sn, we say that σi matches the quadrant marked mesh pattern MMP(a,b,c,d) in σ if there are at least a points to the right of σi in σ which are greater than σi, at least b points to the left of σi in σ which are greater than σi, at least c points to the left of σi in σ which are smaller than σi, and at least d points to the right of σi in σ which are smaller than σi. Kitaev, Remmel, and Tiefenbruck systematically studied the distribution of the number of matches of MMP(a,b,c,d) in 132-avoiding permutations. The operation of reverse and complement on permutations allow one to translate their results to find the distribution of the number of MMP(a,b,c,d) matches in 231-avoiding, 213-avoiding, and 312-avoiding permutations. In this paper, we study the distribution of the number of matches of MMP(a,b,c,d) in 123-avoiding permutations. We provide explicit recurrence relations to enumerate our objects which can be used to give closed forms for the generating functions associated with such distributions. In many cases, we provide combinatorial explanations of the coefficients that appear in our generating functions.


    Volume: Vol. 19 no. 2, Permutation Patterns 2016
    Section: Permutation Patterns
    Published on: August 3, 2018
    Accepted on: June 26, 2018
    Submitted on: May 2, 2017
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 484 times.
    This article's PDF has been downloaded 308 times.