Monica Anderson ; Marika Diepenbroek ; Lara Pudwell ; Alex Stoll - Pattern Avoidance in Reverse Double Lists

dmtcs:3289 - Discrete Mathematics & Theoretical Computer Science, October 29, 2018, Vol. 19 no. 2, Permutation Patterns 2016 - https://doi.org/10.23638/DMTCS-19-2-14
Pattern Avoidance in Reverse Double ListsArticle

Authors: Monica Anderson ; Marika Diepenbroek ; Lara Pudwell ; Alex Stoll

    In this paper, we consider pattern avoidance in a subset of words on $\{1,1,2,2,\dots,n,n\}$ called reverse double lists. In particular a reverse double list is a word formed by concatenating a permutation with its reversal. We enumerate reverse double lists avoiding any permutation pattern of length at most 4 and completely determine the corresponding Wilf classes. For permutation patterns $\rho$ of length 5 or more, we characterize when the number of $\rho$-avoiding reverse double lists on $n$ letters has polynomial growth. We also determine the number of $1\cdots k$-avoiders of maximum length for any positive integer $k$.


    Volume: Vol. 19 no. 2, Permutation Patterns 2016
    Section: Permutation Patterns
    Published on: October 29, 2018
    Accepted on: October 11, 2018
    Submitted on: April 28, 2017
    Keywords: Mathematics - Combinatorics,05A05
    Funding:
      Source : OpenAIRE Graph
    • REU Site: Valparaiso Experience in Research by Undergraduate Mathematicians; Funder: National Science Foundation; Code: 1262852

    Consultation statistics

    This page has been seen 785 times.
    This article's PDF has been downloaded 223 times.