# Positional Marked Patterns in Permutations

Jeffrey B. Remmel
Department of Mathematics
University of California, San Diego
La Jolla, CA 92093-0112. USA
<EMAIL_ADDRESS>Sittipong Thamrongpairoj
Faculty of Science at Sriracha,
Kasetsart University Sriracha Campus
Si Racha, Chonburi. Thailand
<EMAIL_ADDRESS>
###### Abstract

We define and study positional marked patterns, permutations
$\displaystyle\tau$ where one of elements in $\displaystyle\tau$ is
underlined. Given a permutation $\displaystyle\sigma$, we say that
$\displaystyle\sigma$ has a $\displaystyle\tau$-match at position
$\displaystyle i$ if $\displaystyle\tau$ occurs in $\displaystyle\sigma$ in
such a way that $\displaystyle\sigma_{i}$ plays the role of the underlined
element in the occurrence. We let $\displaystyle pmp_{\tau}(\sigma)$ denote
the number of positions $\displaystyle i$ which $\displaystyle\sigma$ has a
$\displaystyle\tau$-match. This defines a new class of statistics on
permutations, where we study such statistics and prove a number of results. In
particular, we prove that two positional marked patterns $\displaystyle
1\underline{2}3$ and $\displaystyle 1\underline{3}2$ give rise to two
statistics that have the same distribution. The equidistibution phenomenon
also occurs in other several collections of patterns like
$\displaystyle\left\\{1\underline{2}3,1\underline{3}2\right\\}$, and
$\displaystyle\left\\{1\underline{2}34,1\underline{2}43,\underline{2}134,\underline{2}143\right\\}$,
as well as two positional marked patterns of any length $\displaystyle n$:
$\displaystyle\left\\{1\underline{2}\tau,\underline{2}1\tau\right\\}$.

##  1 Introduction

The notion of mesh patterns was first introduced by Brändén and Claesson [2].
Many authors have further studied this notion. In particular, the notion of
marked mesh pattern was introduced by Úlfarsson [10], and the study of the
distributions of quadrant marked mesh patterns in permutations was initiated
by Kitaev and Remmel in [4].

Here, we recall the definition of a quadrant marked mesh pattern. Let
$\displaystyle\mathbb{N}=\left\\{0,1,2,\ldots\right\\}$ denote the set of
natural numbers and $\displaystyle S_{n}$ denote the symmetric group of
permutations of $\displaystyle 1,\ldots,n$. We consider the graph of
$\displaystyle\sigma,G(\sigma)$, to be the set of points
$\displaystyle(i,\sigma_{i})$. We are interested in the points that lie in the
four quadrants I, II, III, IV of that coordinate system. For any
$\displaystyle a,b,c,d\in\mathbb{N}$ and any
$\displaystyle\sigma=\sigma_{1}\ldots\sigma_{n}\in S_{n}$, we say that
$\displaystyle\sigma_{i}$ matches the simple marked mesh pattern
$\displaystyle MMP(a,b,c,d)$ if in $\displaystyle G(\sigma)$ relative to the
coordinate system which has the point $\displaystyle(i,\sigma_{i})$ as its
origin, there are at least $\displaystyle a$ points in quadrant I, at least
$\displaystyle b$ points in quadrant II, at least $\displaystyle c$ points in
quadrant III, and at least $\displaystyle d$ points in quadrant IV. We let
$\displaystyle mmp^{(a,b,c,d)}(\sigma)$ denote the number of $\displaystyle i$
such that $\displaystyle\sigma_{i}$ matches the marked mesh pattern
$\displaystyle MMP(a,b,c,d)$ in $\displaystyle\sigma$.

For example, let $\displaystyle\sigma=647913258$ and consider simple marked
mesh pattern $\displaystyle MMP(2,0,2,0)$. We look for points
$\displaystyle(i,\sigma_{i})$ in the graph of $\displaystyle\sigma$ such that
there are at least 2 points to the top right of $\displaystyle(i,\sigma_{i})$
and at least 2 points to the bottom left of $\displaystyle(i,\sigma_{i})$. The
graph of $\displaystyle\sigma$ and an illustration of $\displaystyle
MMP(2,0,2,0)$ are shown in Figure 1. As we see in Figure 2, at point
$\displaystyle(3,7)$, there are two points to the top right and 2 points to
the bottom left of point $\displaystyle(3,7)$, so $\displaystyle 7$ matches
$\displaystyle MMP(2,0,2,0)$ in $\displaystyle\sigma$. At point
$\displaystyle(6,3)$, on the other hand, there are 2 points to the top right
but only 1 point to the bottom left of point $\displaystyle(6,3)$. Therefore,
$\displaystyle 3$ does not match $\displaystyle MMP(2,0,2,0)$ in
$\displaystyle\sigma$. In this case, only 7 matches $\displaystyle
MMP(2,0,2,0)$ in $\displaystyle\sigma$, so $\displaystyle
mmp^{(2,0,2,0)}(\sigma)=1$. Quadrant marked mesh pattern was studied further
in [3], [5], [6], [7], [8] and [9].

$\displaystyle\geq 2$$\displaystyle\geq 2$ Figure 1: Example for marked mesh
pattern. Figure 2: 7 matches $\displaystyle MMP(2,0,2,0)$ in
$\displaystyle\sigma$ but 3 does not.

We studied a generalization of quadrant marked mesh patterns. As a motivation,
consider a statistic $\displaystyle mmp(1,0,1,0)$. Here, we make a connection
between quadrant marked mesh pattern and classical permutation patterns. Let
$\displaystyle\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n}\in S_{n}$ and
$\displaystyle\tau=\tau_{1}\tau_{2}\ldots\tau_{k}\in S_{k}$. We say that
$\displaystyle\sigma$ contains pattern $\displaystyle\tau$ if there is a
subsequence
$\displaystyle\sigma^{\prime}=\sigma_{i_{1}}\sigma_{i_{2}}\ldots\sigma_{i_{k}}$
of $\displaystyle\sigma$ such that $\displaystyle\sigma^{\prime}$ and
$\displaystyle\tau$ have the same relative order. That is,
$\displaystyle\sigma_{i_{j}}<\sigma_{i_{k}}$ if and only if
$\displaystyle\tau_{j}<\tau_{k}$. For example, permutation $\displaystyle
15324$ contains pattern $\displaystyle 123$ as the subsequence $\displaystyle
134$ (and $\displaystyle 124$) has the same relative order as pattern
$\displaystyle 123$. Here, let’s consider $\displaystyle MMP(1,0,1,0)$. An
element in a permutation matches $\displaystyle MMP(1,0,1,0)$ when there is at
least one point to the top right and at least one point to the bottom left of
the interested point. An equivalent way to think about $\displaystyle
MMP(1,0,1,0)$ for any permutation $\displaystyle\sigma$ is to count the number
of elements in $\displaystyle\sigma$ that can be the midpoint of the pattern
$\displaystyle 123$ in $\displaystyle\sigma$. One can ask similar questions
but for different patterns and positions. For example, one may consider the
number of elements in $\displaystyle\sigma$ that can be the starting point of
the pattern $\displaystyle 2314$.

Here, we briefly define the notion of positional marked patterns (pmp) which
enumerates the described statistics. A positional marked pattern of length
$\displaystyle k$ is a permutation of $\displaystyle[k]$ with one of the
elements underlined. Given any positional marked pattern $\displaystyle\tau$,
let $\displaystyle\pi(\tau)$ denote the element in $\displaystyle S_{k}$
obtained from $\displaystyle\tau$ by removing the underline, and let
$\displaystyle u(\tau)$ be the position of the underlined element in
$\displaystyle\tau$. Given
$\displaystyle\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n}\in S_{n}$ and a
positional marked pattern $\displaystyle\tau$, we say that
$\displaystyle\sigma$ has a $\displaystyle\tau$-match at position
$\displaystyle\ell$ if $\displaystyle\sigma$ contains the pattern
$\displaystyle\pi(\tau)$ in such a way that the $\displaystyle\ell$-th element
in $\displaystyle\sigma$ plays the role of the underlined elements in
$\displaystyle\tau$. Let $\displaystyle pmp_{\tau}(\sigma)$ denote the number
of positions $\displaystyle\ell$ such that $\displaystyle\sigma$ has a
$\displaystyle\tau$-match at position $\displaystyle\ell$. We will carefully
define positional marked patterns in Section 2.

Recall that, in classical patterns, two patterns $\displaystyle\tau_{1}$ and
$\displaystyle\tau_{2}$ are Wilf-equivalent if the number of
$\displaystyle\sigma$ in $\displaystyle S_{n}$ avoiding
$\displaystyle\tau_{1}$ is the same as that of $\displaystyle\tau_{2}$ for all
$\displaystyle n\in\mathbb{N}$. Here, we adopt the vocabulary from the
classical definition to our definition. Given two positional marked patterns
$\displaystyle\tau_{1}$ and $\displaystyle\tau_{2}$, we say that
$\displaystyle\tau_{1}$ and $\displaystyle\tau_{2}$ are $\displaystyle
pmp$-Wilf equivalent if $\displaystyle pmp_{\tau_{1}}$ and $\displaystyle
pmp_{\tau_{2}}$ have the same distribution over $\displaystyle S_{n}$ for all
$\displaystyle n$. Our main goal is to classify $\displaystyle pmp$-Wilf
equivalent classes for positional marked patterns.

The paper outlines as follows: In Section 2, we give a precise definition and
some preliminary results on positional marked patterns. In Section 3, we study
positional marked patterns of length $\displaystyle 3$. We prove that there
are only two $\displaystyle pmp$-Wilf equivalent classes for positional marked
patterns of length 3. The result follows from the following theorems.

######  Theorem 1.

Two positional marked patterns $\displaystyle\underline{1}23$ and
$\displaystyle\underline{1}32$ are $\displaystyle pmp$-Wilf equivalent.

######  Theorem 2.

Two positional marked patterns $\displaystyle 1\underline{2}3$ and
$\displaystyle 1\underline{3}2$ are $\displaystyle pmp$-Wilf equivalent.

In Section 4, we prove some non-trivial equivalences of pairs of positional
marked patterns of length 4 as well as providing numerical results for every
patterns of length 4. In Section 5, we prove the following theorem, which
gives an equivalence of pairs of positional marked patterns of arbitrary
length.

######  Theorem 3.

Let $\displaystyle n\geq 4$ and $\displaystyle p_{1},p_{2},\ldots,p_{n-2}$ be
a rearrangement of $\displaystyle 3,4,\ldots n$. Three positional marked
patterns $\displaystyle P_{1}=1\underline{2}p_{1}\ldots p_{\ell-2}$,
$\displaystyle P_{2}=\underline{2}1p_{1}\ldots p_{\ell-2}$ and $\displaystyle
P_{3}=2\underline{1}p_{1}\ldots p_{\ell-2}$ are pmp-Wilf equivalent.

In Section 6, we discuss further research possibilities, as well as precise
connection between positional marked patterns and quadrant marked mesh
patterns.

##  2 Definition

######  Definition 4.

Let $\displaystyle S_{k}^{*}$ denote a set of permutations of
$\displaystyle[k]$ with one of the elements underlined. Given any
$\displaystyle\tau\in S_{k}^{*}$, let $\displaystyle\pi(\tau)$ denote an
element in $\displaystyle S_{k}$ obtained from $\displaystyle\tau$ by removing
the underline, and let $\displaystyle u(\tau)$ be the position of the
underlined element in $\displaystyle\tau$. We shall call an element in
$\displaystyle S_{k}^{*}$ a positional marked pattern (pmp).

For example, $\displaystyle\tau=1\underline{4}32$ is an element in
$\displaystyle S_{4}^{*}$. In this case, $\displaystyle\pi(\tau)=1432$ and
$\displaystyle u(\tau)=2$.

######  Definition 5.

Given a word $\displaystyle w$ where letters are taken from
$\displaystyle\mathbb{Z}_{\geq 0}$, a reduction of $\displaystyle w$, denoted
by $\displaystyle red(w)$, is the word obtained from $\displaystyle w$ by
replacing the $\displaystyle i$-th smallest letter by $\displaystyle i$. In
particular, if $\displaystyle w$ is a word of length $\displaystyle k$ with
distinct letters, then $\displaystyle red(w)\in S_{k}$.

For example, if $\displaystyle w=25725$, then $\displaystyle red(w)=12312$.
Here, we are ready to define a statistic on $\displaystyle S_{n}$ that we
mainly focus on in this paper.

######  Definition 6.

Given $\displaystyle\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n}\in S_{n}$ and
$\displaystyle\tau\in S_{k}^{*}$, we say that $\displaystyle\sigma$ has a
$\displaystyle\tau$-match at position $\displaystyle\ell$ if there is a
subsequence $\displaystyle\sigma_{i_{1}}\sigma_{i_{2}}\ldots\sigma_{i_{k}}$ in
$\displaystyle\sigma$ such that

  1. 1.

$\displaystyle\ell=i_{u(\tau)}$

  2. 2.

$\displaystyle
red(\sigma_{i_{1}}\sigma_{i_{2}}\ldots\sigma_{i_{k}})=\pi(\tau)$.

In other words, $\displaystyle\sigma$ contains the pattern
$\displaystyle\pi(\tau)$ in such a way that $\displaystyle\ell$-th element in
$\displaystyle\sigma$ plays the role of the underlined elements in
$\displaystyle\tau$. Let $\displaystyle pmp_{\tau}(\sigma)$ denote the number
of positions $\displaystyle\ell$ such that $\displaystyle\sigma$ has a
$\displaystyle\tau$-match at position $\displaystyle\ell$.

For example, if $\displaystyle\sigma=26481573$ and
$\displaystyle\tau=1\underline{4}32$. Then $\displaystyle\sigma$ has a
$\displaystyle\tau$-match at positions 2 and 4, as we find subsequences
$\displaystyle 2653$ and $\displaystyle 2853$ respectively. Thus,
$\displaystyle pmp_{\tau}(\sigma)=2$. We are interested in the generating
function $\displaystyle P_{n,\tau}(x)=\sum_{\sigma\in
S_{n}}x^{pmp_{\tau}(\sigma)}$. We say that two positional marked patterns
$\displaystyle\tau_{1}$ and $\displaystyle\tau_{2}$ are $\displaystyle
pmp$-Wilf equivalent if $\displaystyle P_{n,\tau_{1}}(x)=P_{n,\tau_{2}}(x)$
for all $\displaystyle n$. Note that, by looking at the constant terms of
generating functions, if $\displaystyle\tau_{1}$ and $\displaystyle\tau_{2}$
are $\displaystyle pmp$-Wilf equivalent, then $\displaystyle\pi(\tau_{1})$ and
$\displaystyle\pi(\tau_{2})$ are Wilf-equivalent. Thus, one might think of
$\displaystyle pmp$-Wilf equivalent as a stronger version of Wilf-equivalent.
In this paper, we classify equivalence classes of $\displaystyle S_{3}^{*}$
and $\displaystyle S_{4}^{*}$.

We associate a positional marked pattern with a permutation matrix-like
diagram. Given any $\displaystyle\tau\in S_{k}^{*}$, the diagram associated to
$\displaystyle\tau$ is a $\displaystyle k$ by $\displaystyle k$ array with the
following filling: For the cell at $\displaystyle i$-th row and $\displaystyle
j$-th column (i) the cell is filled with $\displaystyle\circ$ if
$\displaystyle\tau_{i}=j$ and $\displaystyle u(\tau)=i$, (ii) the cell is
filled with $\displaystyle\times$ if $\displaystyle\tau_{i}=j$ and
$\displaystyle u(\tau)\neq i$, or (iii) the cell is empty otherwise. By
convention, we count rows and columns of an array from left to right and from
bottom to top. For example, if $\displaystyle\tau=1\underline{4}32$, then the
corresponding diagram is

( ∘ , × , ×,× ) .

Similarly, we associate $\displaystyle\sigma\in S_{n}$ with an $\displaystyle
n$ by $\displaystyle n$ diagram with the cell at $\displaystyle i$-th row and
$\displaystyle j$-column is (i) filled with $\displaystyle\times$ if
$\displaystyle\sigma_{i}=j$ and (ii) empty otherwise. For example, the diagram
corresponding to $\displaystyle\pi=26481573$ is

( × , × , × , × , × , ×,× , × ) .

We can visualize matching of $\displaystyle pmp$ using diagrams. Given a
permutation $\displaystyle\sigma$ and a $\displaystyle pmp$
$\displaystyle\tau$, $\displaystyle\sigma$ has a $\displaystyle\tau$-match at
position $\displaystyle i$ if when replacing $\displaystyle\times$ in the
$\displaystyle i$-th column of the diagram of $\displaystyle\sigma$ by
$\displaystyle\circ$, then it contains a subdiagram $\displaystyle\tau$. For
example, $\displaystyle\sigma=26481573$ has a $\displaystyle\tau$-match at
position 2 and 4 by looking at subdiagrams marked in red below.

( × , × ,  ∘ ,  × , × ,  ×, × , × ) (  ∘ , × , × ,  × , × ,  ×, × , × ) .

With diagrams, we prove equivalences of $\displaystyle pmp$ by symmetry. Given
two $\displaystyle pmp$ $\displaystyle\tau_{1},\tau_{2}$ such that the diagram
of $\displaystyle\tau_{2}$ can be obtained from $\displaystyle\tau_{1}$ by
applying a series of rotations and reflections to the diagram of
$\displaystyle\tau_{1}$, then we can construct a map
$\displaystyle\theta:S_{n}\rightarrow S_{n}$ by applying the same series of
rotations and reflections to elements in $\displaystyle S_{n}$. The map will
obviously have the property that $\displaystyle
pmp_{\tau_{1}}(\sigma)=pmp_{\tau_{2}}(\theta(\sigma))$ for all
$\displaystyle\sigma\in S_{n}$, and so $\displaystyle\tau_{1}$ and
$\displaystyle\tau_{2}$ are $\displaystyle pmp$-Wilf equivalent. We proved the
following lemma.

######  Lemma 7.

Given $\displaystyle\tau_{1},\tau_{2}\in S_{k}^{*}$, such that
$\displaystyle\tau_{2}$ can be obtained by applying series of reflections and
rotation to $\displaystyle\tau_{1}$. Then $\displaystyle\tau_{1}$ and
$\displaystyle\tau_{2}$ are $\displaystyle pmp$-Wilf equivalent.

Lemma 7 reduces the problem tremendously. There are $\displaystyle 3!\cdot
3=18$ $\displaystyle pmp$ of length 3. However, with Lemma 7, there are at
most 4 equivalence classes, which are represented by
$\displaystyle\underline{1}23,1\underline{2}3,\underline{1}32,1\underline{3}2$.
Their diagrams are shown in Figure 3

( ×, × ,∘ ) ( ×, ∘ ,× ) ( × , ×,∘ ) ( ∘ , ×,× ) .

Figure 3: Diagram shows 4 representative of positional marked patterns of
length 3 after geometrical equivalence.

##  3 Equivalence classes of $\displaystyle S_{3}^{*}$

###  3.1 Equivalence of $\displaystyle\underline{1}23$ and
$\displaystyle\underline{1}32$

In this subsection, we restate and prove one of the theorems mentioned in
Section 1.

See 1

For our convenience, we let $\displaystyle\tau_{1}=\underline{1}23$ and
$\displaystyle\tau_{2}=\underline{1}32$. We will first prove by showing that
generating functions corresponding to those patterns satisfy the same
recursive formula. We later will construct a bijection from $\displaystyle
S_{n}$ to itself that maps $\displaystyle pmp_{\tau_{1}}$ to $\displaystyle
pmp_{\tau_{2}}$, that is, a map $\displaystyle\theta$ such that $\displaystyle
pmp_{\tau_{1}}(\sigma)=pmp_{\tau_{2}}(\theta(\sigma))$.

Given any permutation
$\displaystyle\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n}\in S_{n}$. We will
look at the position where the last ascent occurs. In particular, either
$\displaystyle\sigma$ has no ascent or there is $\displaystyle k$ such that
$\displaystyle\sigma_{k}<\sigma_{k+1}>\sigma_{k+2}>\ldots>\sigma_{n}$. In that
case, we say that the last ascent of $\displaystyle\sigma$ is at position
$\displaystyle k$. Let $\displaystyle P_{n,\tau_{1},k}(x)=\sum
x^{pmp_{\tau_{1}}(\sigma)}$ where the sum is over all permutations in
$\displaystyle S_{n}$ with the last ascent at position $\displaystyle k$.
Then, we have $\displaystyle
P_{n,\tau_{1}}(x)=1+\sum_{k=1}^{n-1}P_{n,\tau_{1},k}(x)$.

Given any permutation
$\displaystyle\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n}\in S_{n}$. Similar
to $\displaystyle\tau_{1}$, we will look at the position where the last
descent occurs for $\displaystyle\tau_{2}$. Either $\displaystyle\sigma$ has
no descent, or there is $\displaystyle k$ such that
$\displaystyle\sigma_{k}>\sigma_{k+1}<\sigma_{k+2}<\ldots<\sigma_{n}$. We say
that the last descent of $\displaystyle\sigma$ is at position $\displaystyle
k$. Let $\displaystyle P_{n,\tau_{2},k}(x)=\sum x^{pmp_{\tau_{2}}(\sigma)}$
where the sum is over all permutations in $\displaystyle S_{n}$ with the last
descent at position $\displaystyle k$. Then, we have $\displaystyle
P_{n,\tau_{2}}(x)=1+\sum_{k=1}^{n-1}P_{n,\tau_{2},k}(x)$

First, we derive a recursive formula for $\displaystyle P_{n,\tau_{1},k}(x)$.

######  Lemma 8.

Let $\displaystyle\tau_{1}=\underline{1}23$ and let $\displaystyle
P_{n,\tau_{1},k}(x)=\sum x^{pmp_{\tau_{1}}(\sigma)}$ where the sum is over all
$\displaystyle\sigma\in S_{n}$ with the last ascent of $\displaystyle\sigma$
at position $\displaystyle k$. Then, $\displaystyle P_{n,\tau_{1},k}(x)$
satisfies the following recursive formula:

$\displaystyle
P_{n,\tau_{1},k}(x)=(k-1)xP_{n-1,\tau_{1},k-1}(x)+1+\sum_{\ell=1}^{k}P_{n-1,\tau_{1},\ell}(x)$

where $\displaystyle P_{n,\tau_{1},0}(x)=P_{n,\tau_{1},n}(x)=0$ by convention.

###### Proof.

We derive a recursive formula of $\displaystyle P_{n,\tau_{1},k}(x)$ by
looking at position of $\displaystyle 1$ in $\displaystyle\sigma$ where the
last ascent is at position $\displaystyle k$. So, $\displaystyle\sigma$ has a
following form:

$\displaystyle\sigma=\sigma_{1}~{}\sigma_{2}\ldots\sigma_{k-1}~{}\sigma_{k}<\sigma_{k+1}>\sigma_{k+2}>\ldots>\sigma_{n}.$

Let $\displaystyle t$ be the position of $\displaystyle 1$. We have 3 cases:

  1. 1.

$\displaystyle 1\leq t\leq k-1$. In this case, $\displaystyle
1,\sigma_{k},\sigma_{k+1}$ form the pattern $\displaystyle\tau_{1}$. Thus,
$\displaystyle\sigma$ has a $\displaystyle\tau_{1}$-match at position
$\displaystyle t$. Moreover, 1 does not influence
$\displaystyle\tau_{1}$-match at other positions. Thus, we can remove 1 from
$\displaystyle\sigma$ and reduce other elements. The last ascent will be at
position $\displaystyle k-1$. Therefore, this case contributes $\displaystyle
x(k-1)P_{n-1,\tau_{1},k-1}(x)$.

  2. 2.

$\displaystyle t=k$. In this case, $\displaystyle\sigma$ does not have a
$\displaystyle\tau_{1}$-match at position $\displaystyle k$. We can remove
$\displaystyle 1$ from $\displaystyle\sigma$ and reduce other elements. Either
the remaining permutation will has no ascent, or the last ascent appears at
some position between 1 and $\displaystyle k-1$. Thus, this case contributes
$\displaystyle 1+\sum_{\ell=1}^{k-1}P_{n-1,\tau_{1},\ell}(x)$

  3. 3.

$\displaystyle t=n$. In this case, $\displaystyle\sigma$ does not have a
$\displaystyle\tau_{1}$-match at position $\displaystyle n$. We can remove
$\displaystyle 1$ from $\displaystyle\sigma$ and reduce other elements. The
remaining permutation will have the last ascent at position $\displaystyle k$.
Thus, this case contributes $\displaystyle P_{n-1,\tau_{1},k}(x)$.

In total, we have

$\displaystyle\displaystyle P_{n,\tau_{1},k}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle(k-1)xP_{n-1,\tau_{1},k-1}(x)+1+\left(\sum_{\ell=1}^{k-1}P_{n-1,\tau_{1},\ell}(x)\right)+P_{n-1,\tau_{1},k}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle(k-1)xP_{n-1,\tau_{1},k-1}(x)+1+\sum_{\ell=1}^{k}P_{n-1,\tau_{1},\ell}(x).$

Note that, the first case does not exist when $\displaystyle k=1$, but the
formula is correct since $\displaystyle P_{n-1,\tau_{1},0}(x)=0$. Also, the
third case does not exist when $\displaystyle k=n-1$. However, the formula is
also correct since $\displaystyle P_{n,\tau_{1},n}(x)=0$.

∎

Here, we prove a similar result for $\displaystyle\tau_{2}$.

######  Lemma 9.

Let $\displaystyle\tau_{2}=\underline{1}32$ and let $\displaystyle
P_{n,\tau_{2},k}(x)=\sum x^{pmp_{\tau_{2}}(\sigma)}$ where the sum is over all
$\displaystyle\sigma\in S_{n}$ with the last descent of $\displaystyle\sigma$
at position $\displaystyle k$. Then, $\displaystyle P_{n,\tau_{2},k}(x)$
satisfies the following recursive formula:

$\displaystyle
P_{n,\tau_{2},k}(x)=(k-1)xP_{n-1,\tau_{2},k-1}(x)+1+\sum_{\ell=1}^{k}P_{n-1,\tau_{2},\ell}(x)$

where $\displaystyle P_{n,\tau_{2},0}(x)=P_{n,\tau_{2},n}(x)=0$ by convention.

###### Proof.

We use the same strategy as in the case for $\displaystyle\tau_{1}$. We derive
a recursive formula for $\displaystyle P_{n,\tau_{2},k}(x)$ by looking at the
position of $\displaystyle 1$ in $\displaystyle\sigma$ where the last descent
is at position $\displaystyle k$. So, $\displaystyle\sigma$ has the following
form:

$\displaystyle\sigma=\sigma_{1}~{}\sigma_{2}\ldots\sigma_{k-1}~{}\sigma_{k}>\sigma_{k+1}<\sigma_{k+2}<\ldots<\sigma_{n}.$

Let $\displaystyle t$ be the position of $\displaystyle 1$. We have 2 cases:

  1. 1.

$\displaystyle 1\leq t\leq k-1$. In this case, $\displaystyle
1,\sigma_{k},\sigma_{k+1}$ form the pattern $\displaystyle\tau_{2}$. Thus,
$\displaystyle\sigma$ has a $\displaystyle\tau_{2}$-match at postion
$\displaystyle t$. Moreover, 1 does not influence
$\displaystyle\tau_{2}$-match at other positions. Thus, we can remove 1 from
$\displaystyle\sigma$ and reduce other elements. The last descent will be at
position $\displaystyle k-1$. Therefore, this case contributes $\displaystyle
x(k-1)P_{n-1,\tau_{2},k-1}(x)$.

  2. 2.

$\displaystyle t=k+1$. In this case, $\displaystyle\sigma$ does not have a
$\displaystyle\tau$-match at position $\displaystyle k+1$. We can remove
$\displaystyle 1$ from $\displaystyle\sigma$ and reduce other elements. The
remaining permutation will either has no descent, or the last ascent appears
at some position between 1 and $\displaystyle k$. Thus, this case contributes
$\displaystyle 1+\sum_{\ell=1}^{k}P_{n-1,\tau_{1},\ell}(x)$.

In total, we have

$\displaystyle
P_{n,\tau_{2},k}(x)=(k-1)xP_{n-1,\tau_{2},k-1}(x)+1+\sum_{\ell=1}^{k}P_{n-1,\tau_{2},\ell}(x).$

Note that, the first case does not exist when $\displaystyle k=1$, but the
formula is correct since $\displaystyle P_{n-1,\tau_{2},0}(x)=0$. Also, for
the second case, if $\displaystyle k=n-1$, the last descent cannot be at
position $\displaystyle k=n-1$. However, the formula is still correct since
$\displaystyle P_{n-1,\tau_{2},n}(x)=0$. ∎

One can check that $\displaystyle P_{2,\tau_{1},1}(x)=1=P_{2,\tau_{2},1}(x)$.
Since $\displaystyle P_{n,\tau_{1},k}(x)$ and $\displaystyle
P_{n,\tau_{2},k}(x)$ satisfy the same recursive formula and have the same
initial values, we prove that $\displaystyle
P_{n,\tau_{1},k}(x)=P_{n,\tau_{2},k}(x)$ for all $\displaystyle n,k$ such that
$\displaystyle 1\leq k\leq n-1$, and hence $\displaystyle
P_{n,\tau_{1}}(x)=P_{n,\tau_{2}}(x)$ for all $\displaystyle n\geq 1$.
Therefore, we prove Theorem 1.

To conclude this section, we give a bijection
$\displaystyle\theta:S_{n}\rightarrow S_{n}$ such that $\displaystyle
pmp_{\tau_{1}}(\sigma)=pmp_{\tau_{2}}(\theta(\sigma))$. The bijection is
constructed based on the recursive formula. We start with
$\displaystyle\theta(1)=1$, $\displaystyle\theta(12)=21$ and
$\displaystyle\theta(21)=12$. In general, $\displaystyle\theta$ will have
following properties

  1. 1.

$\displaystyle\sigma$ has no ascent if and only if
$\displaystyle\theta(\sigma)$ has no descent.

  2. 2.

The last ascent of $\displaystyle\sigma$ is at the same position as the last
descent of $\displaystyle\theta(\sigma)$.

  3. 3.

$\displaystyle pmp_{\tau_{1}}(\sigma)=pmp_{\tau_{2}}(\theta(\sigma))$.

By observation, $\displaystyle\theta$ satisfies the properties for
$\displaystyle S_{1}$ and $\displaystyle S_{2}$. For $\displaystyle S_{n+1}$
where $\displaystyle n\geq 2$, we define the map recursively. Given
$\displaystyle\sigma\in S_{n}$, we have
$\displaystyle\sigma^{\prime}=\theta(\sigma)\in S_{n}$, where the last ascent
of $\displaystyle\sigma$ is at the same position as the last descent of
$\displaystyle\sigma^{\prime}$. Let $\displaystyle k$ be the position. We
decompose $\displaystyle\sigma$ and $\displaystyle\sigma^{\prime}$ at
$\displaystyle k$.

$\displaystyle\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{k}\hskip
28.45274pt\sigma_{k+1}\ldots\sigma_{n}$
$\displaystyle\sigma^{\prime}=\sigma^{\prime}_{1}\sigma^{\prime}_{2}\ldots\sigma^{\prime}_{k}\hskip
28.45274pt\sigma^{\prime}_{k+1}\ldots\sigma^{\prime}_{n}$

If $\displaystyle\sigma$ has no ascent, then $\displaystyle\sigma^{\prime}$
has no descent, we decompose $\displaystyle\sigma$ and
$\displaystyle\sigma^{\prime}$ by having the “first part” empty, or,
equivalently, set $\displaystyle k=0$.

$\displaystyle\sigma_{1}$$\displaystyle\sigma_{2}$$\displaystyle\sigma_{3}$$\displaystyle\sigma_{k}$$\displaystyle\sigma_{k+1}$$\displaystyle\sigma_{k+2}$$\displaystyle\sigma_{k+3}$$\displaystyle\sigma_{n}$$\displaystyle\sigma^{\prime}_{1}$$\displaystyle\sigma^{\prime}_{2}$$\displaystyle\sigma^{\prime}_{3}$$\displaystyle\sigma^{\prime}_{k}$$\displaystyle\sigma^{\prime}_{k+1}$$\displaystyle\sigma^{\prime}_{k+2}$$\displaystyle\sigma^{\prime}_{k+3}$$\displaystyle\sigma^{\prime}_{n}$
Figure 4: Inserting positions of 1 of the bijection $\displaystyle\theta$ that
sends $\displaystyle pmp_{\underline{1}23}$ to $\displaystyle
pmp_{\underline{1}32}$

Here, we obtain an element $\displaystyle\hat{\sigma}\in S_{n+1}$ by
increasing every element in $\displaystyle\sigma$ by 1 and inserting 1 at some
position, then $\displaystyle\theta(\hat{\sigma})$ will be obtained from
increasing elements in $\displaystyle\sigma^{\prime}$ by 1 and inserting 1 at
some position based on the position of 1 in $\displaystyle\hat{\sigma}$.
Suppose we insert 1 at position $\displaystyle r$ from the left in
$\displaystyle\sigma$, then the position $\displaystyle r^{\prime}$ of 1
inserted in $\displaystyle\sigma^{\prime}$ is

$\displaystyle r^{\prime}=\left\\{\begin{array}[]{ll}r&r\leq k\\\ r+1&k+1\leq
r\leq n\\\ k+1&r=n+1\end{array}\right..$

The corresponding positions of 1 can be viewed in Figure 4

By observation, the position of the last ascent of $\displaystyle\hat{\sigma}$
is the same as the position of the last descent of
$\displaystyle\hat{\sigma}$. Also, $\displaystyle pmp_{\tau_{1}}$ will
increase by 1 if and only if 1 is inserted at the first $\displaystyle k$
positions, which is the same condition for $\displaystyle pmp_{\tau_{2}}$ to
increase by 1. Thus, $\displaystyle\theta$ satisfies the conditions.

As an example, we start with $\displaystyle\theta(12)=21$. Here, the diagram
for inserting 1 looks

$\displaystyle 1$$\displaystyle 2$$\displaystyle 2$$\displaystyle 1$

.

Suppose we insert 1 to 12 at the last position, so we get 231. According to
the diagram, we should insert 1 to 21 at the second position, so we get 312.
Thus, $\displaystyle\theta(231)=312$. Now the diagram looks like

$\displaystyle 2$$\displaystyle 3$$\displaystyle 1$$\displaystyle
3$$\displaystyle 1$$\displaystyle 2$

.

Here, we insert 1 to 231 at the first position, so we get 1342. We should also
insert 1 to 312 at the first position, so we get 1423. Thus,
$\displaystyle\theta(1342)=1423$.

Below are enumerations of $\displaystyle P_{n,\underline{1}23}(x)$ for the
first few $\displaystyle n$:

$\displaystyle\displaystyle P_{1,\underline{1}23}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle{1}$
$\displaystyle\displaystyle P_{2,\underline{1}23}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle{2}$
$\displaystyle\displaystyle P_{3,\underline{1}23}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle{5+x}$
$\displaystyle\displaystyle P_{4,\underline{1}23}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle{14+8x+2x^{2}}$
$\displaystyle\displaystyle P_{5,\underline{1}23}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle{42+47x+25x^{2}+6x^{3}}$
$\displaystyle\displaystyle P_{6,\underline{1}23}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle{132+244x+216x^{2}+104x^{3}+24x^{4}}$
$\displaystyle\displaystyle P_{7,\underline{1}23}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle{429+1186x+1568x^{2}+1199x^{3}+538x^{4}+120x^{5}}$
$\displaystyle\displaystyle P_{8,\underline{1}23}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle{1430+5536x+10232x^{2}+11264x^{3}+7814x^{4}+3324x^{5}+720x^{6}}$

###  3.2 Special values for $\displaystyle P_{n,\underline{1}23}(x)|_{x^{k}}$

Even though we do not know a formula for $\displaystyle
P_{n,\underline{1}23}(x)$ in general, we can still explain some of the
coefficients. For example, $\displaystyle
P_{n,\underline{1}23}(x)|_{x^{0}}=C_{n}$, the $\displaystyle n$-th Catalan
number. This is obvious since a permutation is $\displaystyle 123$-avoiding if
and only if it does not have a $\displaystyle\underline{1}23$-match at any
position. There are other coefficients that have a nice formula.

######  Theorem 10.

For $\displaystyle n\geq 3$, the degree of $\displaystyle
P_{n,\underline{1}23}(x)$ is $\displaystyle n-2$, and $\displaystyle
P_{n,\underline{1}23}(x)|_{x^{n-2}}=(n-2)!$

###### Proof.

For any $\displaystyle\sigma\in S_{n}$, it is clear that $\displaystyle\sigma$
does not have a $\displaystyle\underline{1}23$-match at position
$\displaystyle n$ or $\displaystyle n-1$. Thus, $\displaystyle
pmp_{\underline{1}23}(\sigma)\leq n-2$. For any $\displaystyle\sigma\in
S_{n}$, we claim that $\displaystyle pmp_{\underline{1}23}(\sigma)=n-2$ if and
only if $\displaystyle\sigma_{n-1}=n-1$ and $\displaystyle\sigma_{n}=n$. The
converse obviously true since $\displaystyle\sigma$ would have a
$\displaystyle\underline{1}23$-match at position $\displaystyle i$ for
$\displaystyle 1\leq i\leq n-2$. Suppose that $\displaystyle
pmp_{\underline{1}23}(\sigma)=n-2$. Let $\displaystyle p_{i}$ be the position
of $\displaystyle i$ in $\displaystyle\sigma$. That is
$\displaystyle\sigma_{p_{i}}=i$. Note that $\displaystyle n-1$ and
$\displaystyle n$ cannot be a starting point of the pattern $\displaystyle
123$, so $\displaystyle\sigma$ does not have a
$\displaystyle\underline{1}23$-match at positions $\displaystyle p_{n-1}$ and
$\displaystyle p_{n}$. However, $\displaystyle\sigma$ has a
$\displaystyle\underline{1}23$-match at every position except $\displaystyle
n-1$ and $\displaystyle n$. Thus,
$\displaystyle\left\\{p_{n-1},p_{n}\right\\}=\left\\{n-1,n\right\\}$. Consider
position $\displaystyle p_{n-2}$. $\displaystyle\sigma$ must be
$\displaystyle\underline{1}23$-match at position $\displaystyle p_{n-2}$. That
is $\displaystyle n-2$ is a starting point of a pattern 123 in
$\displaystyle\sigma$. However, the only way for $\displaystyle n-2$ to be a
starting point of $\displaystyle 123$ is that $\displaystyle n-2,n-1,n$ form
the pattern $\displaystyle 123$. That is $\displaystyle n-1$ is to the left of
$\displaystyle n$. So, $\displaystyle p_{n-1}=n-1$ and $\displaystyle
p_{n}=n$, which means $\displaystyle\sigma_{n-1}=n-1$ and
$\displaystyle\sigma_{n}=n$.

Thus, we know that all $\displaystyle\sigma$ such that $\displaystyle
pmp_{\underline{1}23}(\sigma)=n-2$ are precisely all $\displaystyle\sigma$ of
the form:

$\displaystyle\sigma=\sigma_{1}~{}\sigma_{2}~{}\ldots~{}\sigma_{n-3}~{}\sigma_{n-2}~{}n-1~{}n.$

There are $\displaystyle(n-2)!$ such $\displaystyle\sigma$’s, so
$\displaystyle P_{n,\underline{1}23}(x)|_{x^{n-2}}=(n-2)!$. ∎

This theorem can generalized to any pmp.

######  Theorem 11.

Given any positive integer $\displaystyle n,k$ such that $\displaystyle n\geq
k$, and any $\displaystyle\tau\in S_{k}^{*}$, the degree of $\displaystyle
P_{n,\tau}(x)$ is $\displaystyle n-k+1$, and $\displaystyle
P_{n,\tau}(x)|_{x^{n-k+1}}=(n-k+1)!$.

###### Proof.

Given $\displaystyle k\leq n$ and $\displaystyle\tau\in S_{k}^{*}$. Suppose
$\displaystyle\tau$ has the form

$\displaystyle\tau=\tau_{1}~{}\tau_{2}~{}\ldots\underline{\tau}_{\ell}\ldots~{}\tau_{k-1}~{}\tau_{k}.$

That is $\displaystyle u(\tau)=\ell$ and
$\displaystyle\pi(\tau)=\tau_{1}\tau_{2}\ldots\tau_{k}$. Note that there are
$\displaystyle\ell-1$ numbers to the left of the underlined number in
$\displaystyle\tau$ and there are $\displaystyle k-\ell$ numbers to the right
of the underlined number in $\displaystyle\tau$. Given $\displaystyle\sigma\in
S_{n}$, suppose $\displaystyle\sigma$ has a $\displaystyle\tau$-match at
position $\displaystyle i$. Then, there must be at least $\displaystyle\ell-1$
numbers to the left of position $\displaystyle i$ in $\displaystyle\sigma$ and
there must be at least $\displaystyle k-\ell$ to the right of position
$\displaystyle i$ in $\displaystyle\sigma$. Thus, $\displaystyle\ell\leq i\leq
n-k+\ell$. Therefore, $\displaystyle pmp_{\tau}(\sigma)\leq n-k+1$. Thus, the
degree of $\displaystyle P_{n,\tau}(x)$ is at most $\displaystyle n-k+1$.

Here, we count the number of $\displaystyle\sigma\in S_{n}$ such that
$\displaystyle pmp_{\tau}(x)=n-k+1$. We shall prove the following claim:

######  Claim 12.

Given $\displaystyle\sigma=\sigma_{1}\ldots\sigma_{n}\in S_{n}$,
$\displaystyle pmp_{\tau}(\sigma)=n-k+1$ if and only if all of the followings
hold:

  1. (1)

$\displaystyle\left\\{\sigma_{1},\sigma_{2},\ldots,\sigma_{\ell-1},\sigma_{n-k+\ell+1},\ldots,\sigma_{n}\right\\}=\left\\{1,2,\ldots,\tau_{\ell}-1,n-k+\tau_{\ell}+1,\ldots,n\right\\}$

  2. (2)

$\displaystyle
red(\sigma_{1}\sigma_{2}\ldots\sigma_{\ell-1}\sigma_{n-k+\ell+1}\ldots\sigma_{n})=red(\tau_{1}\tau_{2}\ldots\tau_{\ell-1}\tau_{\ell+1}\ldots\tau_{k})$

That is, the first $\displaystyle\ell-1$ numbers and last $\displaystyle
k-\ell$ numbers in $\displaystyle\sigma$ is a rearrangement of
$\displaystyle\left\\{1,2,\ldots,\tau_{\ell}-1,n-k+\tau_{\ell}+1,\ldots,n\right\\}$
in the way that they have the same relative order as
$\displaystyle\tau_{1}\tau_{2}\ldots\tau_{\ell-1}\tau_{\ell+1}\ldots\tau_{k}$.

###### Proof.

(of the claim)

We first prove the converse. Suppose $\displaystyle\sigma$ satisfies (1) and
(2). We want to show that $\displaystyle\sigma$ has a
$\displaystyle\tau$-match at any position $\displaystyle i$ when
$\displaystyle\ell\leq i\leq n-k+\ell$. Given any such position $\displaystyle
i$. Consider the following subsequence

$\displaystyle\sigma_{1}\sigma_{2}\ldots\sigma_{\ell-1}~{}\sigma_{i}~{}\sigma_{n-k+\ell+1}\ldots\sigma_{n}.$

Note that $\displaystyle\sigma_{i}$ is the $\displaystyle\tau_{\ell}$-th
smallest number in the subsequence, and $\displaystyle\tau_{\ell}$ is the
$\displaystyle\tau_{\ell}$-th smallest number in subsequence
$\displaystyle\tau_{1}\tau_{2}\ldots\tau_{k}$. Thus, we can insert
$\displaystyle\sigma_{i}$ to
$\displaystyle\sigma_{1}\ldots\sigma_{\ell-1}\sigma_{\ell+1}\ldots\sigma_{n}$
and $\displaystyle\tau_{\ell}$ to
$\displaystyle\tau_{1}\ldots\tau_{\ell-1}\tau_{\ell+1}\tau_{k}$. So,
$\displaystyle\sigma_{1}\sigma_{2}\ldots\sigma_{\ell-1}~{}\sigma_{i}~{}\sigma_{n-k+\ell+1}\ldots\sigma_{n}$
have the same relative order as $\displaystyle\tau_{1}\ldots\tau_{k}$.
However, $\displaystyle\tau_{1}\ldots\tau_{k}=\pi(\tau)$ is a permutation, so
$\displaystyle
red(\sigma_{1}\sigma_{2}\ldots\sigma_{\ell-1}~{}\sigma_{i}~{}\sigma_{n-k+\ell+1}\ldots\sigma_{n})=\pi(\tau)$.
So, $\displaystyle\sigma$ has a $\displaystyle\tau$-match at position
$\displaystyle i$.

Here, we prove the forward direction. Suppose $\displaystyle
pmp_{\tau}(\sigma)=n-k+1$, then $\displaystyle\sigma$ has a
$\displaystyle\tau$-match at all positions $\displaystyle i$ when
$\displaystyle\ell\leq i\leq n-k+\ell$, and $\displaystyle\sigma$ does not
have a $\displaystyle\tau$-match at all positions $\displaystyle
j\in\left\\{1,2,\ldots,l-1,n-k+l+1,\ldots,n\right\\}$. Note that, in order for
$\displaystyle\sigma$ to match at postion $\displaystyle i$, there must be at
least $\displaystyle\tau_{\ell}-1$ numbers less than $\displaystyle\sigma_{i}$
and there must be at least $\displaystyle k-\tau_{\ell}$ numbers greater than
$\displaystyle\sigma_{i}$. Therefore
$\displaystyle\tau_{\ell}\leq\sigma_{i}\leq n-k+\tau_{\ell}$. In other words,
$\displaystyle\sigma$ does not have a $\displaystyle\tau$-match at positions
of $\displaystyle 1,2,\ldots,\tau_{\ell}-1$ nor positions of $\displaystyle
n-k+\tau_{\ell},n-k+\tau_{\ell}+1,\ldots,n$. There are $\displaystyle k-1$
such positions, therefore
$\displaystyle\left\\{p_{1},p_{2},\ldots,p_{\tau_{\ell}-1},p_{n-k+\tau_{\ell}+1},\ldots,p_{n}\right\\}=\left\\{1,2,\ldots,\ell-1,n-k+\ell+1,\ldots,n\right\\}$,
or in other words,
$\displaystyle\left\\{\sigma_{1},\sigma_{2},\ldots,\sigma_{\ell-1},\sigma_{n-k+\ell+1},\ldots,\sigma_{n}\right\\}=\left\\{1,2,\ldots,\tau_{\ell}-1,n-k+\tau_{\ell}+1,\ldots,n\right\\}$.
Thus, we prove (1).

To prove (2), we only need to show that there is at most one rearrangement of
$\displaystyle\\{1,2,\ldots,\tau_{\ell}-1,n-k+\tau_{\ell}+1,\ldots,n\\}$ such
that $\displaystyle pmp_{\tau}(\sigma)=n-k+1$. Then, by converse direction, we
know that the rearrangement in (2) make $\displaystyle
pmp_{\tau}(\sigma)=n-k+1$. In that case, we conclude that the unique
rearrangement that make $\displaystyle pmp_{\tau}(\sigma)=n-k+1$ exists and
must be (2).

Let’s call numbers appearing at positions $\displaystyle 1,2,\ldots,\ell-1$
the left part of $\displaystyle\sigma$, while call the numbers appearing at
positions $\displaystyle n-k+\ell+1,n-k+\ell+2,\ldots,n$ the right part of
$\displaystyle\sigma$. Then, $\displaystyle\sigma$ has a following structure:

$\displaystyle 1,2,\ldots,\tau_{\ell}-1,n-k+\tau_{\ell}+1,\ldots
n$$\displaystyle\sigma$ $\displaystyle=$left partright part

We shall prove that ways to rearrange $\displaystyle
1,2,\ldots,\tau_{\ell}-1,n-k+\tau_{\ell}+1,\ldots n$ in left and right part of
$\displaystyle\sigma$ so that $\displaystyle pmp_{\tau}(\sigma)=n-k+1$ is
unique if exist.

Consider the number $\displaystyle\tau_{l}$ in $\displaystyle\sigma$. We know
that $\displaystyle\sigma$ has a $\displaystyle\tau$-match at position
$\displaystyle p_{\tau_{\ell}}$. Then, numbers $\displaystyle
1,2,\ldots,\tau_{\ell}-1$ in $\displaystyle\sigma$ must involve in
$\displaystyle\tau$-match at position $\displaystyle p_{\tau_{\ell}}$ since we
need $\displaystyle\tau_{\ell}-1$ numbers smaller than
$\displaystyle\tau_{\ell}$. Therefore, for each number $\displaystyle i$ less
than $\displaystyle\tau_{\ell}$, we can determine whether $\displaystyle i$ is
in the left part or the right part of $\displaystyle\sigma$ based on the
relative postion of $\displaystyle i$ and $\displaystyle\tau_{\ell}$ in
$\displaystyle\tau$. Also, consider the number $\displaystyle
n-k+\tau_{\ell}$. $\displaystyle\sigma$ must be a $\displaystyle\tau$-match at
position $\displaystyle p_{n-k+\tau_{\ell}}$. By the same reasoning, for each
number $\displaystyle n-k+\tau_{\ell}+i$, we determine whether $\displaystyle
n-k+\tau_{\ell}+i$ is in the left part or right part of $\displaystyle\sigma$
based on the relative position of $\displaystyle\tau_{\ell}+i$ and
$\displaystyle\tau_{\ell}$ in $\displaystyle\tau$. Thus, we determine both
left and right part as sets.

Now, consider position $\displaystyle\ell$ in $\displaystyle\sigma$.
$\displaystyle\sigma$ must have a $\displaystyle\tau$-match at position
$\displaystyle\ell$. Thus, numbers in first $\displaystyle\ell-1$ positions in
$\displaystyle\sigma$ must involve in a $\displaystyle\tau$-match at position
$\displaystyle\ell$, and so, the first $\displaystyle\ell-1$ numbers in
$\displaystyle\sigma$ must have the same relative order as first
$\displaystyle\ell-1$ elements in $\displaystyle\tau$. By the same reasoning,
by considering position $\displaystyle n-k+\ell$, the last $\displaystyle
k-\ell$ numbers in $\displaystyle\sigma$ have the same relative order as the
last $\displaystyle k-\ell$ numbers in $\displaystyle\tau$. Therefore, we
completely determine both left and right part of $\displaystyle\sigma$. Thus,
there is at most one way to rearrange
$\displaystyle\left\\{1,2,\ldots,\tau_{\ell}-1,n-k+\tau_{\ell}+1,\ldots,n\right\\}$.

Since the rearrangement in (2) makes $\displaystyle pmp(\sigma)=n-k+1$,
$\displaystyle\sigma$, then $\displaystyle\sigma$ must satisfies (2).

∎

As an example, if $\displaystyle\tau=164\underline{3}52$, any
$\displaystyle\sigma\in S_{9}$ with $\displaystyle pmp_{\tau}(\sigma)=9-6+1=4$
must have the following form:

$\displaystyle\sigma=1~{}9~{}7~{}~{}\sigma_{4}~{}\sigma_{5}~{}\sigma_{6}~{}\sigma_{7}~{}8~{}2$

There are $\displaystyle(n-k+1)!$ ways to rearrange the “middle” part of
$\displaystyle\sigma$. Thus, $\displaystyle P_{n,\tau}(x)|x^{n-k+1}=(n-k+1)!.$

∎

Another coefficient we can describe is $\displaystyle
P_{n,\underline{1}32}(x)|_{x}$. The sequence are A029760 and A139262 on OEIS.
The sequence A139262 counts the sum of all inversion of all elements in
$\displaystyle S_{n}(132)$, the set of 132-avoiders in $\displaystyle S_{n}$.

######  Theorem 13.

$\displaystyle P_{n+1,\underline{1}32}(x)|_{x}=\sum_{\sigma\in
S_{n}(132)}inv(\sigma)$

###### Proof.

To prove the theorem, we construct sets whose cardinality are
$\displaystyle\sum_{\sigma\in S_{n}(132)}inv(\sigma)$.

######  Definition 14.

Let $\displaystyle IMS_{n}(132)$ be the set of 132-avoiding
$\displaystyle\sigma$ that a pair of elements causing an inversion are marked
with $\displaystyle*$.

As an example, $\displaystyle IMS_{3}(132)$ contains 8 elements, which are
$\displaystyle\overset{*}{2}\overset{*}{1}3$,
$\displaystyle\overset{*}{2}3\overset{*}{1}$, $\displaystyle
2\overset{*}{3}\overset{*}{1}$, $\displaystyle\overset{*}{3}\overset{*}{1}2$,
$\displaystyle\overset{*}{3}1\overset{*}{2}$,
$\displaystyle\overset{*}{3}\overset{*}{2}1$,
$\displaystyle\overset{*}{3}2\overset{*}{1}$, and $\displaystyle
3\overset{*}{2}\overset{*}{1}$. It is easy to see that
$\displaystyle|IMS_{n}(132)|=\sum_{\sigma\in S_{n}(132)}inv(\sigma)$.

######  Definition 15.

Given $\displaystyle\sigma\in S_{n}$, $\displaystyle i,j\in\mathbb{Z}$,
$\displaystyle 1\leq i\leq n$, $\displaystyle 1\leq j\leq n+1$. Let
$\displaystyle\theta(\sigma,i,j)$ be an element in $\displaystyle S_{n+1}$
obtained from $\displaystyle\sigma$ by

  1. 1.

increasing every number greater than or equal to $\displaystyle i$ by 1

  2. 2.

inserting $\displaystyle i$ at the $\displaystyle j$-th position from the
left. (The first position is in front of the first element, and the
$\displaystyle n+1$-th position is behind the last element).

For example, to find $\displaystyle\theta(2143,3,2)$, first, we increase 3,4
by 1 so we have $\displaystyle 2154$. Then, we insert 3 at the second
position, so we have $\displaystyle 23154$. Thus,
$\displaystyle\theta(2143,3,2)=23154$.

Here, we are ready to define a map
$\displaystyle\Phi:IMS_{n}(132)\rightarrow\left\\{\sigma\in S_{n+1}\hskip
2.84544pt|\hskip 2.84544ptpmp_{\underline{1}32}(\sigma)=1\right\\}$.

######  Definition 16.

Given $\displaystyle\overline{\sigma}\in IMS_{n}(132)$. Let
$\displaystyle\sigma$ be the underlying permutation of
$\displaystyle\overline{\sigma}$. Let $\displaystyle j$ be the position of the
first * in $\displaystyle\sigma$, and let $\displaystyle i$ be the number
underneath the second * in $\displaystyle\sigma$. Define
$\displaystyle\Phi(\overline{\sigma})=\theta(\sigma,i,j)$.

######  Lemma 17.

Given $\displaystyle\overline{\sigma}\in IMS_{n}(132)$ and
$\displaystyle\hat{\sigma}=\Phi(\overline{\sigma})$, then $\displaystyle
pmp_{\underline{1}32}(\hat{\sigma})=1$. Thus, $\displaystyle\Phi$ is a map
from $\displaystyle IMS_{n}(132)$ to $\displaystyle\left\\{\sigma\in
S_{n+1}|pmp_{\underline{1}32}(\sigma)=1\right\\}$.

###### Proof.

Let $\displaystyle\overline{\sigma}\in IMS_{n}(132)$ has a form

$\displaystyle\overline{\sigma}=\sigma_{1}\ldots\sigma_{k-1}\overset{*}{\sigma}_{k}\sigma_{k+1}\ldots\sigma_{\ell-1}\overset{*}{\sigma}_{\ell}\sigma_{\ell+1}\ldots\sigma_{n}$

and $\displaystyle\sigma$ is the underlying permutation. Then,
$\displaystyle\Phi(\overline{\sigma})=\theta(\sigma,\sigma_{l},k)$ looks like

$\displaystyle\Phi(\overline{\sigma})=\sigma_{1}^{\prime}\ldots\sigma_{k-1}^{\prime}\sigma_{l}\sigma_{k}^{\prime}\sigma_{k+1}^{\prime}\ldots\sigma_{\ell-1}^{\prime}\sigma_{\ell}^{\prime}\sigma_{\ell+1}^{\prime}\ldots\sigma_{n}^{\prime}$

where

$\displaystyle\sigma_{i}^{\prime}=\left\\{\begin{array}[]{ll}\sigma_{i}+1&\text{for
}\sigma_{i}\geq\sigma_{l}\\\ \sigma_{i}&\text{for
}\sigma_{i}<\sigma_{l}\end{array}\right..$

Note that $\displaystyle\sigma_{\ell}^{\prime}=\sigma_{\ell}+1$. Also, since
$\displaystyle\sigma_{k}$ and $\displaystyle\sigma_{\ell}$ cause an inversion,
so $\displaystyle\sigma_{k}>\sigma_{\ell}$, and thus
$\displaystyle\sigma_{k}^{\prime}=\sigma_{k}+1$. Therefore,
$\displaystyle\sigma_{\ell}<\sigma_{\ell}^{\prime}<\sigma_{k}^{\prime}$.
Equvialently,
$\displaystyle\sigma_{\ell},\sigma_{k}^{\prime},\sigma_{\ell}^{\prime}$ form
the pattern $\displaystyle 132$ in $\displaystyle\hat{\sigma}$. Thus,
$\displaystyle pmp_{\underline{1}32}(\hat{\sigma})\geq 1$. To prove that
$\displaystyle pmp_{\underline{1}32}(\hat{\sigma})=1$, we need to show that
$\displaystyle\hat{\sigma}$ does not contain a pattern 132 that starts at any
element other than $\displaystyle\sigma_{\ell}$.

Suppose otherwise. That is, $\displaystyle\hat{\sigma}$ contains the pattern
$\displaystyle 132$ where the starting element is
$\displaystyle\sigma^{\prime}_{t}$ for some $\displaystyle t$. We have two
cases:

  1. 1.

If the pattern does not involve $\displaystyle\sigma_{\ell}$, then there must
be $\displaystyle u,v$ such that
$\displaystyle\sigma^{\prime}_{t},\sigma^{\prime}_{u},\sigma^{\prime}_{v}$
form a pattern 132. It is easy to see that
$\displaystyle\sigma_{t},\sigma_{u},\sigma_{v}$ also form a pattern 132 in
$\displaystyle\sigma$, which is a contradiction since $\displaystyle\sigma$ is
a 132-avoider.

  2. 2.

If the pattern involves $\displaystyle\sigma_{\ell}$, then $\displaystyle t<k$
and $\displaystyle\sigma_{t}^{\prime}<\sigma_{\ell}$. In this case, it is easy
to see that
$\displaystyle\sigma_{t}^{\prime},\sigma_{k}^{\prime},\sigma_{\ell}^{\prime}$
also form the pattern $\displaystyle 132$. Thus,
$\displaystyle\sigma_{t},\sigma_{k},\sigma_{\ell}$ form the pattern
$\displaystyle 132$ in $\displaystyle\sigma$, which is again a contradiction.

Thus, $\displaystyle\hat{\sigma}$ does not contain the pattern 132 that starts
at any element except $\displaystyle\sigma_{\ell}$. So, $\displaystyle
pmp_{\underline{1}32}(\hat{\sigma})=1$. ∎

The map $\displaystyle\Phi$ is clearly an injection. Let
$\displaystyle\sigma=\sigma_{1}\ldots\sigma_{n}$ be in the image of
$\displaystyle\Phi$, and let $\displaystyle\sigma_{i}$ be the starting point
of the pattern 132. Then, $\displaystyle i$ determines the first starred
element, and $\displaystyle\sigma_{i}$ determines the second starred element.
To prove that the map $\displaystyle\Phi$ is a surjective, we need another
lemma:

######  Lemma 18.

Given $\displaystyle\sigma=\sigma_{1}\ldots\sigma_{n}\in S_{n}$ such that
$\displaystyle pmp_{\underline{1}32}(\sigma)=1$. Suppose the pattern 132 in
$\displaystyle\sigma$ starts at $\displaystyle\sigma_{t}$, then the following
must be true:

  1. (1)

$\displaystyle\sigma_{t+1}\geq\sigma_{t}$

  2. (2)

$\displaystyle\sigma_{t}+1$ is on the right of $\displaystyle\sigma_{t}$

  3. (3)

$\displaystyle\sigma_{t+1}\neq\sigma_{t}+1$

That is, the graph of $\displaystyle\sigma$ should look like

$\displaystyle\sigma_{t}$$\displaystyle\sigma_{t+1}$$\displaystyle\sigma_{t}+1$

.

###### Proof.

Suppose (1) is not true. There must be $\displaystyle u,v$ such that
$\displaystyle\sigma_{t},\sigma_{u},\sigma_{v}$ form a pattern 132. Then,
$\displaystyle\sigma_{t+1},\sigma_{u},\sigma_{v}$ also form a pattern 132. So,
$\displaystyle pmp_{\underline{1}32}(\sigma)\geq 2$.

Suppose (2) is not true. There must be $\displaystyle u,v$ such that
$\displaystyle\sigma_{t},\sigma_{u},\sigma_{v}$ form a pattern 132. Then,
$\displaystyle\sigma_{t}+1,\sigma_{u},\sigma_{v}$ also form a pattern 132. So,
$\displaystyle pmp_{\underline{1}32}(\sigma)\geq 2$.

Suppose (3) is not true. There must be $\displaystyle u,v$ such that
$\displaystyle\sigma_{t},\sigma_{u},\sigma_{v}$ form a pattern 132. Then,
$\displaystyle\sigma_{t+1},\sigma_{u},\sigma_{v}$ also form a pattern 132. So,
$\displaystyle pmp_{\underline{1}32}(\sigma)\geq 2$.

In all cases, we have a contradiction. Therefore, (1), (2) and (3) are true. ∎

######  Lemma 19.

The map $\displaystyle\Phi:IMS_{n}(132)\rightarrow\left\\{\sigma\in
S_{n+1}|\underline{1}32(\sigma)=1\right\\}$ is surjective.

###### Proof.

Given any $\displaystyle\sigma\in\left\\{\sigma\in
S_{n+1}|\underline{1}32(\sigma)=1\right\\}$. Let $\displaystyle\sigma_{t}$ be
the starting point of the pattern 132 in $\displaystyle\sigma$. By lemma 18,
we know that $\displaystyle\sigma_{t},\sigma_{t+1},\sigma_{t}+1$ form a
pattern 132. Let $\displaystyle\tilde{\sigma}$ be a permutation obtained from
$\displaystyle\sigma$ by removing $\displaystyle\sigma_{t}$ and reducing. Let
$\displaystyle\tilde{\sigma}^{*}$ be $\displaystyle\tilde{\sigma}$ with *
marked on elements corresponding to $\displaystyle\sigma_{t+1}$ and
$\displaystyle\sigma_{t}+1$ before reducing
($\displaystyle\sigma_{t+1}-1,\sigma_{t}$ after reducing).
$\displaystyle\tilde{\sigma}^{*}$ is an element is $\displaystyle
IMS_{n}(132)$ since $\displaystyle\sigma_{t+1},\sigma_{t}+1$ form an
inversion. Clearly, $\displaystyle\Phi(\tilde{\sigma}^{*})=\sigma$ ∎

For example, consider $\displaystyle\sigma=785269314\in S_{9}$ with
$\displaystyle pmp_{132}(\sigma)=1$, where only possible starting point of the
pattern 132 is 2. So, in this example,
$\displaystyle\sigma_{t},\sigma_{t+1},\sigma_{t}+1$ are 2,6,3. Then, removing
2 and reducing give $\displaystyle\tilde{\sigma}=67458213$. Then, put * at
elements corresponding to 6,3 before reducing, which are 5,2 after reducing.
So, $\displaystyle\tilde{\sigma}^{*}=674\overset{*}{5}8\overset{*}{2}13$.

Therefore $\displaystyle\Phi$ is a bijection, and so we prove Theorem 13.

∎

###  3.3 Equivalence of $\displaystyle 1\underline{2}3$ and $\displaystyle
1\underline{3}2$

By observing diagrams of $\displaystyle 1\underline{3}2$ and $\displaystyle
13\underline{2}$, we see that those two patterns are equivalent by lemma 7.
Thus, we will instead prove that $\displaystyle 1\underline{2}3$ and
$\displaystyle 13\underline{2}$ are equivalent.

( ∘ , ×,× ) ( × , ∘,× )

Diagrams of $\displaystyle 1\underline{3}2$ and $\displaystyle
13\underline{2}$

Here, we restate and prove one of the theorems mentioned in Section 1.

See 2

For our convenience, we let $\displaystyle\tau_{1}=1\underline{2}3$ and
$\displaystyle\tau_{2}=13\underline{2}$. We will first prove by showing that
two generating functions satisfy the same recursive formula. We later will
construct a bijection from $\displaystyle S_{n}$ to itself that maps an
$\displaystyle pmp_{\tau_{1}}$ to $\displaystyle pmp_{\tau_{2}}$, that is, a
map $\displaystyle\theta$ such that $\displaystyle
pmp_{\tau_{1}}(\sigma)=pmp_{\tau_{2}}(\theta(\sigma))$.

Given any permutation $\displaystyle\sigma\in S_{n}$. We will look at the
position of $\displaystyle 1$ in $\displaystyle\sigma$. Let $\displaystyle
P_{n,\tau_{1},k}(x)=\sum x^{pmp_{\tau_{1}}(\sigma)}$, where the sum is over
all permutations in $\displaystyle S_{n}$ with 1 at position $\displaystyle
k$. Then, we have $\displaystyle
P_{n,\tau_{1}}(x)=\sum_{k=1}^{n}P_{n,\tau_{1},k}(x)$.

Here, we derive a recursive formula for $\displaystyle P_{n,\tau_{1},k}(x)$.

######  Lemma 20.

Let $\displaystyle\tau_{1}=1\underline{2}3$ and let $\displaystyle
P_{n,\tau_{1},k}=x^{pmp_{\tau_{1}}(\sigma)}$ where the sum is over all
$\displaystyle\sigma\in S_{n}$ with 1 at position $\displaystyle k$. Then,
$\displaystyle P_{n,\tau_{1},k}(x)$ satisfies the following recursive formula:

$\displaystyle
P_{n,\tau_{1},k}(x)=\left(\sum_{\ell=1}^{k-1}P_{n-1,\tau_{1},\ell}(x)\right)+(x(n-k-1)+1)P_{n-1,\tau_{1},k}(x)$

where $\displaystyle P_{n,\tau_{1},N}(x)=0$ for $\displaystyle N>n$ by
convention.

###### Proof.

We derive a recursive formula for $\displaystyle P_{n,\tau_{1},k}(x)$ by
looking at the position of 2 in $\displaystyle\sigma$ where the position of
$\displaystyle 1$ is $\displaystyle k$. $\displaystyle\sigma$ has a following
form

$\displaystyle\sigma=\sigma_{1}~{}\sigma_{2}~{}\ldots~{}\sigma_{k-1}~{}1~{}\sigma_{k+1}~{}\ldots~{}\sigma_{n}.$

Let $\displaystyle\ell$ be the position of $\displaystyle 2$. We have 3 cases:

  1. 1.

$\displaystyle 1\leq\ell\leq k-1$. In this case, we can remove $\displaystyle
1$ from $\displaystyle\sigma$ and reduce other elements without effecting
$\displaystyle\tau_{1}$-match at other position. To see this, first note that
if $\displaystyle\sigma$ does not have a $\displaystyle\tau_{1}$-match at a
particular position, removing 1 and reducing will not change it. Also, if
$\displaystyle\sigma$ does not have a $\displaystyle\tau_{1}$-match at some
position before 1, then removing $\displaystyle 1$ will not change
$\displaystyle\tau_{1}$-match at the position, since $\displaystyle 1$ can
only serve as $\displaystyle 1$ in $\displaystyle 1\underline{2}3$. However,
$\displaystyle 1$ appears after the position that
$\displaystyle\tau_{1}$-match occurs. Thus, $\displaystyle\sigma$ has a
$\displaystyle\tau_{1}$-match at the position without considering 1. Lastly,
if $\displaystyle\sigma$ has a $\displaystyle\tau_{1}$-match at some position
$\displaystyle t$ after 1. Note that 2 appears before 1 in
$\displaystyle\sigma$. Thus, 2 can serve as 1 in $\displaystyle
1\underline{2}3$. Therefore, $\displaystyle\sigma$ still has a
$\displaystyle\tau_{1}$-match at position $\displaystyle t$ when not
considering $\displaystyle 1$. So, we can remove $\displaystyle 1$ and reduce
without effecting $\displaystyle\tau_{1}$-match.

After removing 1 and reducing, the position of $\displaystyle 1$ will be
$\displaystyle\ell$. Thus, this case contributes
$\displaystyle\sum_{\ell=1}^{k-1}P_{n-1,\tau_{1},\ell}(x)$.

  2. 2.

$\displaystyle k+1\leq\ell\leq n-1$. In this case, $\displaystyle\sigma$ has a
$\displaystyle\tau_{1}$-match at position $\displaystyle\ell$ since
$\displaystyle 1~{}2~{}\sigma_{n}$ form the pattern $\displaystyle\tau_{1}$.
Moreover, by the same reason as in the first case, removing 2 and reducing
will not effect $\displaystyle\tau_{1}$-match at other position.

After removing 2 and reducing, the position of $\displaystyle 1$ is still
$\displaystyle\ell$. Thus, this case contributes $\displaystyle
x(n-k-1)P_{n-1,\tau_{1},k}(x)$.

  3. 3.

$\displaystyle\ell=n$. In this case, $\displaystyle\sigma$ does not have a
$\displaystyle\tau_{1}$-match at position $\displaystyle\ell$, and removing
$\displaystyle 2$ will not effect $\displaystyle\tau_{1}$-match at other
positions. Thus, this case contributes $\displaystyle P_{n-1,\tau_{1},k}(x)$

In total, we have

$\displaystyle\displaystyle P_{n,\tau_{1},k}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\left(\sum_{\ell=1}^{k-1}P_{n-1,\tau_{1},\ell}(x)\right)+x(n-k-1)P_{n-1,\tau_{1},k}(x)+P_{n-1,\tau_{1},k}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\left(\sum_{\ell=1}^{k-1}P_{n-1,\tau_{1},\ell}(x)\right)+(x(n-k-1)+1)P_{n-1,\tau_{1},k}(x).$

Note that, the first case vanishes when $\displaystyle k=1$, but the formula
is correct since it would contribute an empty summation. The second case
vanishes when $\displaystyle n-1\leq k\leq n$, but the formula is still
correct since $\displaystyle n-k-1=0$ for $\displaystyle k=n-1$ and
$\displaystyle P_{n-1,\tau_{1},n}(x)=0$ for $\displaystyle k=n$. The last case
also vanishes when $\displaystyle k=n$, but the formula is still correct as
$\displaystyle P_{n-1,\tau_{1},n}(x)=0$.

∎

Here, we prove a similar result of $\displaystyle\tau_{2}=13\underline{2}$.

######  Lemma 21.

Let $\displaystyle\tau_{2}=13\underline{2}$ and let $\displaystyle
P_{n,\tau_{2},k}(x)=x^{pmp_{\tau_{2}}(\sigma)}$ where the sum is over all
$\displaystyle\sigma\in S_{n}$ with 1 at position $\displaystyle k$. Then,
$\displaystyle P_{n,\tau_{2},k}(x)$ satisfies the following recursive formula:

$\displaystyle
P_{n,\tau_{2},k}(x)=\left(\sum_{\ell=1}^{k-1}P_{n-1,\tau_{2},\ell}(x)\right)+(x(n-k-1)+1)P_{n-1,\tau_{2},k}(x).$

###### Proof.

We derive a recursive formula for $\displaystyle P_{n,\tau_{2},k}(x)$ by
looking at the position of $\displaystyle 2$ in $\displaystyle\sigma$ where
the position of $\displaystyle 1$ is $\displaystyle k$. $\displaystyle\sigma$
has a following form

$\displaystyle\sigma=\sigma_{1}~{}\sigma_{2}~{}\ldots~{}\sigma_{k-1}~{}1~{}\sigma_{k+1}~{}\ldots~{}\sigma_{n}$

Let $\displaystyle l$ be the position of $\displaystyle 2$. We have 3 cases:

  1. 1.

$\displaystyle 1\leq\ell\leq k-1$. In this case, by the same reason as the
first case in the proof of Lemma 20, we can remove $\displaystyle 1$ from
$\displaystyle\sigma$ and reduce other elements without effecting
$\displaystyle\tau_{1}$-match at other positions.

After removing 1 and reducing, the position of $\displaystyle 1$ will be
$\displaystyle\ell$. Thus, this case contributes
$\displaystyle\sum_{\ell=1}^{k-1}P_{n-1,\tau_{2},\ell}(x)$.

  2. 2.

$\displaystyle\ell=k+1$. In this case, $\displaystyle\sigma$ does not have a
$\displaystyle\tau_{2}$-match at position $\displaystyle\ell$, and removing
$\displaystyle 2$ will not effect $\displaystyle\tau_{2}$-match at other
positions by the same reason as above. Thus, this case contributes
$\displaystyle P_{n-1,\tau_{2},k}(x).$

  3. 3.

$\displaystyle k+2\leq\ell\leq n$. In this case, $\displaystyle\sigma$ has a
$\displaystyle\tau_{2}$-match at position $\displaystyle\ell$ since
$\displaystyle 1~{}\sigma_{k+1}~{}2$ form the pattern $\displaystyle\tau_{2}$.
Moreover, by the same reason as above, removing 2 and reducing will not effect
$\displaystyle\tau_{2}$-match at other position.

After removing 2 and reducing, the position of $\displaystyle 1$ is still at
$\displaystyle\ell$. Thus, this case contribute $\displaystyle
x(n-k-1)P_{n-1,\tau_{2},k}(x)$.

In total, we have

$\displaystyle\displaystyle P_{n,\tau_{2},k}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle\left(\sum_{\ell=1}^{k-1}P_{n-1,\tau_{2},\ell}(x)\right)+x(n-k-1)P_{n-1,\tau_{2},k}(x)+P_{n-1,\tau_{2},k}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\left(\sum_{\ell=1}^{k-1}P_{n-1,\tau_{2},\ell}(x)\right)+(x(n-k-1)+1)P_{n-1,\tau_{2},k}(x).$

Note that the first case vanishes when $\displaystyle k=1$, but the formula is
still correct as it contributes an empty summation. The second case vanishes
when $\displaystyle k=n$. The formula is still correct as $\displaystyle
P_{n-1,\tau_{2},n}(x)=0$. The last case vanishes when $\displaystyle k=n-1,n$.
When $\displaystyle k=n-1$, the formula is correct as $\displaystyle n-k-1=0$.
When $\displaystyle k=n$, the formula is correct as $\displaystyle
P_{n-1,\tau_{2},n}(x)=0$ .

∎

It is easy to see that $\displaystyle
P_{1,\tau_{1},1}(x)=1=P_{1,\tau_{2},1}(x)$. Since, $\displaystyle
P_{n,\tau_{1},k}(x)$ and $\displaystyle P_{n,\tau_{2},k}(x)$ satisfy the same
recursive formula and have the same initial values, we prove that
$\displaystyle P_{n,\tau_{1},k}(x)=P_{n,\tau_{2},k}(x)$ for all $\displaystyle
n,k$ such that $\displaystyle 1\leq k\leq n$, and thus $\displaystyle
P_{n,\tau_{1}}(x)=P_{n,\tau_{2}}(x)$ for all $\displaystyle n\geq 1$. Hence,
we prove Theorem 2.

We also construct a bijection $\displaystyle\theta:S_{n}\rightarrow S_{n}$
such that $\displaystyle
pmp_{\tau_{1}}(\sigma)=pmp_{\tau_{2}}(\theta(\sigma))$ based on the recursive
formula. We define $\displaystyle\theta(1)=1,\theta(12)=12$ and
$\displaystyle\theta(21)=21$. In general, $\displaystyle\theta$ will satisfies
the following properties:

  1. 1.

The position of 1 in $\displaystyle\sigma$ is the same as the position of 1 in
$\displaystyle\theta(\sigma)$.

  2. 2.

$\displaystyle pmp_{\tau_{1}}(\sigma)=pmp_{\tau_{2}}(\theta(\sigma)).$

$\displaystyle\theta$ satisfies the properties for $\displaystyle S_{1}$ and
$\displaystyle S_{2}$. For $\displaystyle S_{n+1}$ where $\displaystyle n\geq
2$, we define the map recursively. Given $\displaystyle\sigma\in S_{n}$, we
have $\displaystyle\sigma^{\prime}=\theta(\sigma)$. We know that the position
of 1 in $\displaystyle\sigma$ is the same as the position of 1 in
$\displaystyle\sigma^{\prime}$. Let $\displaystyle k$ be the position.

Here, we obtain an element $\displaystyle\hat{\sigma}\in S_{n+1}$ by applying
one of the following:

  1. 1.

Increase every element by 1, and insert 1 at or after position $\displaystyle
k+1$.

  2. 2.

Increase every element except 1 by 1, and insert 2 at or after position
$\displaystyle k+1$.

Then, we obtain $\displaystyle\theta(\hat{\sigma})$ by applying similar action
to $\displaystyle\sigma^{\prime}$ based on an action applied to
$\displaystyle\sigma$:

  1. 1.

If 1 was inserted to $\displaystyle\sigma$, then increase every element in
$\displaystyle\sigma^{\prime}$ by 1 and insert 1 at the same position as
inserted in $\displaystyle\sigma$.

  2. 2.

If 2 was inserted to $\displaystyle\sigma$ at position $\displaystyle r$, then
increase every element in $\displaystyle\sigma^{\prime}$ except 1 by 1 and
insert 2 at position $\displaystyle r^{\prime}$ where

$\displaystyle r^{\prime}=\left\\{\begin{array}[]{ll}r+1&k+1\leq r\leq n\\\
k+1&r=n+1\end{array}\right..$

Corresponding positions when inserting 1 or 2 can be viewed from Figure 5 and
Firgure 6.

$\displaystyle\sigma_{1}$$\displaystyle\sigma_{2}$$\displaystyle\sigma_{k-1}$$\displaystyle
1$$\displaystyle\sigma_{k+1}$$\displaystyle\sigma_{k+2}$$\displaystyle\sigma_{n-1}$$\displaystyle\sigma_{n}$$\displaystyle\sigma^{\prime}_{1}$$\displaystyle\sigma^{\prime}_{2}$$\displaystyle\sigma^{\prime}_{k-1}$$\displaystyle
1$$\displaystyle\sigma^{\prime}_{k+1}$$\displaystyle\sigma^{\prime}_{k+2}$$\displaystyle\sigma^{\prime}_{n-1}$$\displaystyle\sigma^{\prime}_{n}$
Figure 5: Corresponding positions when inserting 1
$\displaystyle\sigma_{1}$$\displaystyle\sigma_{2}$$\displaystyle\sigma_{k-1}$$\displaystyle
1$$\displaystyle\sigma_{k+1}$$\displaystyle\sigma_{k+2}$$\displaystyle\sigma_{n-1}$$\displaystyle\sigma_{n}$$\displaystyle\sigma^{\prime}_{1}$$\displaystyle\sigma^{\prime}_{2}$$\displaystyle\sigma^{\prime}_{k-1}$$\displaystyle
1$$\displaystyle\sigma^{\prime}_{k+1}$$\displaystyle\sigma^{\prime}_{k+2}$$\displaystyle\sigma^{\prime}_{n-1}$$\displaystyle\sigma^{\prime}_{n}$
Figure 6: Corresponding positions when inserting 2

The position of $\displaystyle 1$ in $\displaystyle\hat{\sigma}$ and
$\displaystyle\theta(\hat{\sigma})$ will be the same. Also, $\displaystyle
pmp_{\tau_{1}}(\sigma)$ would increase by $\displaystyle 1$ if and only if 2
was inserted at a non-last position, while $\displaystyle
pmp_{\tau_{2}}({\sigma^{\prime}})$ will increase by 1 if and only if 2 was
inserted at any position but $\displaystyle k+1$. Thus, $\displaystyle
pmp_{\tau_{1}}(\hat{\sigma})=pmp_{\tau_{2}}(\theta(\hat{\sigma}))$. Also, it
is not hard to see that every $\displaystyle\sigma\in S_{n}$ can be obtained
by inserting 1 or 2 repeatedly in a unique way. Therefore,
$\displaystyle\theta$ is a bijection.

As an example, we start with $\displaystyle\theta(12)=12$. Say, we would like
to insert 2, then the diagram looks like

$\displaystyle 1$$\displaystyle 2$$\displaystyle 1$$\displaystyle 2$

.

Suppose we insert 2 to the preimage 12 at the last position, so then get
$\displaystyle 132$. According to the diagram, we should insert 2 to the image
12 at the first position, so we get $\displaystyle 123$. Thus,
$\displaystyle\theta(132)=123$. Here, suppose we would like to insert 1, then
the diagram looks like:

$\displaystyle 1$$\displaystyle 3$$\displaystyle 2$$\displaystyle
1$$\displaystyle 2$$\displaystyle 3$

.

Suppose we insert 1 to 132 at the first position, then we get 2143. According
to the diagram, we insert 1 to 123 at the same position, so we get 2134. Thus,
$\displaystyle\theta(2143)=2134$.

Now, suppose we want to insert 2. The diagram looks like:

$\displaystyle 2$$\displaystyle 1$$\displaystyle 3$$\displaystyle
4$$\displaystyle 2$$\displaystyle 1$$\displaystyle 4$$\displaystyle 3$

.

Suppose we insert 2 to 2134 at the second position, so we get $\displaystyle
31245$. According to the diagram, we insert 2 to $\displaystyle 2143$ at the
last position, so we get 31542. Thus, $\displaystyle\theta(31245)=31542$.

Below are enumerations of $\displaystyle P_{n,1\underline{2}3}(x)$ for the
first few $\displaystyle n$.

$\displaystyle\displaystyle P_{1,1\underline{2}3}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle{1}$
$\displaystyle\displaystyle P_{2,1\underline{2}3}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle{2}$
$\displaystyle\displaystyle P_{3,1\underline{2}3}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle{5+x}$
$\displaystyle\displaystyle P_{4,1\underline{2}3}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle{14+8x+2x^{2}}$
$\displaystyle\displaystyle P_{5,1\underline{2}3}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle{42+46x+26x^{2}+6x^{3}}$
$\displaystyle\displaystyle P_{6,1\underline{2}3}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle{132+232x+220x^{2}+112x^{3}+24x^{4}}$
$\displaystyle\displaystyle P_{7,1\underline{2}3}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle{429+1093x+1527x^{2}+1275x^{3}+596x^{4}+120x^{5}}$
$\displaystyle\displaystyle P_{8,1\underline{2}3}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle{1430+4944x+9436x^{2}+11384x^{3}+8638x^{4}+3768x^{5}+720x^{6}}$

Remark In fact, the equivalence of $\displaystyle 1\underline{2}3$ and
$\displaystyle\underline{2}13$ follows a general result from Theorem 3.

##  4 Equivalence classes of $\displaystyle S_{4}^{*}$

There are $\displaystyle 4!\cdot 4=96$ $\displaystyle pmp$ in $\displaystyle
S_{4}^{*}$. However, there are at most 16 equivalent classes by Lemma 7. All
the representatives are listed in Figure 7.

$\displaystyle\young(\hfil\hfil\hfil\times,\hfil\hfil\times\hfil,\hfil\times\hfil\hfil,\circ\hfil\hfil\hfil)$ $\displaystyle\underline{1}234$ |  $\displaystyle\young(\hfil\hfil\hfil\times,\hfil\hfil\times\hfil,\hfil\circ\hfil\hfil,\times\hfil\hfil\hfil)$ $\displaystyle 1\underline{2}34$ |  $\displaystyle\young(\hfil\hfil\times\hfil,\hfil\hfil\hfil\times,\hfil\times\hfil\hfil,\circ\hfil\hfil\hfil)$ $\displaystyle\underline{1}243$ |  $\displaystyle\young(\hfil\hfil\times\hfil,\hfil\hfil\hfil\times,\hfil\circ\hfil\hfil,\times\hfil\hfil\hfil)$ $\displaystyle 1\underline{2}43$
---|---|---|---
$\displaystyle\young(\hfil\hfil\circ\hfil,\hfil\hfil\hfil\times,\hfil\times\hfil\hfil,\times\hfil\hfil\hfil)$ $\displaystyle 12\underline{4}3$ |  $\displaystyle\young(\hfil\times\hfil\hfil,\hfil\hfil\times\hfil,\hfil\hfil\hfil\times,\circ\hfil\hfil\hfil)$ $\displaystyle\underline{1}432$ |  $\displaystyle\young(\hfil\circ\hfil\hfil,\hfil\hfil\times\hfil,\hfil\hfil\hfil\times,\times\hfil\hfil\hfil)$ $\displaystyle 1\underline{4}32$ |  $\displaystyle\young(\hfil\times\hfil\hfil,\hfil\hfil\circ\hfil,\hfil\hfil\hfil\times,\times\hfil\hfil\hfil)$ $\displaystyle 14\underline{3}2$
$\displaystyle\young(\hfil\hfil\times\hfil,\hfil\hfil\hfil\times,\circ\hfil\hfil\hfil,\hfil\times\hfil\hfil)$ $\displaystyle\underline{2}143$ |  $\displaystyle\young(\hfil\hfil\times\hfil,\hfil\times\hfil\hfil,\hfil\hfil\hfil\times,\circ\hfil\hfil\hfil)$ $\displaystyle\underline{1}342$ |  $\displaystyle\young(\hfil\hfil\times\hfil,\hfil\circ\hfil\hfil,\hfil\hfil\hfil\times,\times\hfil\hfil\hfil)$ $\displaystyle 1\underline{3}42$ |  $\displaystyle\young(\hfil\hfil\circ\hfil,\hfil\times\hfil\hfil,\hfil\hfil\hfil\times,\times\hfil\hfil\hfil)$ $\displaystyle 13\underline{4}2$
$\displaystyle\young(\hfil\hfil\times\hfil,\hfil\times\hfil\hfil,\hfil\hfil\hfil\circ,\times\hfil\hfil\hfil)$ $\displaystyle 134\underline{2}$ |  $\displaystyle\young(\hfil\times\hfil\hfil,\hfil\hfil\hfil\times,\circ\hfil\hfil\hfil,\hfil\hfil\times\hfil)$ $\displaystyle\underline{2}413$ |  $\displaystyle\young(\hfil\hfil\hfil\times,\hfil\times\hfil\hfil,\hfil\hfil\times\hfil,\circ\hfil\hfil\hfil)$ $\displaystyle\underline{1}324$ |  $\displaystyle\young(\hfil\hfil\hfil\times,\hfil\circ\hfil\hfil,\hfil\hfil\times\hfil,\times\hfil\hfil\hfil)$ $\displaystyle 1\underline{3}24$
Figure 7: Diagrams of representatives of $\displaystyle pmp$ of length 4 after
considering geometrical equivalence

In this section, we present numerical results suggesting that there are 10
equivalent classes in $\displaystyle S_{4}^{*}$. We then will show that the
following patterns are equivalent: $\displaystyle
1\underline{2}34,1\underline{2}43,2\underline{1}34,2\underline{1}43$.

###  4.1 Numerical data

Here, for each pattern $\displaystyle\tau$ shown in Figure 7, we enumerate
polynomials $\displaystyle P_{n,\tau}(x)$ for small $\displaystyle n$. We also
group patterns together if they seem to provide the same polynomials.

####  4.1.1
$\displaystyle\tau=\underline{1}234,\underline{1}243,\underline{1}432$

$\displaystyle\displaystyle P_{1,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 1$ $\displaystyle\displaystyle P_{2,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 2$
$\displaystyle\displaystyle P_{3,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 6$ $\displaystyle\displaystyle P_{4,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 23+x$
$\displaystyle\displaystyle P_{5,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 103+15x+2x^{2}$ $\displaystyle\displaystyle
P_{6,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
513+158x+43x^{2}+6x^{3}$ $\displaystyle\displaystyle P_{7,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle
2761+1466x+619x^{2}+170x^{3}+24x^{4}$ $\displaystyle\displaystyle
P_{8,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
15767+12864x+7598x^{2}+3121x^{3}+850x^{4}+120x^{5}$

####  4.1.2
$\displaystyle\tau=1\underline{2}34,1\underline{2}43,12\underline{4}3,\underline{2}143$

$\displaystyle\displaystyle P_{1,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 1$ $\displaystyle\displaystyle P_{2,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 2$
$\displaystyle\displaystyle P_{3,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 6$ $\displaystyle\displaystyle P_{4,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 23+x$
$\displaystyle\displaystyle P_{5,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 103+15x+2x^{2}$ $\displaystyle\displaystyle
P_{6,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
513+157x+44x^{2}+6x^{3}$ $\displaystyle\displaystyle P_{7,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle
2761+1439x+638x^{2}+178x^{3}+24x^{4}$ $\displaystyle\displaystyle
P_{8,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
15767+12420x+7764x^{2}+3341x^{3}+908x^{4}+120x^{5}$

####  4.1.3 $\displaystyle\tau=1\underline{4}32$

$\displaystyle\displaystyle P_{1,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 1$ $\displaystyle\displaystyle P_{2,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 2$
$\displaystyle\displaystyle P_{3,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 6$ $\displaystyle\displaystyle P_{4,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 23+x$
$\displaystyle\displaystyle P_{5,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 103+15x+2x^{2}$ $\displaystyle\displaystyle
P_{6,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
513+157x+44x^{2}+6x^{3}$ $\displaystyle\displaystyle P_{7,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle
2761+1438x+640x^{2}+177x^{3}+24x^{4}$ $\displaystyle\displaystyle
P_{8,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
15767+12393x+7809x^{2}+3332x^{3}+899x^{4}+120x^{5}$

####  4.1.4 $\displaystyle\tau=14\underline{3}2$

$\displaystyle\displaystyle P_{1,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 1$ $\displaystyle\displaystyle P_{2,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 2$
$\displaystyle\displaystyle P_{3,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 6$ $\displaystyle\displaystyle P_{4,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 23+x$
$\displaystyle\displaystyle P_{5,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 103+15x+2x^{2}$ $\displaystyle\displaystyle
P_{6,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
513+156x+45x^{2}+6x^{3}$ $\displaystyle\displaystyle P_{7,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle
2761+1415x+655x^{2}+185x^{3}+24x^{4}$ $\displaystyle\displaystyle
P_{8,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
15767+12058x+7895x^{2}+3524x^{3}+956x^{4}+120x^{5}$

####  4.1.5 $\displaystyle\tau=\underline{1}342$

$\displaystyle\displaystyle P_{1,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 1$ $\displaystyle\displaystyle P_{2,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 2$
$\displaystyle\displaystyle P_{3,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 6$ $\displaystyle\displaystyle P_{4,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 23+x$
$\displaystyle\displaystyle P_{5,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 103+15x+2x^{2}$ $\displaystyle\displaystyle
P_{6,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
512+160x+42x^{2}+6x^{3}$ $\displaystyle\displaystyle P_{7,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle
2740+1500x+614x^{2}+162x^{3}+24x^{4}$ $\displaystyle\displaystyle
P_{8,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
15485+13207x+7700x^{2}+3016x^{3}+792x^{4}+120x^{5}$

####  4.1.6 $\displaystyle\tau=1\underline{3}42$

$\displaystyle\displaystyle P_{1,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 1$ $\displaystyle\displaystyle P_{2,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 2$
$\displaystyle\displaystyle P_{3,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 6$ $\displaystyle\displaystyle P_{4,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 23+x$
$\displaystyle\displaystyle P_{5,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 103+15x+2x^{2}$ $\displaystyle\displaystyle
P_{6,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
512+158x+44x^{2}+6x^{3}$ $\displaystyle\displaystyle P_{7,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle
2740+1451x+646x^{2}+179x^{3}+24x^{4}$ $\displaystyle\displaystyle
P_{8,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
15485+12455x+7912x^{2}+3427x^{3}+921x^{4}+120x^{5}$

####  4.1.7 $\displaystyle\tau=13\underline{4}2,\underline{2}413$

$\displaystyle\displaystyle P_{1,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 1$ $\displaystyle\displaystyle P_{2,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 2$
$\displaystyle\displaystyle P_{3,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 6$ $\displaystyle\displaystyle P_{4,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 23+x$
$\displaystyle\displaystyle P_{5,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 103+15x+2x^{2}$ $\displaystyle\displaystyle
P_{6,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
512+158x+44x^{2}+6x^{3}$ $\displaystyle\displaystyle P_{7,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle
2740+1454x+644x^{2}+178x^{3}+24x^{4}$ $\displaystyle\displaystyle
P_{8,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
15485+12533x+7897x^{2}+3377x^{3}+908x^{4}+120x^{5}$

####  4.1.8 $\displaystyle\tau=134\underline{2}$

$\displaystyle\displaystyle P_{1,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 1$ $\displaystyle\displaystyle P_{2,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 2$
$\displaystyle\displaystyle P_{3,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 6$ $\displaystyle\displaystyle P_{4,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 23+x$
$\displaystyle\displaystyle P_{5,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 103+15x+2x^{2}$ $\displaystyle\displaystyle
P_{6,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
512+159x+43x^{2}+6x^{3}$ $\displaystyle\displaystyle P_{7,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle
2740+1475x+629x^{2}+172x^{3}+24x^{4}$ $\displaystyle\displaystyle
P_{8,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
15485+12817x+7781x^{2}+3244x^{3}+873x^{4}+120x^{5}$

####  4.1.9 $\displaystyle\tau=\underline{1}324$

$\displaystyle\displaystyle P_{1,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 1$ $\displaystyle\displaystyle P_{2,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 2$
$\displaystyle\displaystyle P_{3,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 6$ $\displaystyle\displaystyle P_{4,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 23+x$
$\displaystyle\displaystyle P_{5,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 103+15x+2x^{2}$ $\displaystyle\displaystyle
P_{6,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
513+158x+43x^{2}+6x^{3}$ $\displaystyle\displaystyle P_{7,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle
2762+1464x+620x^{2}+170x^{3}+24x^{4}$ $\displaystyle\displaystyle
P_{8,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
15793+12820x+7608x^{2}+3129x^{3}+850x^{4}+120x^{5}$

####  4.1.10 $\displaystyle\tau=1\underline{3}24$

$\displaystyle\displaystyle P_{1,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 1$ $\displaystyle\displaystyle P_{2,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 2$
$\displaystyle\displaystyle P_{3,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 6$ $\displaystyle\displaystyle P_{4,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle 23+x$
$\displaystyle\displaystyle P_{5,\tau}(x)$ $\displaystyle\displaystyle=$
$\displaystyle\displaystyle 103+15x+2x^{2}$ $\displaystyle\displaystyle
P_{6,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
513+156x+45x^{2}+6x^{3}$ $\displaystyle\displaystyle P_{7,\tau}(x)$
$\displaystyle\displaystyle=$ $\displaystyle\displaystyle
2762+1414x+654x^{2}+186x^{3}+24x^{4}$ $\displaystyle\displaystyle
P_{8,\tau}(x)$ $\displaystyle\displaystyle=$ $\displaystyle\displaystyle
15793+12041x+7861x^{2}+3539x^{3}+966x^{4}+120x^{5}$

###  4.2 Equivalence of $\displaystyle
1\underline{2}34,1\underline{2}43,\underline{2}134$ and
$\displaystyle\underline{2}143$

Here, we prove an equivalence of four patterns: $\displaystyle
1\underline{2}34,1\underline{2}43,\underline{2}134$ and
$\displaystyle\underline{2}143$. Note that, they are equivalent to four
patterns appearing in Section 4.1.2, since $\displaystyle\underline{2}134$ and
$\displaystyle 12\underline{4}3$ are equivalent.

( ×, × ,∘ , × ) ( ∘ , ×, × ,× )

Diagrams of $\displaystyle\underline{2}134$ and $\displaystyle
12\underline{4}3$

The equivalence of $\displaystyle 1\underline{2}34$ and
$\displaystyle\underline{2}134$ as well as the equivalence of $\displaystyle
1\underline{2}43$ and $\displaystyle\underline{2}143$ follow a more general
Theorem 3. Thus, in this section, we only prove the equivalence of
$\displaystyle 1\underline{2}34$ and $\displaystyle 1\underline{2}43$.

######  Theorem 22.

Two pmp $\displaystyle 1\underline{2}34$ and $\displaystyle 1\underline{2}43$
are pmp-Wilf equivalent.

For our convenience, let $\displaystyle\tau_{1}=1\underline{2}34$. Let
$\displaystyle P_{n,\tau_{1},s}(x)=\sum_{\sigma}x^{pmp_{\tau_{1}}(\sigma)}$,
where the sum is over all $\displaystyle\sigma\in S_{n}$ with the last ascent
of $\displaystyle\sigma$ at position $\displaystyle s$. Let $\displaystyle
P_{n,\tau_{1},s,t}(x)=\sum_{\sigma}x^{pmp_{\tau_{1}}(\sigma)}$, where the sum
is over all $\displaystyle\sigma\in S_{n}$ with the last ascent of
$\displaystyle\sigma$ at position $\displaystyle s$ and 1 at position
$\displaystyle t$. All feasible values of $\displaystyle s$ are $\displaystyle
1,2,\ldots,n-1$. All feasible values of $\displaystyle t$ are $\displaystyle
1,2,\ldots,s,n$ for $\displaystyle s\neq n-1$, and $\displaystyle
1,2,\ldots,n-1$ for $\displaystyle s=n-1$. Thus,

$\displaystyle P_{n,\tau_{1}}(x)=1+\sum_{s=1}^{n-1}P_{n,\tau_{1},s}(x)$

Also,

$P_{n,\tau_{1},s}(x)=\left(\sum_{t=1}^{s}P_{n,\tau_{1},s,t}(x)\right)+P_{n,\tau_{1},s,n}(x).$
(4.1)

Note that the second term vanishes as $\displaystyle s=n-1$. Here, we derive a
recursive formula for $\displaystyle P_{n,\tau_{1},s,t}(x)$.

######  Lemma 23.

$\displaystyle P_{n,\tau_{1},s,t}(x)$ satisfies the following recursive
formulas:

$\displaystyle
P_{n,\tau_{1},s,t}(x)=\sum_{\ell=1}^{t-1}P_{n-1,\tau_{1},s-1,\ell}(x)+(s-1-t)xP_{n-1,\tau_{1},s-1,t}(x)+\sum_{j=t+1}^{s}P_{n-1,\tau_{1},j,t}(x)+P_{n-1,\tau_{1},t,t}(x)$

for $\displaystyle 1\leq t<s\leq n-1,$

$\displaystyle P_{n,\tau_{1},s,s}(x)=1+\sum_{i=1}^{s-1}P_{n-1,\tau_{1},i}(x)$

for $\displaystyle 1\leq s\leq n-1$, and

$\displaystyle P_{n,\tau_{1},s,n}(x)=P_{n-1,\tau_{1},s}(x)$

for $\displaystyle 1\leq s<n-1$.

By convention, Let $\displaystyle P_{n,\tau_{1},s,t}(x)=0$ for infeasible
value of $\displaystyle s,t$.

###### Proof.

First, consider the formula for $\displaystyle P_{n,\tau_{1},s,t}(x)$ when
$\displaystyle 1\leq t<s\leq n-1.$ Let $\displaystyle\ell$ be the position of
$\displaystyle 2$ in $\displaystyle\sigma$, where $\displaystyle\sigma\in
S_{n}$ with the last ascent of $\displaystyle\sigma$ at position
$\displaystyle s$ and 1 at position $\displaystyle t$. We have 4 cases:

  1. 1.

$\displaystyle 1\leq\ell\leq t-1$. In this case, we can remove $\displaystyle
1$ from $\displaystyle\sigma$ without effecting a
$\displaystyle\tau_{1}$-match at other positions. That is because
$\displaystyle\sigma$ does not have a $\displaystyle\tau_{1}$-match at the
position of $\displaystyle 2$, and if $\displaystyle\sigma$ has a
$\displaystyle\tau_{1}$-match at other positions and matching involves 1, it
can still have a $\displaystyle\tau_{1}$-match by using 2 instead of 1.

After removing and reducing, the position of 1 is $\displaystyle\ell$, and the
position of the last ascent is $\displaystyle s-1$. Thus, this case
contributes $\displaystyle\sum_{\ell=1}^{t-1}P_{n-1,\tau_{1},s-1,\ell}(x)$.

  2. 2.

$\displaystyle t+1\leq\ell\leq s-1$. In this case, $\displaystyle\sigma$ has a
$\displaystyle\tau_{1}$-match at position $\displaystyle\ell$ since
$\displaystyle 1~{}2~{}\sigma_{s}~{}\sigma_{s+1}$ form the pattern
$\displaystyle\tau_{1}$. By the same reasoning as the first case, we can
remove 2 without effecting $\displaystyle\tau_{1}$-match at any other
positions.

After removing and reducing, the position of $\displaystyle 1$ stays at
$\displaystyle t$ and the position of the last ascent is $\displaystyle s-1$.
Thus, this case contributes $\displaystyle x(s-1-t)P_{n-1,\tau_{1},s-1,t}(x)$.

  3. 3.

$\displaystyle\ell=s$. In this case, we can remove 2 without effecting a
$\displaystyle\tau_{1}$-match at other positions.

After removing and reducing, the position of $\displaystyle 1$ stays at
$\displaystyle t$ and the last ascent appears at some position between
$\displaystyle t$ and $\displaystyle s-1$. Thus, this case contributes
$\displaystyle\sum_{j=t}^{s-1}P_{n-1,\tau_{1},j,t}(x)$.

  4. 4.

$\displaystyle\ell=n$. In this case, we can remove 2 without effecting a
$\displaystyle\tau_{1}$-match at other positions. After removing and reducing,
the position of 1 stays at $\displaystyle t$ and the position of the last
ascent stays at $\displaystyle s$. Thus, this case contributes $\displaystyle
P_{n-1,\tau_{1},s,t}(x)$.

In total, we have

$\displaystyle\displaystyle P_{n,\tau_{1},s,t}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\sum_{\ell=1}^{t-1}P_{n-1,\tau_{1},s-1,\ell}(x)+(s-1-t)xP_{n-1,\tau_{1},s-1,t}(x)+\sum_{j=t}^{s-1}P_{n-1,\tau_{1},j,t}(x)+P_{n-1,\tau_{1},s,t}(x)$
$\displaystyle\displaystyle=$
$\displaystyle\displaystyle\sum_{\ell=1}^{t-1}P_{n-1,\tau_{1},s-1,\ell}(x)+(s-1-t)xP_{n-1,\tau_{1},s-1,t}(x)+\sum_{j=t+1}^{s}P_{n-1,\tau_{1},j,t}(x)+P_{n-1,\tau_{1},t,t}(x)$

Note that, the first case vanishes if $\displaystyle t=1$, but the formula is
consistent as it contributes an empty summation. The second case vanishes when
$\displaystyle t=s-1$, but the formula is still correct as $\displaystyle
P_{n-1,\tau_{1},s-1,s}(x)=0$. The last case vanishes when $\displaystyle
s=n-1$, but the formula is correct as $\displaystyle
P_{n-1,\tau_{1},n-1,t}(x)=0$. Thus, we prove the first formula.

Here, we derive a recursive formula for $\displaystyle P_{n,\tau_{1},s,s}(x)$
when $\displaystyle 1\leq s\leq n-1$. Given any $\displaystyle\sigma\in S_{n}$
such that the position of 1 and the position of the last ascent is
$\displaystyle s$. Removing 1 does not effect a $\displaystyle\tau_{1}$-match
at other positions. After removing and reducing, the permutation either has no
ascent, or the last ascent is at some position between 1 and $\displaystyle
s-1$. Thus, we have

$\displaystyle P_{n,\tau_{1},s,s}(x)=1+\sum_{i=1}^{s-1}P_{n-1,\tau_{1},i}(x).$

Lastly, we derive a formula for $\displaystyle P_{n,\tau_{1},s,n}(x)$ when
$\displaystyle 1\leq s<n-1$. Given any $\displaystyle\sigma$ such that the
position of the last ascent is $\displaystyle s$ and 1 is at the last
position. Removing 1 will not effect $\displaystyle\tau_{1}$-match at other
positions. The position of the last ascent is still $\displaystyle s$. Thus,
we have

$\displaystyle P_{n,\tau_{1},s,n}(x)=P_{n-1,\tau_{1},s}(x).$

∎

We shall prove similar result for $\displaystyle 1\underline{2}43$. Let
$\displaystyle\tau_{2}=1\underline{2}43$. Let $\displaystyle
P_{n,\tau_{2},s}(x)=\sum_{\sigma}x^{pmp_{\tau_{2}}(\sigma)}$, where the sum is
over all $\displaystyle\sigma\in S_{n}$ with the last descent of
$\displaystyle\sigma$ at position $\displaystyle s$. Let $\displaystyle
P_{n,\tau_{2},s,t}(x)=\sum_{\sigma}x^{pmp_{\tau_{2}}(\sigma)}$, where the sum
is over all $\displaystyle\sigma\in S_{n}$ with the last descent of
$\displaystyle\sigma$ at position $\displaystyle s$ and 1 at position
$\displaystyle t$. All feasible values of $\displaystyle s$ are $\displaystyle
1,2,\ldots,n-1$. All feasible values of $\displaystyle t$ are $\displaystyle
t=1,2,\ldots,s-1$ and $\displaystyle s+1$. Note that, when $\displaystyle
s=1$, the only possible value for $\displaystyle t$ is 2. Thus, we have

$\displaystyle P_{n,\tau_{2}}(x)=1+\sum_{s=1}^{n-1}P_{n,\tau_{2},s}(x).$

Also,

$P_{n,\tau_{2},s}(x)=\left(\sum_{t=1}^{s-1}P_{n,\tau_{2},s,t}(x)\right)+P_{n,\tau_{2},s,s+1}(x).$
(4.2)

Here, we derive a recursive formula for $\displaystyle P_{n,\tau_{2},s}(x)$.

######  Lemma 24.

$\displaystyle P_{n,\tau_{2},s,t}(x)$ satisfies the following recursive
formulas:

$\displaystyle
P_{n,\tau_{2},s,t}(x)=\sum_{\ell=1}^{t-1}P_{n-1,\tau_{2},s-1,\ell}(x)+(s-1-t)xP_{n-1,\tau_{2},s-1,t}(x)+\sum_{j=t+1}^{s}P_{n-1,\tau_{2},j,t}(x)+P_{n-1,\tau_{2},t-1,t}(x).$

for $\displaystyle 1\leq t<s\leq n-1,$

$\displaystyle P_{n,\tau_{2},s,s+1}(x)=1+\sum_{i=1}^{s}P_{n-1,\tau_{2},i}(x)$

for $\displaystyle 1\leq s\leq n-1$, and

By convention, let $\displaystyle P_{n,\tau_{2},s,t}(x)=0$ for infeasible
value of $\displaystyle s,t$.

###### Proof.

First, consider the formula for $\displaystyle P_{n,\tau_{2},s,t}(x)$ when
$\displaystyle 1\leq t<s\leq n-1$. Let $\displaystyle\ell$ be the position of
2 in $\displaystyle\sigma$, where $\displaystyle\sigma\in S_{n}$ with the last
descent of $\displaystyle\sigma$ at position $\displaystyle s$ and 1 at
position $\displaystyle t$. we have 4 cases:

  1. 1.

$\displaystyle 1\leq\ell\leq t-1$. In this case, $\displaystyle\sigma$ does
not have a $\displaystyle\tau_{2}$-match at position $\displaystyle\ell$. We
can remove 1 from $\displaystyle\sigma$ without effecting
$\displaystyle\tau_{2}$-match at other positions. That is because if
$\displaystyle\sigma$ has a $\displaystyle\tau_{2}$-match at other positions
and the matching involves 1, it still has a $\displaystyle\tau_{2}$-match by
using $\displaystyle 2$ instead of $\displaystyle 1$.

After removing and reducing, the position of $\displaystyle 1$ is
$\displaystyle\ell$ and the position of the last descent is $\displaystyle
s-1$. Thus, this case contributes
$\displaystyle\sum_{\ell=1}^{t-1}P_{n-1,\tau_{2},s-1,\ell}(x)$.

  2. 2.

$\displaystyle t+1\leq\ell\leq s-1$. In this case, $\displaystyle\sigma$ has a
$\displaystyle\tau_{2}$-match at position $\displaystyle\ell$ since
$\displaystyle 1~{}2~{}\sigma_{s}~{}\sigma_{s+1}$ form the pattern
$\displaystyle\tau_{2}$. By the same reasoning as the first case, we can
remove 2 without effecting $\displaystyle\tau_{2}$-match at any other
positions.

After removing and reducing, the position of $\displaystyle 1$ stays at
$\displaystyle t$ and the position of the last descent is $\displaystyle s-1$.
Thus, this case contributes $\displaystyle x(s-1-t)P_{n-1,\tau_{1},s-1,t}(x)$.

  3. 3.

$\displaystyle\ell=s$. In this case, we can remove 2 without effecting
$\displaystyle\tau_{2}$-match at other positions.

After removing and reducing, the position of $\displaystyle 1$ stays at
$\displaystyle t$ and the last descent appears at some position between
$\displaystyle t+1$ and $\displaystyle s$, or at the position $\displaystyle
t-1$ (right before 1). Thus, this case contributes
$\displaystyle\sum_{j=t+1}^{s}P_{n-1,\tau_{2},j,t}(x)+P_{n-1,\tau_{2},t-1,t}(x)$.

In total, we have

$\displaystyle
P_{n,\tau_{2},s,t}(x)=\sum_{\ell=1}^{t-1}P_{n-1,\tau_{2},s-1,\ell}(x)+(s-1-t)xP_{n-1,\tau_{2},s-1,t}(x)+\sum_{j=t+1}^{s}P_{n-1,\tau_{2},j,t}(x)+P_{n-1,\tau_{2},t-1,t}(x).$

Note that, the first case vanishes if $\displaystyle t=1$, but the formula is
consistent as it contributes an empty summation. The second case vanishes when
$\displaystyle t=s-1$, but the formula is still correct as $\displaystyle
P_{n-1,\tau_{2},s-1,s}(x)=0$. The last case vanishes when $\displaystyle
s=n-1$, but the formula is correct as $\displaystyle
P_{n-1,\tau_{2},n-1,t}(x)=0$. Thus, we prove the first formula.

Next, we derive the recursive formula for $\displaystyle
P_{n,\tau_{2},s,s+1}(x)$ for $\displaystyle 1\leq s\leq n-1$. Given any
$\displaystyle\sigma\in S_{n}$ such that the position of the last descent is
$\displaystyle s$ and the position of 1 is $\displaystyle s+1$. Removing 1
will not effect $\displaystyle\tau_{2}$-matching at other positions. After
removing and reducing, the remaining permutation either has no descent, or the
last descent is at some position between 1 and $\displaystyle s$. Thus, we
have

$\displaystyle P_{n,\tau_{2},s,s+1}(x)=1+\sum_{i=1}^{s}P_{n-1,\tau_{2},i}(x).$

Thus, we prove the second formula.

∎

Here, we prove equality of $\displaystyle P_{n,\tau_{1}}(x)$ and
$\displaystyle P_{n,\tau_{2}}(x)$. Note that since $\displaystyle
P_{n,\tau_{1}}(x)=1+\sum_{s=1}^{n-1}P_{n,\tau_{1},s}(x)$ and $\displaystyle
P_{n,\tau_{2}}(x)=1+\sum_{s=1}^{n-1}P_{n,\tau_{2},s}(x)$, it is enough to show
that $\displaystyle P_{n,\tau_{1},s}(x)=P_{n,\tau_{2},s}(x)$ for
$\displaystyle 1\leq s\leq n-1$.

######  Lemma 25.

$\displaystyle P_{n,\tau_{1},s}(x)=P_{n,\tau_{2},s}(x)$ for $\displaystyle
1\leq s\leq n-1$.

###### Proof.

First of all, $\displaystyle P_{n,\tau_{1},t,t}(x)=P_{n,\tau_{2},t-1,t}(x)$ by
Lemma 23 and 24. As a result, $\displaystyle P_{n,\tau_{1},s,t}(x)$ and
$\displaystyle P_{n,\tau_{2},s,t}(x)$ have the same recursive formula for
$\displaystyle 1\leq t<s$. Then, we proceed to prove the lemma as follows.

$\displaystyle\displaystyle P_{n,\tau_{1},s}(x)$
$\displaystyle\displaystyle=\sum_{t=1}^{s}P_{n,\tau_{1},s,t}(x)+P_{n,\tau_{1},s,n}(x)$
$\displaystyle\displaystyle\text{By }(\ref{start_t1})$
$\displaystyle\displaystyle=\sum_{t=1}^{s-1}P_{n,\tau_{1},s,t}(x)+P_{n,\tau_{1},s,s}(x)+P_{n,\tau_{1},s,n}(x)$
$\displaystyle\displaystyle=\sum_{t=1}^{s-1}P_{n,\tau_{1},s,t}(x)+\left(1+\sum_{\ell=1}^{s-1}P_{n-1,\tau_{1},\ell}(x)\right)+P_{n-1,\tau_{1},s}(x)$
By Lemma 23
$\displaystyle\displaystyle=\sum_{t=1}^{s-1}P_{n,\tau_{1},s,t}(x)+1+\sum_{i=1}^{s}P_{n-1,\tau_{1},i}(x)$

Here, notice that $\displaystyle P_{n,\tau_{1},s,t}(x)=P_{n,\tau_{2},s,t}(x)$
as we discussed above, and $\displaystyle
P_{n-1,\tau_{1},i}(x)=P_{n-1,\tau_{2},i}(x)$ by inductive hypothesis. Thus, we
have

$\displaystyle\displaystyle P_{n,\tau_{1},s}(x)$
$\displaystyle\displaystyle=\sum_{t=1}^{s-1}P_{n,\tau_{2},s,t}(x)+1+\sum_{i=1}^{s}P_{n-1,\tau_{2},i}(x)$
$\displaystyle\displaystyle=\sum_{t=1}^{s-1}P_{n,\tau_{2},s,t}(x)+P_{n,\tau_{2},s,s+1}(x)$
By Lemma 24 $\displaystyle\displaystyle=P_{n,\tau_{2},s}(x)$
$\displaystyle\displaystyle\text{By }(\ref{start_t2})$

Therefore, $\displaystyle P_{n,\tau_{1},s}(x)=P_{n,\tau_{2},s}(x)$ for all
$\displaystyle 1\leq s\leq n-1$.

∎

As a consequence, $\displaystyle P_{n,\tau_{1}}(x)=P_{n,\tau_{2}}(x)$, and so
$\displaystyle\tau_{1}$ and $\displaystyle\tau_{2}$ are $\displaystyle
pmp$-Wilf equivalent. Hence, we prove Theorem 22.

We end this section here by introducing collections of patterns that are
likely to be equivalent to one another, but we do not yet have a proof.
According to numerical values generated, we guess that
$\displaystyle\underline{1}234,\underline{1}432$ and
$\displaystyle\underline{1}243$ are all equivalent to one another. Also,
$\displaystyle 13\underline{4}2$ and $\displaystyle\underline{2}413$ are
likely to be equivalent. Diagrams of mentioned positional marked patterns are
shown in Figure 8 and 9.

$\displaystyle\young(\hfil\hfil\hfil\times,\hfil\hfil\times\hfil,\hfil\times\hfil\hfil,\circ\hfil\hfil\hfil)$
$\displaystyle\underline{1}234$

$\displaystyle\young(\hfil\times\hfil\hfil,\hfil\hfil\times\hfil,\hfil\hfil\hfil\times,\circ\hfil\hfil\hfil)$
$\displaystyle\underline{1}432$

$\displaystyle\young(\hfil\hfil\times\hfil,\hfil\hfil\hfil\times,\hfil\times\hfil\hfil,\circ\hfil\hfil\hfil)$
$\displaystyle\underline{1}243$

Figure 8: Patterns $\displaystyle\underline{1}234,\underline{1}432$ and
$\displaystyle\underline{1}243$

$\displaystyle\young(\hfil\times\hfil\hfil,\hfil\hfil\hfil\times,\circ\hfil\hfil\hfil,\hfil\hfil\times\hfil)$
$\displaystyle\underline{2}413$

$\displaystyle\young(\hfil\hfil\circ\hfil,\hfil\times\hfil\hfil,\hfil\hfil\hfil\times,\times\hfil\hfil\hfil)$
$\displaystyle 13\underline{4}2$

Figure 9: Patterns $\displaystyle\underline{2}413$ and $\displaystyle
13\underline{4}2$

##  5 Patterns of arbitrary length

In this section, we restate and prove an equivalence of a collection
positional marked patterns of arbitrary length mentioned in Section 1.

See 3

We will prove that $\displaystyle P_{1}$ and $\displaystyle P_{2}$ are
$\displaystyle pmp$-Wilf equivalent. The equivalence of $\displaystyle P_{1}$
and $\displaystyle P_{3}$ follows from the fact that $\displaystyle P_{1}$ and
$\displaystyle P_{2}$ are equivalent. Here, we apply the technique introduced
in [1] to prove the equivalence of $\displaystyle P_{1}$ and $\displaystyle
P_{2}$. First, we need to give several definitions. Let
$\displaystyle\tau=red(p_{1}p_{2}\ldots p_{\ell-2})$.

######  Definition 26.

Given $\displaystyle\pi\in S_{n}$. Consider the diagram of $\displaystyle\pi$.
For each cell $\displaystyle(i,j)$ in the diagram of $\displaystyle\pi$, the
cell is dominant if there is an occurrence of $\displaystyle\tau$ in the
diagram of $\displaystyle\pi$ when only considering row $\displaystyle
i+1,i+2,\ldots,n$ and columns $\displaystyle j+1,j+2,\ldots,n$. A cell is non-
dominant if it is not dominant.

It is clear that given any dominant cell, every cell to the left and below the
dominant cell is also dominant. Thus, the collection of dominant cells form a
Ferrers board.

Let $\displaystyle ND(\pi)=\left\\{(i,j)\in[n]\times[n]\hskip 5.69046pt|\hskip
5.69046pt\text{cell }(i,j)\text{ is non-dominant and contains
}\times\right\\}$. Note that, if a cell is dominant, then one could find an
occurrence of $\displaystyle\tau$ above and to the right of the cell such that
all $\displaystyle\times$ involved are in non-dominant cell. If not, then
every occurrence of $\displaystyle\tau$ above and to the right of the cell
$\displaystyle(i,j)$ contains $\displaystyle\times$ in a dominant cell. Pick a
copy $\displaystyle T_{1}$ of $\displaystyle\tau$ in which a dominant cell
$\displaystyle(i^{\prime},j^{\prime})$ containing $\displaystyle\times$ is the
rightmost among all dominant cells containing $\displaystyle\times$ in all
copies of $\displaystyle\tau$ above and to the right of $\displaystyle(i,j)$.
Since cell $\displaystyle(i^{\prime},j^{\prime})$ is also dominant, one can
find a copy $\displaystyle T_{2}$ of $\displaystyle\tau$ above and to the
right of $\displaystyle(i^{\prime},j^{\prime})$, which is also above and to
the right of cell $\displaystyle(i,j)$. Thus, this copy will also contain a
dominant cell containing $\displaystyle\times$, contradicting to the fact that
the $\displaystyle T_{1}$ contains the rightmost dominant cell.

Thus, if $\displaystyle ND(\pi)$ is known, one can recover the set of dominant
cells in the diagram of $\displaystyle\pi$ completely. Given any
$\displaystyle Q\subseteq[n]\times[n]$, let $\displaystyle
S^{Q}_{n}=\left\\{\pi\in S_{n}|ND(\pi)=Q\right\\}$. We shall prove that

$\displaystyle\sum_{\pi\in S^{Q}_{n}}x^{pmp_{P_{1}}(\pi)}=\sum_{\pi\in
S^{Q}_{n}}x^{pmp_{P_{2}}(\pi)}.$

Here, we analyse the set $\displaystyle S_{n}^{Q}$. First, we only need to
consider those $\displaystyle Q$ such that $\displaystyle
S_{n}^{Q}\neq\emptyset$. Given any such $\displaystyle Q$, we can obtain an
element in $\displaystyle S_{n}^{Q}$ by filling $\displaystyle\times$ in the
dominant part of the diagram until every row and column contains precisely one
$\displaystyle\times$. This gives all elements in $\displaystyle S_{n}^{Q}$
since filling $\displaystyle\times$ in the dominant part does not alter
whether a cell is dominant or non-dominant.

To fill $\displaystyle\times$ in dominant cells, we start with all dominant
cells and eliminate all rows and columns that already contain
$\displaystyle\times$ from the set $\displaystyle Q$. The remaining cells form
a Ferrers board. Let $\displaystyle\lambda(Q)$ denote the shape of the Ferrers
board obtained from the process above.

######  Definition 27.

Given any Ferrers board of shape
$\displaystyle\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{k})$ with
$\displaystyle\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{k}$, a filling
of $\displaystyle\lambda$ is an assignment of $\displaystyle\times$ in the
Ferrers board of shape $\displaystyle\lambda$ such that every row and columns
contain precisely one $\displaystyle\times$.

In order for $\displaystyle\lambda$ to have a filling, the number of rows of
$\displaystyle\lambda$ must be the same as the number of columns in
$\displaystyle\lambda$. More specifically, if
$\displaystyle\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{k})$,
$\displaystyle\lambda$ has a filling if and only if
$\displaystyle(k-i+1)\leq\lambda_{i}\leq k$ for all $\displaystyle k$. Let
$\displaystyle S_{\lambda}$ denote the set of fillings of
$\displaystyle\lambda$.

Given any $\displaystyle\pi\in S_{\lambda}$, and $\displaystyle p\in S_{k}$,
we say that $\displaystyle\pi$ contains $\displaystyle p$ if
$\displaystyle\pi$ contains a subdiagram of $\displaystyle p$. Note that, in
order for $\displaystyle\pi$ to contain $\displaystyle p$, the entire diagram
of $\displaystyle p$ has to present as a subdiagram of $\displaystyle\pi$
including cells not containing $\displaystyle\times$. For example, the filling
below contains $\displaystyle p=12$ but does not contain $\displaystyle q=21$.

(×, ×, ×, × )

Here, we define positional marked pattern on $\displaystyle S_{\lambda}$
similar to $\displaystyle S_{n}$. Given any $\displaystyle\pi\in S_{\lambda}$
and $\displaystyle p\in S_{k}^{*}$, we say that $\displaystyle\pi$ has a
$\displaystyle p$-match at position $\displaystyle t$ if when replacing
$\displaystyle\times$ in the $\displaystyle t$-th column of $\displaystyle\pi$
of by $\displaystyle\circ$, then it contains a subdiagram $\displaystyle p$.
For example, the diagram above has a $\displaystyle\underline{1}2$-match at
position 3 as shown below.

(×, ×,  ×,  ∘ )

Let $\displaystyle pmp_{p}(\pi)$ denote the number of positions $\displaystyle
t$ such that $\displaystyle\pi$ has a $\displaystyle p$-match at position
$\displaystyle t$. Here, we state a lemma which will be our main tool to prove
Theorem 3.

######  Lemma 28.

Given any $\displaystyle Q\subseteq[n]\times[n]$ such that $\displaystyle
S_{n}^{Q}\neq\emptyset$. Then

$\displaystyle\sum_{\pi\in S_{n}^{Q}}x^{pmp_{P_{1}}(\pi)}=\sum_{\pi\in
S_{\lambda}(Q)}x^{pmp_{1\underline{2}}(\pi)}$

and

$\displaystyle\sum_{\pi\in S_{n}^{Q}}x^{pmp_{P_{2}}(\pi)}=\sum_{\pi\in
S_{\lambda}(Q)}x^{pmp_{\underline{2}1}(\pi)}.$

###### Proof.

Note that there is a natural bijection
$\displaystyle\phi:S_{\lambda(Q)}\rightarrow S_{n}^{Q}$ which maps any filling
$\displaystyle\pi\in\lambda(Q)$ to a permutation with non-dominant part
corresponding to $\displaystyle Q$ and dominant part having the same filling
as $\displaystyle\pi$. We will show that $\displaystyle\pi$ has a
$\displaystyle 1\underline{2}$-match at a position if and only if
$\displaystyle\phi(\pi)$ has a $\displaystyle P_{1}$-match at the
corresponding position according to the map $\displaystyle\phi$

The converse is obvious. For the forward direction, suppose
$\displaystyle\pi\in S_{\lambda(Q)}$ has a $\displaystyle
1\underline{2}$-match at a certain position. Thus, the corresponding position
in $\displaystyle\phi(\pi)$ has a $\displaystyle 1\underline{2}$-match with
every cells involved are dominant. Thus, we can find a copy of
$\displaystyle\tau$ above and to the right of every cells involved in
$\displaystyle 1\underline{2}$-match. Therefore, the $\displaystyle
1\underline{2}$-match together with $\displaystyle\tau$ makes
$\displaystyle\phi(\pi)$ $\displaystyle P_{1}$-match at the position
corresponding to the $\displaystyle 1\underline{2}$-match in
$\displaystyle\pi$.

Therefore, $\displaystyle\phi$ is a bijection between $\displaystyle
S_{\lambda(Q)}$ and $\displaystyle S_{n}^{Q}$ such that $\displaystyle
pmp_{1\underline{2}}(\pi)=pmp_{P_{1}}(\phi(\pi))$. Thus, it proves the first
equality of the lemma. The second equation can be proved with the exact same
reasoning. ∎

As an example, let $\displaystyle n=9$, $\displaystyle\tau=12$, (so
$\displaystyle P_{1}=1\underline{2}34$ and $\displaystyle
P_{2}=\underline{2}134$), and $\displaystyle Q$ is as below

( ×, × , , × , , , × , , )

With $\displaystyle Q$, we recover dominant and non-dominant cells. We fill
$\displaystyle\bullet$ in non-dominant cells.

(∙∙∙∙∙∙∙∙×,∙×∙∙∙∙∙∙∙, ∙∙∙∙∙∙∙∙, ∙∙∙×∙∙∙∙, ∙∙∙∙∙, ∙∙∙∙∙, ∙∙∙×∙, ∙∙, ∙∙)

We want to fill $\displaystyle\times$ into the diagram so that every row and
column contains precisely one $\displaystyle\times$, thus we eliminate all
empty cells that are in same rows or columns with cell containing
$\displaystyle\times$. We fill $\displaystyle\bullet$ in such cells.

(∙∙∙∙∙∙∙∙×,∙×∙∙∙∙∙∙∙, ∙∙∙∙∙∙∙∙,∙∙∙∙×∙∙∙∙, ∙ ∙∙∙∙∙, ∙ ∙∙∙∙∙,∙∙∙∙∙∙∙×∙, ∙ ∙ ∙∙,
∙ ∙ ∙∙)

Thus, the remaining cells form a Ferrers board
$\displaystyle\lambda(Q)=(5,5,3,3,1)$, as shown below:

( , , , , )

Then, to define the one-to-one corresponding between $\displaystyle S_{9}^{Q}$
and $\displaystyle S_{\lambda(Q)}$, we fill cells in $\displaystyle\lambda(Q)$
the same way we fill available cells in a diagram $\displaystyle Q$. For
example, below is an example of the correspondence:

$\displaystyle\pi=$ (×, ×, × , ×, × ) $\displaystyle\longleftrightarrow$
$\displaystyle\phi(\pi)=$ (∙∙∙∙∙∙∙∙×,∙×∙∙∙∙∙∙∙, ×∙∙∙∙∙∙∙∙,∙∙∙∙×∙∙∙∙, ∙
×∙∙∙∙∙, ∙ × ∙∙∙∙∙,∙∙∙∙∙∙∙×∙, ∙ ∙  ×∙∙, ∙ ∙ × ∙∙)

With this map, $\displaystyle 1\underline{2}$-matching at position 3 of
$\displaystyle\pi$ corresponds to $\displaystyle 1\underline{2}34$-matching at
position 4 of $\displaystyle\phi(\pi)$.

$\displaystyle\pi=$ (×,  ∘,  × , ×, × ) $\displaystyle\longleftrightarrow$
$\displaystyle\phi(\pi)=$ (∙∙∙∙∙∙∙∙ ×,∙×∙∙∙∙∙∙∙,×∙∙∙∙∙∙∙∙,∙∙∙∙ ×∙∙∙∙, ∙
∘∙∙∙∙∙, ∙ × ∙∙∙∙∙,∙∙∙∙∙∙∙×∙, ∙ ∙ ×∙∙, ∙ ∙× ∙∙)

Here, in order to prove theorem 3, we only need to prove that, given any
Ferrers board $\displaystyle\lambda$, $\displaystyle\sum_{\pi\in
S_{\lambda}}x^{pmp_{1\underline{2}}(\pi)}=\sum_{\pi\in
S_{\lambda}}x^{pmp_{\underline{2}1}(\pi)}$. In fact, we find a formula for
both polynomials.

######  Lemma 29.

Let $\displaystyle\lambda=(\lambda_{1},\lambda_{2},\ldots,\lambda_{k})$ be a
Ferrers board such that $\displaystyle(k-i+1)\leq\lambda_{i}\leq k$ for all
$\displaystyle 1\leq i\leq k$. Then,

$\displaystyle\sum_{\pi\in
S_{\lambda}}x^{pmp_{1\underline{2}}(\pi)}=\sum_{\pi\in
S_{\lambda}}x^{pmp_{\underline{2}1}(\pi)}=\prod_{i=1}^{k}(1+(\lambda_{i}-(k-i+1))x.)$

###### Proof.

Given any $\displaystyle\lambda$ satisfying
$\displaystyle(k-i+1)\leq\lambda_{i}\leq k$ for all $\displaystyle 1\leq i\leq
k$, let $\displaystyle\overline{\lambda}$ be a Ferrers board obtained from
$\displaystyle\lambda$ by removing the top most row and left most column. That
is
$\displaystyle\overline{\lambda}=(\lambda_{1}-1,\lambda_{2}-1,\ldots,\lambda_{k-1}-1)$.
Then, to prove the formula, we only need to prove that

$\displaystyle\sum_{\pi\in
S_{\lambda}}x^{pmp_{1\underline{2}}(\pi)}=(1+(\lambda_{k}-1)x)\sum_{\pi\in
S_{\overline{\lambda}}}x^{pmp_{1\underline{2}}(\pi)}$

To prove the equation above, we consider the topmost row in
$\displaystyle\lambda$. The filling has a $\displaystyle 1\underline{2}$-match
at the position of $\displaystyle\times$ in the topmost row if and only if
$\displaystyle\times$ is not in the rightmost possible cell. So, there are
$\displaystyle\lambda_{k}-1$ positions to fill $\displaystyle\times$ so that
it has a $\displaystyle 1\underline{2}$-match, and 1 position otherwise. Once
the top row is filled, we consider filling the rest of $\displaystyle\lambda$
by remove the top row and the column containing $\displaystyle\times$. The
remaining cells form a shape $\displaystyle\overline{\lambda}$. Thus, the
equation above is proved.

For the pattern $\displaystyle\underline{2}1$, a similar reasoning can also be
applied. The filling of $\displaystyle\lambda$ has a
$\displaystyle\underline{2}1$-match at the position of $\displaystyle\times$
in the topmost row if and only if $\displaystyle\times$ is not in the leftmost
possible cell. Hence, we have

$\displaystyle\sum_{\pi\in
S_{\lambda}}x^{pmp_{\underline{2}1}(\pi)}=(1+(\lambda_{k}-1)x)\sum_{\pi\in
S_{\overline{\lambda}}}x^{pmp_{\underline{2}1}(\pi)}$

Therefore, we proved the lemma.

∎

Here, we prove the main theorem:

###### Proof.

(of Theorem 3) Note that $\displaystyle S_{n}$ is a disjoint union of
$\displaystyle S_{n}^{Q}$ for all $\displaystyle Q$ such that $\displaystyle
S_{n}^{Q}\neq\emptyset$. So, we have

$\displaystyle\displaystyle P_{n,P_{1}}(x)$
$\displaystyle\displaystyle=\sum_{\sigma\in S_{n}}x^{pmp_{P_{1}}(\sigma)}$
$\displaystyle\displaystyle=\sum_{Q}\sum_{\sigma\in
S^{Q}_{n}}x^{pmp_{P_{1}}(\sigma)}$
$\displaystyle\displaystyle=\sum_{Q}\sum_{\sigma\in
S_{\lambda(Q)}}x^{pmp_{1\underline{2}}(\sigma)}$ By Lemma 28
$\displaystyle\displaystyle=\sum_{Q}\sum_{\sigma\in
S_{\lambda(Q)}}x^{pmp_{\underline{2}1}(\sigma)}$ By Lemma 29
$\displaystyle\displaystyle=\sum_{Q}\sum_{\sigma\in
S^{Q}_{n}}x^{pmp_{P_{2}}(\sigma)}$ By Lemma 28
$\displaystyle\displaystyle=\sum_{\sigma\in
S_{n}}x^{pmp_{P_{2}}(\sigma)}=P_{n,P_{2}}(x)$

Thus, $\displaystyle P_{1}$ and $\displaystyle P_{2}$ are $\displaystyle
pmp$-Wilf equivalent.

To see that $\displaystyle P_{1}=1\underline{2}p_{1}\ldots p_{n-2}$ and
$\displaystyle P_{3}=2\underline{1}p_{1}\ldots p_{n-2}$, Let $\displaystyle
P_{1}^{inv}$ and $\displaystyle P_{3}^{inv}$ be positional marked patterns
obtained from $\displaystyle P_{1}$ and $\displaystyle P_{3}$ by reflecting
diagram of $\displaystyle P_{1}$ and $\displaystyle P_{3}$ along the diagonal
$\displaystyle y=x$ respectively. By Lemma 7, $\displaystyle P_{1}$ and
$\displaystyle P_{1}^{inv}$ are $\displaystyle pmp$-Wilf equivalent, and so
are $\displaystyle P_{3}$ and $\displaystyle P_{3}^{inv}$. However,
$\displaystyle P_{1}^{inv}$ has the form $\displaystyle
1\underline{2}q_{1}\ldots q_{n-2}$ and $\displaystyle P_{3}^{inv}$ has the
form of $\displaystyle\underline{2}1q_{1}\ldots q_{n-2}$, thus $\displaystyle
P_{1}^{inv}$ and $\displaystyle P_{3}^{inv}$ are $\displaystyle pmp$-Wilf
equivalent by the main argument above. Therefore, $\displaystyle P_{1}$ and
$\displaystyle P_{3}$ are $\displaystyle pmp$-Wilf equivalent.

∎

Remark Alternately, we can prove that $\displaystyle P_{3}$ and $\displaystyle
P_{2}$ are $\displaystyle pmp$-Wilf equivalent by considering the rightmost
column of any Ferrers board $\displaystyle\lambda$.

To end this section, we state possible nontrivial $\displaystyle pmp$-Wilf
equivalence classes of size 4. According to numerical data, we conjecture that
$\displaystyle\underline{1}234$, $\displaystyle\underline{1}243$ and
$\displaystyle\underline{1}432$ are equivalent. Also, $\displaystyle
134\underline{2}$ and $\displaystyle\underline{2}413$ are equivalent.

$\displaystyle\young(\hfil\hfil\hfil\times,\hfil\hfil\times\hfil,\hfil\times\hfil\hfil,\circ\hfil\hfil\hfil)$
$\displaystyle\underline{1}234$
$\displaystyle\young(\hfil\hfil\times\hfil,\hfil\hfil\hfil\times,\hfil\times\hfil\hfil,\circ\hfil\hfil\hfil)$
$\displaystyle\underline{1}243$
$\displaystyle\young(\hfil\times\hfil\hfil,\hfil\hfil\times\hfil,\hfil\hfil\hfil\times,\circ\hfil\hfil\hfil)$
$\displaystyle\underline{1}432$
$\displaystyle\young(\hfil\hfil\times\hfil,\hfil\times\hfil\hfil,\hfil\hfil\hfil\circ,\times\hfil\hfil\hfil)$
$\displaystyle 134\underline{2}$
$\displaystyle\young(\hfil\times\hfil\hfil,\hfil\hfil\hfil\times,\circ\hfil\hfil\hfil,\hfil\hfil\times\hfil)$
$\displaystyle\underline{2}413$

##  6 Future research

One way to generalize positional marked pattern is to consider multiple
patterns. Given a collection of positional marked patterns
$\displaystyle\Gamma$ and $\displaystyle\sigma\in S_{n}$, we say that
$\displaystyle\sigma$ has a $\displaystyle\Gamma$-match at position
$\displaystyle l$ if $\displaystyle\sigma$ has a $\displaystyle\tau$-match at
position $\displaystyle l$ for some $\displaystyle\tau\in\Gamma$. Given
$\displaystyle\sigma\in S_{n}$, let $\displaystyle pmp_{\Gamma}(\sigma)$
denote the number of positions $\displaystyle l$ such that
$\displaystyle\sigma$ has a $\displaystyle\Gamma$-match at position
$\displaystyle l$. Let $\displaystyle P_{n,\Gamma}(x)=\sum_{\sigma\in
S_{n}}x^{pmp_{\Gamma}(\sigma)}$. Given two collections of positional marked
patterns $\displaystyle\Gamma_{1}$ and $\displaystyle\Gamma_{2}$, they are
Wilf-equivalent if $\displaystyle P_{n,\Gamma_{1}}(x)=P_{n,\Gamma_{2}}(x)$.
This is a nice generalization to positional marked patterns since the constant
term of $\displaystyle P_{n,\Gamma}(x)$ enumerates the number of
$\displaystyle\sigma\in S_{n}$ avoiding every patterns in
$\displaystyle\Gamma$, which replicates what $\displaystyle P_{n,\tau}(x)$
provides in single pattern cases. Here, we stated, without proof, a result on
collection of positional marked patterns similar to Theorem 3. The proof also
follows the same logic as in the proof of Theorem 3.

######  Theorem 30.

Let $\displaystyle\tau_{1},\tau_{2},\ldots,\tau_{l}$ be rearrangements of
$\displaystyle\left\\{3,4,\ldots,k\right\\}$, so that $\displaystyle
1\underline{2}\tau_{i}$ and $\displaystyle\underline{2}1\tau_{i}$ are elements
of $\displaystyle S_{k}^{*}$. Let
$\displaystyle\Gamma_{1}=\left\\{1\underline{2}\tau_{i}|1\leq i\leq
l\right\\}$ and $\displaystyle\Gamma_{2}=\left\\{\underline{2}1\tau_{i}|1\leq
i\leq l\right\\}$. Then $\displaystyle\Gamma_{1}$ and
$\displaystyle\Gamma_{2}$ are Wilf-equivalent.

Moreover, define $\displaystyle\Gamma$-matching would let us realize
positional marked pattern as a refinement of marked mesh pattern defined by
Remmel and Kitaev [4]. Given $\displaystyle a,b,c,d\in\mathbb{Z}_{\geq 0}$,
and given $\displaystyle\sigma\in S_{n}$, we say $\displaystyle\sigma$ matches
$\displaystyle MMP(a,b,c,d)$ at position $\displaystyle l$ if in the diagram
of $\displaystyle\sigma$ relative to the coordinate system which has
$\displaystyle\times$ in the $\displaystyle l$-th column as its origin there
are at least $\displaystyle a$ $\displaystyle\times$’s in quadrant I, at least
$\displaystyle b$ $\displaystyle\times$’s in quadrant II, at least
$\displaystyle c$ $\displaystyle\times$’s in quadrant III, and at least
$\displaystyle d$ $\displaystyle\times$’s in quadrant IV. As an example,
$\displaystyle\sigma=25417683$ matches $\displaystyle MMP(3,0,1,1)$ at
position 3:

( × , × , × , × , × , ×,× , × )IIIIIIIV

It is easy to see that, for any $\displaystyle a,b,c,d$, $\displaystyle
MMP(a,b,c,d)$ is equivalent to $\displaystyle\Gamma$-matching for some
collection of positional marked patterns $\displaystyle\Gamma$. For example,
to match $\displaystyle MMP(2,0,0,0)$ at some position, it is the same as to
match $\displaystyle\Gamma=\left\\{\underline{1}23,\underline{1}32\right\\}$
at the same position. Therefore, as we introduce multiple positional marked
patterns, one can realize positional marked patterns as a refinement of marked
mesh pattern.

## References

  * [1] E. Babson and J. West.  The permutations 123p4 . . . pm and 321p4 . . . pm are wilf-equivalent.  Graphs and Combinatorics, 16:173:373–380, 2000.
  * [2] P. Brändén and A. Claesson.  Mesh patterns and the expansion of permutation statistics as sums of permutation patterns.  Electronic J. Combin., 18:2, 2011.
  * [3] M. Davis.  Quadrant marked mesh patterns and the $\displaystyle r$-stirling numbers.  Journal of Integer Sequences, 18, 2015.
  * [4] S. Kitaev and J. Remmel.  Quadrant marked mesh patterns.  Journal of Integer Sequence, 15 issue 4(12.4.7):29, 2012.
  * [5] S. Kitaev and J. Remmel.  Quadrant marked mesh patterns in alternating permutations.  Sem. Lothar. Combin, B68a:20, 2012.
  * [6] S. Kitaev and J. Remmel.  Quadrant marked mesh patterns in alternating permutations ii.  Journal of Combinatorics, 4 no 1:31–65, 2013.
  * [7] S. Kitaev, J. Remmel, and M. Tiefenbruck.  Marked mesh patterns in 132-avoiding permutations.  Pure Mathematics and Applications, 23:219–256, 2012.
  * [8] S. Kitaev, J. Remmel, and M. Tiefenbruck.  Marked mesh patterns in 132-avoiding permutations ii.  Integers: Electronic Journal of Combinatorial Number Theory, A16:33, 2015.
  * [9] D. Qiu and J. Remmel.  Marked mesh patterns in 123-avoiding permutations.  ArXiv.org, https://arxiv.org/pdf/1705.00164.pdf, 2017.
  * [10] Henning A. Úlfarsson.  A unification of permutation patterns related to schubert varieties.  DMTCS proc., AN:1057–1068, 2010.