Pattern Avoidance in Reverse Double Lists - Monica Anderson; Marika Diepenbroek; Lara Pudwell; Alex Stoll (Discrete Mathematics & Theoretical Computer Science, 2018)
In this paper, we consider pattern avoidance in a subset of words on $\{1,1,2,2,…,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 $ρ$ of length 5 or more, we characterize when the number of $ρ$-avoiding reverse double lists on $n$ letters has polynomial growth. We also determine the number of $1… k$-avoiders of maximum length for any positive integer $k$.