On a refinement of Wilf-equivalence for permutations

Huiyun Ge, Sherry H.F. Yan111 Corresponding author. , Yaqiu Zhang
Department of Mathematics, Zhejiang Normal University, Jinhua 321004, P.R.
China
<EMAIL_ADDRESS>

Abstract. Recently, Dokos et al. conjectured that for all $k,m\geq 1$, the
patterns $12\ldots k(k+m+1)\ldots(k+2)(k+1)$ and
$(m+1)(m+2)\ldots(k+m+1)m\ldots 21$ are $maj$-Wilf-equivalent. In this paper,
we confirm this conjecture for all $k\geq 1$ and $m=1$. In fact, we construct
a descent set preserving bijection between $12\ldots k(k-1)$-avoiding
permutations and $23\ldots k1$-avoiding permutations for all $k\geq 3$. As a
corollary, our bijection enables us to settle a conjecture of Gowravaram and
Jagadeesan concerning the Wilf-equivalence for permutations with given descent
sets.

Key words: $maj$-Wilf-equivalent, pattern avoiding permutation, bijection.

AMS Mathematical Subject Classifications: 05A05, 05C30.

##  1 Introduction

Denote by $\mathcal{S}_{n}$ the set of all permutations on $[n]$. Given a
permutation $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}\in\mathcal{S}_{n}$ and a
permutation $\tau=\tau_{1}\tau_{2}\ldots\tau_{k}\in\mathcal{S}_{k}$, we say
that $\pi$ contains the pattern $\tau$ if there exists a subsequence
$\pi_{i_{1}}\pi_{i_{2}}\ldots\pi_{i_{k}}$ of $\pi$ that is order-isomorphic to
$\tau$. Otherwise, $\pi$ is said to avoid  the pattern $\tau$ or be
$\tau$-avoiding. Denote by $\mathcal{S}_{n}(\tau)$ the set of all
$\tau$-avoiding permutations in $\mathcal{S}_{n}$. Pattern avoiding
permutations have been extensively studied over last decade. For a thorough
summary of the current status of research, see Bóna’s book [5] and Kitaev’s
book [12].

If two patterns $\sigma,\tau\in\mathcal{S}_{m}$ are said to be Wilf-equivalent
if and only if $|\mathcal{S}_{n}(\sigma)|=|\mathcal{S}_{n}(\tau)|$. A
permutation statistic is defined to be a function
$s:\mathcal{S}_{n}\rightarrow T$, where $T$ is any fixed set. The most studied
statistics include the inversion number and the major index. Let
$\pi=\pi_{1}\pi_{2}\ldots\pi_{n}\in\mathcal{S}_{n}$. The set of inversions of
$\pi$ is

$\mathcal{I}(\pi)=\\{(i,j)|i<j\,\mbox{and}\,\pi_{i}>\pi_{j}\\}.$

The inversion number of $\pi$, denoted by $inv(\pi)$, is the cardinality of
$\mathcal{I}(\pi)$. The decent set of $\pi$ is

$\mathcal{D}(\pi)=\\{i|\pi_{i}>\pi_{i+1}\\}.$

The ascent set of $\pi$ is

$\mathcal{A}(\pi)=\\{i|\pi_{i}<\pi_{i+1}\\}.$

The major index of $\pi$, denoted by $maj(\pi)$, is given by
$maj(\pi)=\sum_{i\in\mathcal{D}(\pi)}i$.

Given a permutation statistic $s$, we say that $\sigma$ and $\tau$ are
$s$-wilf-equivalent if there exists a bijection
$\Theta:\mathcal{S}_{n}(\sigma)\rightarrow\mathcal{S}_{n}(\tau)$ such that
$s(\pi)=s(\Theta(\pi))$ for all $\pi\in\mathcal{S}_{n}(\sigma)$. In other
words, the statistic $s$ is equally distributed on the sets
$\mathcal{S}_{n}(\sigma)$ and $\mathcal{S}_{n}(\tau)$. This refinement of
Wilf-equivalence for patterns of length $3$ has been extensively studied, see
[2, 3, 7, 8, 10, 14]. However, little is known about permutation statistics
and patterns of length $4$ or greater. Recently, Dokos et al. [9] posed the
following two conjectures on the $maj$-Wilf-equivalence for patterns of length
4 or greater.

###### Conjecture 1.1

( [9], Conjecture 2.6) For all $k,m\geq 1$, the patterns $12\ldots
k(k+m+1)\ldots(k+2)(k+1)$ and $(m+1)(m+2)\ldots(k+m+1)m\ldots 21$ are
$maj$-Wilf-equivalent.

###### Conjecture 1.2

( [9], Conjecture 2.8) The major index is equally distributed on the sets
$\mathcal{S}_{n}(2413)$, $\mathcal{S}_{n}(1423)$ and $\mathcal{S}_{n}(2314)$

Recently, Bloom [4] confirmed Conjecture 1.2 by providing descent set
preserving bijections between the set $\mathcal{S}_{n}(2413)$ and the set
$\mathcal{S}_{n}(1423)$, and between the set $\mathcal{S}_{n}(2413)$ and the
set $\mathcal{S}_{n}(2314)$. In their paper [9], Dokos et al. showed that
Conjecture 1.1 is true for $m=k=1$. The main purpose of this paper is to
confirm Conjecture 1.1 for all $k\geq 1$ and $m=1$. Actually, we obtain the
following stronger result.

###### Theorem 1.3

For $k\geq 3$, there exists a descent set preserving bijection between the set
$\mathcal{S}_{n}(12\ldots k(k-1))$ and the set $\mathcal{S}_{n}(23\ldots k1)$.

Denote by $J_{k}=12\ldots k$, $F_{k}=23\ldots k1$ and $G_{k}=12\ldots k(k-1)$,
respectively. Give a permutation $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$, suppose
that $\mathcal{D}(\pi)=\\{i_{1},i_{2},\ldots,i_{s}\\}$. Then we call the
subsequence $\pi_{1}\pi_{2}\ldots\pi_{i_{1}}$ the first block of $\pi$, the
subsequence $\pi_{i_{1}+1}\pi_{i_{1}+2}\ldots\pi_{i_{2}}$ the second block of
$\pi$, and so on. We say that a permutation $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$
contains an occurrence of $H_{k}$ if there exists indices
$i_{1}<i_{2}<\ldots<i_{k}$ such that the subsequence
$\pi_{i_{1}}\pi_{i_{2}}\ldots\pi_{i_{k}}$ is isomorphic to $J_{k}$ and entries
$\pi_{i_{k-1}}$ and $\pi_{i_{k}}$ belong to two different blocks. That is,
there exists a $j\in\mathcal{D}(\pi)$ with $i_{k-1}\leq j<i_{k}$. Otherwise,
we say that $\pi$ avoids $H_{k}$. For example, the subsequence $13579$ of the
permutation $\pi=13576894(10)2(11)\in\mathcal{S}_{11}$ is an occurrence of
$H_{5}$, while the subsequence $13569$ is not an occurrence of $H_{5}$. We say
that a permutation $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}$ contains an occurrence of
$Q_{k}$ if there exists indices $i_{1}<i_{2}<\ldots<i_{k}$ such that the
subsequence $\pi_{i_{1}}\pi_{i_{2}}\ldots\pi_{i_{k}}$ is isomorphic to $G_{k}$
and $\pi_{i_{k-1}}<\pi_{i_{k-1}+1}<\ldots<\pi_{i_{k}-1}>\pi_{i_{k}}$.
Otherwise, we say that $\pi$ avoids $Q_{k}$. For example, the subsequence
$13586$ of the permutation $\pi=1358(10)67492(11)\in\mathcal{S}_{11}$ is an
occurrence of $Q_{5}$, while the subsequence $13587$ is not an occurrence of
$Q_{5}$.

In order to prove Theorem 1.3, we obtain the following two theorems.

###### Theorem 1.4

For $k\geq 3$, there is a bijection $f$ between the set
$\mathcal{S}_{n}(G_{k})$ and the set $\mathcal{S}_{n}(H_{k},Q_{k})$ such that
for any $\pi\in\mathcal{S}_{n}(G_{k})$, we have
$\mathcal{D}(\pi)=\mathcal{D}(f(\pi))$.

###### Theorem 1.5

For $k\geq 3$, there is a bijection $\Phi$ between the set
$\mathcal{S}_{n}(F_{k})$ and the set $\mathcal{S}_{n}(H_{k},Q_{k})$ such that
for any $\pi\in\mathcal{S}_{n}(F_{k})$, we have
$\mathcal{D}(\pi)=\mathcal{D}(\Phi(\pi))$.

Combining Theorems 1.4 and 1.5, we are led to Theorem 1.3.

Given a positive integer $t$, Let $D^{t}_{n}=\\{i|1\leq i\leq
n-1\,\mbox{and}\,i\equiv 0\,\mbox{mod}\,t\\}$. Denote by
$\mathcal{S}^{t}_{n}(12\ldots k(k-1))$ (resp. $\mathcal{S}^{t}_{n}(23\ldots
k1)$) the set of permutations $\pi\in\mathcal{S}_{n}(12\ldots k(k-1))$ (resp.
$\pi\in\mathcal{S}^{t}_{n}(23\ldots k1)$) with $\mathcal{D}(\pi)=D^{t}_{n}$.
From Theorem 1.3, we obtain the following result as conjectured by Gowravaram
and Jagadeesan [11].

###### Corollary 1.6

([11], Conjecture 6.2) For $t\geq 1$ and $k\geq 3$, we have
$|\mathcal{S}^{t}_{n}(12\ldots k(k-1))|=|\mathcal{S}^{t}_{n}(23\ldots k1)|$.

##  2 Proof of Theorem 1.4

We begin with some definitions and notations. An entry of a permutation is
said to have rank $k$ if the length of the longest increasing subsequence that
ends in that entry is $k$. We now construct a map $f$ from the set
$\mathcal{S}_{n}(G_{k})$ to the set $\mathcal{S}_{n}(H_{k},Q_{k})$. The map
$f$ is a slight modification of a classic bijection, which is given by West
[15] to prove the equality $|\mathcal{S}_{n}(J_{k})|=|\mathcal{S}_{n}(G_{k})|$
for all $k\geq 3$. Recently, Bona [6] proved that West’s bijection also
induces a bijection between $12\ldots k$-avoiding alternating permutations and
$12\ldots k(k-1)$-avoiding alternating permutations, thereby proving
generalized versions of some conjectures of Lewis [13].

Let $\pi\in\mathcal{S}_{n}(G_{k})$. In order to obtain $f(\pi)$, we leave all
entries of $\pi$ that are of rank $k-2$ or less in their place and rearrange
the entries of rank $k-1$ or higher. Let $B_{1},B_{2},\ldots,B_{s}$ be the
blocks of $\pi$ that are listed from left to right. Let $P_{i}$ be the set of
positions of $\pi$ in which, an entry that has rank $k-1$ or higher and
belongs to the block $B_{i}$, is located, and let $R$ be the set of entries of
$\pi$ that are of rank $k-1$ or higher. Now we fill the positions of
$P_{i}^{\prime}s$ as follows.

  * Step 1.

Choose $|P_{1}|$ largest entries from $R$ that are larger than the closest
entry of rank $k-2$ on the left of the positions of $P_{1}$, and fill the
positions of $P_{1}$ with the selected entries from left to right in
increasing order.

  * Step 2.

Choose $|P_{2}|$ largest entries from $R$ that have not been placed yet and
are larger than the closest entry of rank $k-2$ on the left of the positions
of $P_{2}$. Fill the positions of $P_{2}$ with the selected entries from left
to right in increasing order.

  * Step 3.

Fill the positions of $P_{3}$, $P_{4}$, $\ldots$, $P_{s}$ as in Step 2.

Let $f(\pi)$ be the obtained permutation.

###### Example 2.1

Consider $\pi=13576894(10)2(11)\in\mathcal{S}_{11}(G_{6})$. Then we have
$B_{1}=1357$, $B_{2}=689$, $B_{3}=4(10)$ and $B_{4}=2(11)$. Moreover, we have
$P_{1}=\emptyset$, $P_{2}=\\{6,7\\}$, $P_{3}=\\{9\\}$, $P_{4}=\\{11\\}$ and
$R=\\{8,9,10,11\\}$. According to the definition of $f$, we have
$f(\pi)=13576(10)(11)4928$.

Since the existence of $\pi$ shows that there is at least one way to assign
the entries of $R$ to the positions of $P_{i}$, the definition of $f$ always
enables us to create $f(\pi)$.

Notice that if entry $\pi_{i}$ of $\pi$ has rank $k-2$ or less, then $\pi_{i}$
do not move in the above procedure, and the rank of $\pi_{i}$ do not change.
If entry $\pi_{i}$ of $\pi$ has rank $k-1$ or higher, then $\pi_{i}$ may have
moved and the rank of $\pi_{i}$ in $f(\pi)$ is $k-1$ or higher. We claim that
if $\pi_{i-1}>\pi_{i}$, then the rank of $\pi_{i}$ is $k-2$ or less. If not,
the longest increasing subsequence that ends in $\pi_{i}$ combining with
$\pi_{i-1}$ would form a $G_{k}$ in $\pi$. This contradicts the fact that
$\pi$ avoids $G_{k}$.

Now we proceed to show that $\mathcal{D}(\pi)=\mathcal{D}(f(\pi))$. Let
$f(\pi)=\sigma_{1}\sigma_{2}\ldots\sigma_{n}$. If $\pi_{i-1}>\pi_{i}$, then
the rank of $\pi_{i}$ is $k-2$ or less and do not move. This implies that
$\pi_{i}=\sigma_{i}$ and $\sigma_{i}$ has rank $k-2$ or less. If $\pi_{i-1}$
is of rank $k-2$ or less, then we have $\sigma_{i-1}=\pi_{i-1}$. In this case,
we have $\sigma_{i-1}=\pi_{i-1}>\pi_{i}=\sigma_{i}$. If $\pi_{i-1}$ is of rank
$k-1$ or higher, then $\sigma_{i-1}$ is of rank $k-1$ or higher. Since
$\sigma_{i}$ is of rank $k-2$ or less, we have $\sigma_{i-1}>\sigma_{i}$.
Thus, we have concluded that if $\pi_{i-1}>\pi_{i}$, then
$\sigma_{i-1}>\sigma_{i}$.

Next we aim to show that if $\pi_{i-1}<\pi_{i}$, then we have
$\sigma_{i-1}<\sigma_{i}$. We have three cases. If $\pi_{i}$ is of rank $k-2$
or less in $\pi$, then then the rank of $\pi_{i-1}$ is also $k-2$ or less. In
this case, we have $\sigma_{i-1}=\pi_{i-1}<\pi_{i}=\sigma_{i}$. If both
$\pi_{i}$ and $\pi_{i-1}$ are of rank $k-1$ or higher, then according to the
definition of $f$, we have $\sigma_{i-1}<\sigma_{i}$ . If $\pi_{i}$ has rank
$k-1$ or higher and $\pi_{i-1}$ is of rank $k-2$ or less, then the rank of
$\sigma_{i-1}$ is $k-2$ or less and $\sigma_{i}$ is of rank $k-1$ or higher.
This implies that $\sigma_{i-1}<\sigma_{i}$. Thus, we have concluded that if
$\pi_{i-1}<\pi_{i}$, then $\sigma_{i-1}<\sigma_{i}$. Therefore, we have
$\mathcal{D}(\pi)=\mathcal{D}(f(\pi))$.

Notice that $f(\pi)$ avoids $H_{k}$ since the existence of such a pattern in
$f(\pi)$ would mean that the last two entries of that pattern were not placed
according to the rule specified above. Moreover, we have that $f(\pi)$ avoids
$Q_{k}$. If not, suppose that
$\sigma_{i_{1}}\sigma_{i_{2}}\ldots\sigma_{i_{k}}$ is such a $Q_{k}$. Then we
have $\sigma_{i_{k}-1}>\sigma_{i_{k}}$ and $\sigma_{i_{k}}$ has rank $k-1$ or
higher. Since $\mathcal{D}(\pi)=\mathcal{D}(f(\pi))$, we have
$\pi_{i_{k}-1}>\pi_{i_{k}}$. Recall that if $\pi_{i-1}>\pi_{i}$, then both
$\pi_{i}$ and $\sigma_{i}$ have rank $k-2$ or less. This implies that
$\sigma_{i_{k}}$ has rank $k-2$ or less, which contradicts the fact that
$\sigma_{i_{k}}$ has rank $k-1$ or higher. Thus, we deduce that $f(\pi)$
avoids $Q_{k}$.

In order to show that the map $f$ is a bijection, we construct a map $g$ from
the set $\mathcal{S}_{n}(H_{k},Q_{k})$ to the set $\mathcal{S}_{n}(G_{k})$.
Let
$\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n}\in\mathcal{S}_{n}(H_{k},Q_{k})$.
We aim to obtain $g(\sigma)$ by leaving all entries of $\sigma$ that are of
rank $k-2$ or less in their place and rearranging the entries of rank $k-1$ or
higher. Label the blocks of $\sigma$ from left to right by
$B_{1},B_{2},\ldots,B_{s}$. Let $P_{i}$ be the set of positions of $\pi$ in
which an entry, that has rank $k-1$ or higher and belongs to the block
$B_{i}$, is located, and let $R$ be the set of entries of $\pi$ that are of
rank $k-1$ or higher. Now we fill the positions of $P_{i}$ as follows.

  * Step 1.

Choose $|P_{1}|$ smallest entries from $R$ that are larger than the closest
entry of rank $k-2$ on the left of the positions of $P_{1}$, and fill the
positions of $P_{1}$ with the selected entries from left to right in
increasing order.

  * Step 2.

Choose $|P_{2}|$ smallest entries from $R$ that have not been placed yet and
are larger than the closest entry of rank $k-2$ on the left of the positions
of $P_{2}$. Fill the positions of $P_{2}$ with the selected entries from left
to right in increasing order.

  * Step 3.

Fill the positions of $P_{3}$, $P_{4}$, $\ldots$, $P_{s}$ as in Step 2.

Let $g(\sigma)$ be the obtained permutation.

###### Example 2.2

Consider $\pi=13576(10)(11)4928\in\mathcal{S}_{11}(H_{6},Q_{6})$. Then we have
$B_{1}=1357$, $B_{2}=6(10)(11)$, $B_{3}=49$ and $B_{4}=28$. Moreover, we have
$P_{1}=\emptyset$, $P_{2}=\\{6,7\\}$, $P_{3}=\\{9\\}$, $P_{4}=\\{11\\}$ and
$R=\\{8,9,10,11\\}$. According to the definition of $g$, we have
$g(\pi)=13576894(10)2(11)$.

Since the existence of $\sigma$ shows that there is at least one way to assign
the entries of $R$ to the positions of $P_{i}$, the definition of $g$ always
enables us to create $g(\sigma)$.

Notice that if entry $\sigma_{i}$ has rank $k-2$ or less, then $\sigma_{i}$
does not move in the above procedure, and the rank of $\sigma_{i}$ do not
change. If entry $\sigma_{i}$ has rank $k-1$ or higher, then $\sigma_{i}$ may
have moved and the rank of $\sigma_{i}$ in $g(\sigma)$ is $k-1$ or higher. We
claim that if $\sigma_{i-1}>\sigma_{i}$, then the rank of $\sigma_{i}$ is
$k-2$ or less. If not, the longest increasing subsequence that ends in
$\sigma_{i}$ combining with $\sigma_{i-1}$ would form a $Q_{k}$ in $\sigma$.

By the similar reasoning as in the proof of the equality
$\mathcal{D}(\pi)=\mathcal{D}(f(\pi))$, one can verify that
$\mathcal{D}(\sigma)=\mathcal{D}(g(\sigma))$. Now we proceed to show that
$g(\sigma)$ avoids $G_{k}$. Let $g(\sigma)=\pi_{1}\pi_{2}\ldots\pi_{n}$.
Suppose that the the subsequence $\pi_{i_{1}}\pi_{i_{2}}\ldots\pi_{i_{k}}$ is
a pattern $G_{k}$ in $\pi$ with $i_{1}<i_{2}<\ldots<i_{k}$. Without loss of
generality, assume that $\pi_{i_{k-2}}$ has rank $k-2$. Clearly, both
$\pi_{i_{k-1}}$ and $\pi_{i_{k}}$ have rank $k-1$ or higher in $\pi$. Suppose
that $i_{k-1}\in P_{j}$ for some $j$, and $\sigma_{s}$ is the closest entry of
rank $k-2$ on the left of the positions of $P_{j}$ in $\sigma$. Recall that
the map $g$ does not change the position of entry $\sigma_{i}$ that has rank
$k-2$ or less, and the rank of $\sigma_{i}$ does not change in $\pi$. So we
have $\pi_{s}=\sigma_{s}$ and $\pi_{i_{k-2}}=\sigma_{i_{k-2}}$, and the rank
of $\pi_{s}$ (resp. $\sigma_{i_{k-2}}$) is $k-2$ in $\pi$ (resp. $\sigma$).
Moreover, since $\sigma_{s}$ is the closest entry of rank $k-2$ on the left of
the positions of $P_{j}$ in $\sigma$, we have $i_{k-2}\leq s$. This implies
that $\sigma_{s}\leq\sigma_{i_{k-2}}=\pi_{i_{k-2}}$. Then, we have
$\pi_{i_{k}}>\sigma_{s}$, which contradicts the selection of $\pi_{i_{k-1}}$
when filling the positions of $P_{j}$. Hence, we have
$g(\sigma)\in\mathcal{S}_{n}(G_{k})$.

In order to show that the map $f$ is a bijection, it suffices to show that the
maps $f$ and $g$ are inverses of each other. First, we wish to prove that for
any $\pi\in\mathcal{S}_{n}(G_{k})$, we have $g(f(\pi))=\pi$. Since
$\mathcal{D}(f(\pi))=\mathcal{D}(\pi)$, $\pi$ and $f(\pi)$ have the same
number of blocks. Suppose that
$B^{\prime}_{1},B^{\prime}_{2},\ldots,B^{\prime}_{s}$ are the blocks of
$f(\pi)$, that are listed from left to right. Let $P^{\prime}_{i}$ be the set
of positions of $f(\pi)$ in which an entry that has rank $k-1$ or higher and
belongs to the block $B^{\prime}_{i}$, is located, and let $R^{\prime}$ be the
set of entries of $f(\pi)$ that are of rank $k-1$ or higher. Recall that if
the entry $\pi_{i}$ of $\pi$ has rank $k-2$ or less, then the map $f$ does not
change the position of $\pi_{i}$, and the rank of $\pi_{i}$ do not change. If
entry $\pi_{i}$ of $\pi$ has rank $k-1$ or higher, then $\pi_{i}$ may have
moved and the rank of $\pi_{i}$ in $f(\pi)$ is $k-1$ or higher. So we have
$P_{i}=P^{\prime}_{i}$ and $R=R^{\prime}$. Since $\pi$ avoids $G_{k}$, the
positions of $P_{1}$ in $\pi$ are filled with $|P_{1}|$ smallest elements of
$R$ in increasing order which are larger than the closet entry of rank $k-2$
on the left of the positions of $P_{1}$. The positions of $P_{2}$ are filled
with the next $|P_{2}|$ smallest entries of $R$ in increasing order that have
not been placed and larger than the closet entry of rank $k-2$ on the left of
the positions of $P_{2}$. And the positions of $P_{3},\ldots,P_{s}$ are filled
in the same manner as the positions of $P_{2}$. Thus, according to the
definition of $g$, it is easy to check that $g(f(\pi))=\pi$.

Our next goal is to show that for any $\sigma\in\mathcal{S}_{n}(H_{k},Q_{k})$,
we have $f(g(\sigma))=\sigma$. Since
$\mathcal{D}(g(\sigma))=\mathcal{D}(\sigma)$, $\sigma$ and $f(\sigma)$ have
the same number of blocks. Suppose that
$B^{\prime}_{1},B^{\prime}_{2},\ldots,B^{\prime}_{s}$ are the blocks of
$f(\sigma)$, that are listed from left to right. Let $P^{\prime}_{i}$ be the
set of positions of $f(\pi)$ in which an entry that has rank $k-1$ or higher
and belongs to the block $B^{\prime}_{i}$, is located, and let $R^{\prime}$ be
the set of entries of $f(\pi)$ that are of rank $k-1$ or higher. Recall that
if entry $\sigma_{i}$ of $\sigma$ has rank $k-2$ or less, then the map $g$
does not change the position of $\sigma_{i}$, and the rank of $\sigma_{i}$ do
not change. If entry $\sigma_{i}$ of $\sigma$ has rank $k-1$ or higher, then
$\sigma_{i}$ may have moved and the rank of $\sigma_{i}$ in $g(\sigma)$ is
$k-1$ or higher. So we have $P_{i}=P^{\prime}_{i}$ and $R=R^{\prime}$. Since
$\sigma$ avoids $H_{k}$, the positions of $P_{1}$ in $\sigma$ are filled with
$|P_{1}|$ largest elements of $R$ in increasing order which are larger than
the closet entry of rank $k-2$ on the left of the positions of $P_{1}$. The
positions of $P_{2}$ are filled with the next $|P_{2}|$ largest entries of $R$
in increasing order that have not been placed and larger than the closet entry
of rank $k-2$ on the left of the positions of $P_{2}$. And the positions of
$P_{3},\ldots,P_{s}$ are filled in the same manner as the positions of
$P_{2}$. Thus, according to the definition of $f$, it is easy to check that
$f(g(\sigma))=\sigma$.

##  3 Proof of Theorem 1.5

Let us begin with some necessary definitions and notations. We draw Young
diagrams in English notation, and number columns from left to right and rows
from bottom to up. For example, the square $(1,2)$ is the second square in the
bottom row of a Young diagram.

A transversal of a Young diagram
$\lambda=(\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n})$ is a filling
of the squares of $\lambda$ with $1^{\prime}s$ and $0^{\prime}s$ such that
every row and column contains exactly one $1$. Denote by
$T=\\{(t_{i},i)\\}_{i=1}^{n}$ the transversal in which the square $(t_{i},i)$
is filled with a $1$ for all $i\leq n$. For example the transversal
$T=\\{(1,1),(2,3),(3,2),(4,4),(5,5)\\}$ of a Young diagram $(5,4,3,3,1)$ is
illustrated as Figure 1.

$1$$0$$0$$1$$0$$1$$0$$0$$0$$0$$1$$0$$0$$0$$0$$1$ Figure 1:  The transversal
$T=\\{(1,1),(2,3),(3,2),(4,4),(5,5)\\}$.

In this section, we will consider permutations as permutation matrices. Given
a permutation $\pi=\pi_{1}\pi_{2}\ldots\pi_{n}\in\mathcal{S}_{n}$, its
corresponding permutation matrix is a transversal of the square shape
$\lambda_{1}=\lambda_{2}=\ldots=\lambda_{n}=n$ in which the square
$(\pi_{i},i)$ is filled with a $1$ for all $1\leq i\leq n$ and all the other
squares are filled with $0^{\prime}s$.

The notion of pattern avoidance is extended to transversal of a Young diagram
in [1]. Given a permutation $\alpha$ of $\mathcal{S}_{m}$, let $M$ be its
permutation matrix. A transversal $L$ of a Young diagram $\lambda$ will be
said to contain $\alpha$ if there exists two subsets of the index set $[n]$,
namely, $R=\\{r_{1}<r_{2}<\ldots<r_{m}\\}$ and
$C=\\{c_{1}<c_{2}<\ldots<c_{m}\\}$, such that the matrix on $R$ and $C$ is a
copy of $M$ and each of the squares $(r_{j},c_{j})$ falls within the Young
diagram.

###  3.1 The map $\Phi$ from the set $\mathcal{S}_{n}(F_{k})$ to the set
$\mathcal{S}_{n}(H_{k},Q_{k})$

Before we describe the map $\Phi$, let us review a transformation $\theta$
introduced in [1]

Let $\pi=\\{(\pi_{1},1),(\pi_{2},2),\ldots,(\pi_{n},n)\\}$. Suppose that $G$
is the submatrix of $\pi$ at columns $c_{1}<c_{2}<\ldots<c_{k-1}<c_{k}$ and
rows $r_{1}<r_{2}<\ldots<r_{k-1}<r_{k}$, which is isomorphic to $J_{k}$. In
other words, the square $(r_{i},c_{i})$ is filled with $1$ for all
$i=1,2,\ldots,k$. Let $\theta(G)$ be the submatrix at the same rows and
columns as $G$, such that the squares $(r_{2},c_{1})$, $(r_{3},c_{2})$,
$\ldots$, $(r_{k},c_{k-1})$, $(r_{1},c_{k})$ are filled with $1^{\prime}s$ and
all the other squares are filled with $0^{\prime}s$. Clearly, $\theta(G)$ is
isomorphic to $F_{k}$.

Based on the transformation $\theta$, we define the following three
transformations, which will play an essential role in the construction of the
map $\Phi$.

Suppose that $G$ is the submatrix of $\pi$ at columns
$c_{1}<c_{2}<\ldots<c_{k-1}<s<s+1<\ldots<c_{k}-1<c_{k}$ and rows
$r_{1}<r_{2}<\ldots<r_{k-1}<r_{k}>\pi_{c_{k}-1}>\ldots>\pi_{s+1}>\pi_{s}$, in
which the squares $(r_{i},c_{i})$ are filled with $1^{\prime}s$ for all
$i=1,2,\ldots,k$. Let $\alpha(G)$ be the submatrix at the same rows and
columns as $G$, such that the squares $(r_{2},c_{1})$, $(r_{3},c_{2})$,
$\ldots$, $(r_{k},c_{k-1})$, $(r_{1},s)$, $(\pi_{s},s+1)$, $\ldots$,
$(\pi_{c_{k}-1},c_{k})$ are filled with $1^{\prime}s$ and all the other
squares are filled with $0^{\prime}s$. Clearly, the submatrix at columns
$c_{1}<c_{2}<\ldots<c_{k-1}<s$ and rows $r_{1}<r_{2}<\ldots<r_{k-1}<r_{k}$ is
isomorphic to $F_{k}$.

Suppose that $G$ is the submatrix of $\pi$ at columns
$c_{1}<c_{2}<\ldots<c_{k-1}<c_{k}<c_{k}+1<\ldots<t-1<t$ and rows
$r_{1}<r_{2}<\ldots<r_{k}>\pi_{c_{k}+1}>\ldots>\pi_{t-1}>\pi_{t}$, in which
the squares $(r_{i},c_{i})$ are filled with $1^{\prime}s$ for all
$i=1,2,\ldots,k$. Define $\beta(G)$ to be the submatrix at the same columns
and rows as $G$, such that the squares $(r_{2},c_{1})$, $(r_{3},c_{2})$,
$\ldots$, $(r_{k},c_{k-1})$, $(\pi_{c_{k}+1},c_{k})$, $\ldots$,
$(\pi_{t},t-1)$, $(r_{1},t)$ are filled with $1^{\prime}s$ and all the other
squares are filled with $0^{\prime}s$. Clearly, the submatrix at columns
$c_{1}<c_{2}<\ldots<c_{k-1}<t$ and rows $r_{1}<r_{2}<\ldots<r_{k-1}<r_{k}$ is
isomorphic to $F_{k}$.

The transformation $\phi$:  Suppose that $\pi$ is a permutation in
$\mathcal{S}_{n}$. First, find the highest square $(p_{1},q_{1})$ containing a
$1$, such that there is an $H_{k}$ or $Q_{k}$ in $\pi$ in which the $1$
positioned at the square$(p_{1},q_{1})$ is the leftmost entry. Then, find the
leftmost square $(p_{2},q_{2})$ containing a $1$, such that there is an
$H_{k}$ or $Q_{k}$ in $\pi$ in which the $1^{\prime}s$ positioned at the
squares $(p_{1},q_{1})$ and $(p_{2},q_{2})$ are the leftmost two
$1^{\prime}s$. Find $(p_{3},q_{3}),(p_{4},q_{4}),\ldots,(p_{k-1},q_{k-1})$ one
by one as $(p_{2},q_{2})$.

If there is an $H_{k}$ in which the $1^{\prime}s$ positioned at the squares
$(p_{1},q_{1}),(p_{2},q_{2}),\ldots$ $(p_{k-1},q_{k-1})$ are the leftmost
$k-1$ $1^{\prime}s$, then find the highest square $(p_{k},q_{k})$ containing a
$1$, such that the $1^{\prime}s$ positioned at the squares
$(p_{1},q_{1}),(p_{2},q_{2}),\ldots$ $(p_{k},q_{k})$ form an $H_{k}$. Find the
largest $s$ such that $s-1\in\mathcal{D}(\pi)$ and $q_{k-1}<s<q_{k}$. Now we
proceed to construct a permutation $\phi(\pi)$ by the following procedure.

  1. Case 1.

$q_{k}=n$ or $\pi_{q_{k}-1}>\pi_{q_{k}+1}$. Let $G$ be the submatrix of $\pi$
at columns $q_{1}<q_{2}<\ldots<q_{k-1}<s<s+1<\ldots<q_{k}-1<q_{k}$ and rows
$p_{1}<p_{2}<\ldots<p_{k}>\pi_{q_{k}-1}>\ldots>\pi_{s+1}>\pi_{s}$. Replace $G$
by $\alpha(G)$ and leave all the other squares fixed.

  2. Case 2.

$\pi_{q_{k}-1}<\pi_{q_{k}+1}$. Find the least $t$ such that $t>q_{k}$ and
$t\in\mathcal{A}(\pi)$. If such $t$ does not exist, set $t=n$. Let $G$ be the
submatrix of $\pi$ at columns
$q_{1}<q_{2}<\ldots<q_{k-1}<q_{k}<q_{k}+1<\ldots<t-1<t$ and rows
$p_{1}<p_{2}<\ldots<p_{k}>\pi_{q_{k}+1}>\ldots>\pi_{t-1}>\pi_{t}$. Replace $G$
by $\beta(G)$ and leave all the other squares fixed.

If such an $H_{k}$ does not exist, then find the leftmost square
$(p_{k},q_{k})$ containing a $1$, such that the $1^{\prime}s$ positioned at
the squares $(p_{1},q_{1}),(p_{2},q_{2})\ldots,(p_{k},q_{k})$ form a $Q_{k}$.
Construct a permutation $\phi(\pi)$ by the following procedure.

  1. Case 3.

$q_{k}\in\mathcal{A}(\pi)$. Let $G$ be the submatrix of $\pi$ at columns
$q_{1}<q_{2}<\ldots<q_{k-2}<q_{k}$ and rows
$p_{1}<p_{2}<\ldots<p_{k-2}<p_{k}$. Replace $G$ by $\theta(G)$ and leave all
the other squares fixed.

  2. Case 4.

Otherwise, find the least $t$ such that $t>q_{k}$ and $t\in\mathcal{A}(\pi)$.
If such $t$ does not exist, set $t=n$. Let $G$ be the submatrix of $\pi$ at
columns $q_{1}<q_{2}<\ldots<q_{k-2}<q_{k}<q_{k}+1<q_{k}+2<\ldots<t-1<t$ and
rows
$p_{1}<p_{2}<\ldots<p_{k-2}<p_{k}>\pi_{q_{k}+1}>\pi_{q_{k}+2}>\ldots>\pi_{t-1}>\pi_{t}$.
Replace $G$ by $\beta(G)$ and leave all the other squares fixed.

###### Remark 3.1

Notice that the definition of $H_{k}$ ensures that there exists an $s$ such
that $s-1\in\mathcal{D}(\pi)$ and $q_{k-1}<s\leq q_{k}$. In fact, we have
$q_{k-1}<s<q_{k}$. If not, then the $1^{\prime}s$ positioned at the squares
$(p_{2},q_{2}),(p_{3},q_{3})\ldots(p_{k-1},q_{k-1}),(\pi_{q_{k}-1},q_{k}-1),(p_{k},q_{k})$
would form a $Q_{k}$, which contradicts the selection of $(p_{1},q_{1})$.

###### Remark 3.2

We denote the resulting permutation in Case 1, Case 2, Case 3 and Case 4 by
$\phi_{1}(\pi),\phi_{2}(\pi)$, $\phi_{3}(\pi)$ and $\phi_{4}(\pi)$,
respectively.

It is obvious that the transformation $\phi$ changes every occurrence of
$H_{k}$ (or $Q_{k}$) to an occurrence of $F_{k}$. Denote by $\Phi$ the
iterated transformation, that recursively transforms every occurrence of
$H_{k}$ (or $Q_{k}$) into $F_{k}$.

Using the notation of the algorithm for $\phi_{1}$, we label the squares
containing $1^{\prime}s$ in $G$ by
$a_{1},a_{2},\ldots,a_{k-1},c_{1},c_{2},\ldots,c_{q_{k}-s},a_{k}$, and the
squares containing $1^{\prime}s$ in $\alpha(G)$ by
$b_{1},b_{2},\ldots,b_{k},d_{1},d_{2},\ldots,d_{q_{k}-s}$, from left to right,
see Figure 2 for example.

$E_{1}$$E_{1}$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{5}$$c_{1}$$d_{1}$$c_{2}$$d_{2}$
Figure 2: The labelling of squares in $\phi_{1}(\pi)$ for $k=5$.

Using the notation of the algorithm for $\phi_{2}$, we label the squares
containing $1^{\prime}s$ in $G$ by
$a_{1},a_{2},\ldots,a_{k-1},a_{k},e_{1},e_{2},\ldots,e_{t-q_{k}}$, and the
squares containing $1^{\prime}s$ in $\beta(G)$ by
$b_{1},b_{2},\ldots,b_{k-1},f_{1},f_{2},\ldots,f_{t-q_{k}},b_{k}$, from left
to right. We also label the square $(\pi_{s},s)$ by $c_{1}$, see Figure 3 for
example.

$E_{1}$$E_{1}$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{5}$$c_{1}$$f_{1}$$f_{2}$$e_{1}$$e_{2}$
Figure 3: The labelling of squares in $\phi_{2}(\pi)$ for $k=5$.

Using the notation of the algorithm for $\phi_{3}$, we label the squares
containing $1^{\prime}s$ in $G$ by $a_{1},a_{2},\ldots,a_{k-2},a_{k},$ and the
squares containing $1^{\prime}s$ in $\theta(G)$ by
$b_{1},b_{2},\ldots,b_{k-2},b_{k}$, from left to right. We also label the
square $(p_{k-1},q_{k-1})$ by $b_{k-1}$ (or $a_{k-1}$), see Figure 4 for
example.

$E_{2}$$E_{2}$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$$a_{6}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{6}$$(b_{5})$
Figure 4: The labelling of squares in $\phi_{3}(\pi)$ for $k=6$.

Using the notation of the algorithm for $\phi_{4}$, we label the squares
containing $1^{\prime}s$ in $G$ by $a_{1},a_{2},\ldots,a_{k-2},a_{k},$
$e_{1},e_{2},\ldots,e_{t-q_{k}}$, and the squares containing $1^{\prime}s$ in
$\beta(G)$ by
$b_{1},b_{2},\ldots,b_{k-2},f_{1},f_{2},\ldots,f_{t-q_{k}},b_{k}$, from left
to right. We also label the square $(p_{k-1},q_{k-1})$ by $b_{k-1}$ (or
$a_{k-1}$), see Figure 5 for example.

$E_{2}$$E_{2}$$E_{2}$$a_{1}$$a_{2}$$a_{3}$$a_{4}$$a_{5}$$a_{6}$$b_{1}$$b_{2}$$b_{3}$$b_{4}$$b_{6}$$(b_{5})$$e_{1}$$f_{1}$$e_{2}$$f_{2}$
Figure 5: The labelling of squares in $\phi_{4}(\pi)$ for $k=6$.

In $\phi_{1}(\pi)$ or $\phi_{2}(\pi)$, we denote by $E_{1}$ the union of the
following four parts of the board: the board that is above $a_{1}$ but below
$b_{1}$ and to the left of $a_{1}$, the board that is above $a_{k-1}$ but
below $b_{k-1}$, to the left of $c_{1}$ and to the right of $a_{k-1}$, the
union of the rectangles with corners $a_{i}$ and $b_{i+1}$ for
$i=1,2,\ldots,k-2$, and the board that is above $a_{k}$ and to the right of
$c_{1}$, see Figures 2 and 3 for example.

We claim that there are no $1^{\prime}s$ inside $E_{1}$ in $\pi$,
$\phi_{1}(\pi)$ or $\phi_{2}(\pi)$. By the selection of $a_{k}$, there is no
$1$ to the right of $c_{1}$ and above $a_{k}$ in $\pi$, $\phi_{1}(\pi)$ or
$\phi_{2}(\pi)$. Suppose that there is a $1$ in the rectangle with corners
$a_{i}$ and $b_{i+1}$ for $i=1,2,\ldots,k-2$, then that 1 combining with the
$1^{\prime}s$ positioned at $a_{1},a_{2},\ldots,a_{i},a_{i+2},\ldots,a_{k}$
would form an $H_{k}$ in $\pi$, which contradicts the selection of $a_{i+1}$.
If there is a $1$ above $a_{1}$ but below $b_{1}$, then that $1$, combining
with the $1^{\prime}s$ positioned at $a_{2},a_{3},\ldots,a_{k}$ would form a
$H_{k}$ in $\pi$, which contradicts the selection of $a_{1}$. If there is a
$1$ above $a_{k-1}$ but below $b_{k-1}$ and to the left of $c_{1}$, then that
$1$, combining with the $1^{\prime}s$ positioned at $a_{2},a_{3},\ldots,a_{k}$
would form a $H_{k}$ in $\pi$, which contradicts the selection of $a_{1}$.
Thus, all the $1^{\prime}s$ are to the left of $E_{1}$ or to the right of
$E_{1}$ in $\pi$, $\phi_{1}(\pi)$ or $\phi_{2}(\pi)$.

In $\phi_{3}(\pi)$ and $\phi_{4}(\pi)$, we denote by $E_{2}$ the union of the
following four parts of the board: the board that is above $a_{1}$ but below
$b_{1}$ and to the left of $a_{1}$, the board that is above and to the right
of $a_{k-2}$ but below $a_{k-1}$, and to the left of $a_{k}$, the union of the
rectangles with corners $a_{i}$ and $b_{i+1}$ for $i=1,2,\ldots,k-2$, and the
board that is above $a_{k-1}$ and to the right of $a_{k}$, see Figures 4 and 5
for example.

We claim that there are no $1^{\prime}s$ inside $E_{2}$ in $\pi$,
$\phi_{3}(\pi)$ and $\phi_{4}(\pi)$. By similar arguments in $E_{1}$, one can
easily verify that there are no $1^{\prime}s$ inside the board that is above
$a_{1}$ but below $b_{1}$ and to the left of $a_{1}$, the union of the
rectangles with corners $a_{i}$ and $b_{i+1}$ for $i=1,2,\ldots,k-2$, and the
board that is above $a_{k-1}$ and to the right of $a_{k}$. It remains to show
that there are no $1^{\prime}s$ inside the board that is above $a_{k-2}$ but
below $a_{k-1}$ and to the left of $a_{k}$. According to the definition of
$Q_{k}$, all of the $1^{\prime}s$ between $a_{k-1}$ and $a_{k}$ are above
$a_{k-1}$. This implies that there are no $1^{\prime}s$ inside the board that
is below and to the right of $a_{k-1}$, and to the left of $a_{k}$. Now
suppose that there is a $1$ inside the rectangle with corners $a_{k-2}$ and
$a_{k-1}$. Suppose that this $1$ is at the square $(\pi_{g},g)$. If
$(\pi_{g},g)$ is below $a_{k}$, then the $1^{\prime}s$ positioned at the
squares $a_{2},a_{3},\ldots,a_{k-2},(\pi_{g},g),a_{k-1},a_{k}$ would form a
$Q_{k}$ in $\pi$, which contradicts the selection of $a_{1}$. If $(\pi_{g},g)$
is above $a_{k}$, then we have two cases. If there exists a $j$ such that
$g\leq j<q_{k}$ and $j\in\mathcal{D}(\pi)$, then the $1^{\prime}s$ positioned
at $a_{1},a_{2},\ldots,a_{k-2},(\pi_{g},g),a_{k-1}$ would form an $H_{k}$ in
$\pi$, which contradicts the selection of $a_{k-1}$. Otherwise, the
$1^{\prime}s$ positioned at the squares
$a_{1},a_{2},\ldots,a_{k-2},(\pi_{g},g),a_{k}$ would form a $Q_{k}$ in $\pi$,
which contradicts the selection of $a_{k-1}$. Hence, we have concluded that
there are no $1^{\prime}s$ inside the board that is above $a_{k-2}$ but below
$a_{k-1}$ and to the left of $a_{k}$. Hence, the claim is proved. In other
words, all the $1^{\prime}s$ of $\pi$, $\phi_{3}(\pi)$ or $\phi_{4}(\pi)$ are
to the left or to the right of $E_{2}$.

###### Definition 3.3

A $1$ is said to be strictly to the left (resp. right) of $E_{1}$(or $E_{2}$)
if it is lying to the left (resp. right) of $E_{1}$ (or $E_{2}$) and does not
belong to the boundary of $E_{1}$ (or $E_{2}$).

We need the following useful properties that will play an essential role in
the construction of vertical slide algorithm and horizontal slide algorithm
for $\phi$ Properties

  * (1)

For any $1\leq i\leq k-2$, the board that is above $a_{1}$ and below $b_{i}$
cannot contain a $J_{i}$ with all its $1^{\prime}s$ strictly to the left of
$E_{1}$ (or $E_{2}$) in $\phi(\pi)$.

  * (2)

For any $1\leq i<j\leq k-2$, the rectangle with corners $b_{i}$ and $b_{j}$
cannot contain a $J_{j-i}$ with all its $1^{\prime}s$ strictly to the left of
$E_{1}$ (or $E_{2}$) in $\phi(\pi)$. Moreover, the rectangle with corners
$b_{i}$ and $b_{k-1}$ cannot contain a $J_{k-1-i}$ with all its $1^{\prime}s$
strictly to the left of $E_{1}$ in $\phi_{1}(\pi)$ (or $\phi_{2}(\pi)$).

Proof.

  * (1)

If there is such a $J_{i}$ below $b_{i}$ in $\phi(\pi)$, then it is below
$a_{i+1}$. Therefore these $i$ $1^{\prime}s$, combining with
$a_{i+1},a_{i+2},\ldots,a_{k}$, will either form an $H_{k}$ or a $Q_{k}$ in
$\pi$, which contradicts the selection of $a_{1}$.

  * (2)

If there is a $J_{j-i}$ in this region, then either its leftmost $1$ is to the
left to $b_{i+1}$ (and hence to the left of $a_{i+1}$), or else it lies to the
right of $b_{i+1}$ (and $a_{i+1}$). In the first case,
$a_{1},a_{2},\ldots,a_{i}$, combining with this $J_{j-i}$ and
$a_{j+1},\ldots,a_{k}$, will form an $H_{k}$ (or $Q_{k}$) in $\pi$, which
contradicts the selection of $a_{i+1}$. In the second case,
$a_{2},a_{3},\ldots,a_{i+1}$, combining with this $J_{j-i}$ and
$a_{j+1},\ldots,a_{k}$, will form an $H_{k}$ (or $Q_{k}$) in $\pi$, which
contradicts the selection of $a_{1}$.

Now we proceed to introduce the vertical slide algorithm and horizontal slide
algorithm for $\phi$.

Suppose that $H$ is a $J_{t}$ in $\phi(\pi)$. Label the squares containing
$1^{\prime}s$ of $H$ by $h_{1},h_{2},\ldots,h_{t}$, from left to right.

Vertical slide algorithm for $\phi$: When $H$ is in $\phi_{1}(\pi)$ (or
$\phi_{2}(\pi)$), find the largest $i$ such that $b_{i}$ falls in $H$ with
$i\leq k-1$; otherwise, find the largest $i$ such that $b_{i}$ falls in $H$
with $i\leq k-2$. If there is a $1$ of $H$ which is below $b_{i}$ and to the
right of $E_{1}$ (or $E_{2}$), find the rightmost square containing such a $1$
and denote it by $h_{y}$. Find $x$ such that $h_{y}$ is to the right of
$b_{x}$, and to the left of $b_{x+1}$. By property $(2)$, there are at most
$i-x$ $1^{\prime}s$ in $H$, which are above $b_{x}$ but not above $b_{i}$, and
weakly to the left of $E_{1}$ (or $E_{2}$). So we can replace these
$1^{\prime}s$ by $b_{x+1},b_{x+2},\ldots,b_{i}$, and hence by
$a_{x+1},a_{x+2},\ldots,a_{i}$.

We can repeat the vertical slide algorithm until the following two cases
appear.
(1) There is no $b_{i}$ that falls in $H$.
(2) There is such a $b_{i}$, but $h_{y}$ does not exist. By Property (1),
there are at most $i$ $1^{\prime}s$ of $H$ that are above $a_{1}$ but not
above $b_{i}$, and weakly to the left of $E_{1}$ (or $E_{2}$). So we can
replace these $1^{\prime}s$ by $a_{1},a_{2},\ldots,a_{i}$ to form an $J_{t}$
in $\pi$.

Suppose that $H$ is a $J_{t}$ in $\phi(\pi)$. Label the squares containing the
$1^{\prime}s$ of $H$ by $h_{1},h_{2},\ldots,h_{t}$, from left to right. Assume
that $h_{t}$ is not above $b_{k-1}$ when $H$ is in $\phi_{1}(\pi)$ (or
$\phi_{2}(\pi)$), and not above $b_{k-2}$ when $H$ is in $\phi_{3}(\pi)$ (or
$\phi_{4}(\pi)$).

Horizontal slide algorithm for $\phi$: When $H$ is in $\phi_{1}(\pi)$ (or
$\phi_{2}(\pi)$), find the least $i$ such that $b_{i}$ falls in $H$ with
$i\leq k-1$; otherwise, find the least $i$ such that $b_{i}$ falls in $H$ with
$i\leq k-2$. If there is a $1$ of $H$ which is above $b_{i}$ and to the right
of $E_{1}$ (or $E_{2}$), find the leftmost square containing such a $1$ and
denote it by $h_{y}$. Find $x$ such that $h_{y}$ is above $b_{x}$, and below
$b_{x+1}$. By property $(2)$, there are at most $x+1-i$ $1^{\prime}s$ in $H$,
which are below $b_{x+1}$ but not below $b_{i}$, and weakly to the left of
$E_{1}$ (or $E_{2}$). So we can replace these $1^{\prime}s$ by
$b_{i},b_{i+1},\ldots,b_{x}$, and hence by $a_{i+1},a_{i+2},\ldots,a_{x+1}$.

We can repeat the horizontal slide algorithm until the following two cases
appear.
(1) There is no $b_{i}$ that falls in $H$.
(2) There is such a $b_{i}$, but $h_{y}$ does not exist. Find the least $v$
such that $h_{t}$ is not above $b_{v}$. By property $(2)$, we have at most
$v-i$ $1^{\prime}s$ of $H$ that are below $b_{v}$ but not below $b_{i}$ and
weakly to the left of $E_{1}$(or $E_{2}$). So we can replace these
$1^{\prime}s$ by $a_{i+1},a_{i+2},\ldots,a_{v}$ to form an $J_{t}$ in $\pi$.

Our next goal is to show that the transformation $\phi$ have the following
properties, which are essential in the proof of Theorem 1.5.

###### Lemma 3.4

If there is no $F_{k}$ with at least one square in a row below $a_{1}$, then
we have $\mathcal{D}(\pi)=\mathcal{D}(\phi(\pi))$.

Proof. Since there are no $1^{\prime}s$ inside $E_{1}$ (or $E_{2}$) and no
$F_{k}$ with at least one square in a row below $a_{1}$, one can easily verify
that $\mathcal{D}(\pi)=\mathcal{D}(\phi(\pi))$. The details are omitted here.

###### Lemma 3.5

If $\pi$ contains no $F_{k}$ with at least one square in a row below $a_{1}$,
then $\phi(\pi)$ contains no such $F_{k}$.

Proof. If not, suppose that $H$ is such an $F_{k}$ in $\phi(\pi)$. Label the
squares containing the $1^{\prime}s$ of $H$ by $h_{1},h_{2},\ldots,h_{k}$,
from left to right. Then $h_{k}$ is below $a_{1}$.

We claim that $h_{k}$ must be positioned to the left of $a_{k-1}$. If not,
then $a_{1},a_{2},\ldots,$ $a_{k-1},$ $h_{k}$ would form an $F_{k}$ in $\pi$,
which contradicts the hypothesis. From the construction of the transformation
$\phi$, it follows that at least one of $b_{1},b_{2},\ldots,b_{k-2}$ must fall
in $H$. Otherwise, $H$ is an $F_{k}$ with at least one square in a row below
$a_{1}$ in $\pi$, which contradicts the hypothesis.

By applying the vertical slide algorithm repeatedly to the $J_{k-1}$
consisting of $h_{1},h_{2},\ldots,h_{k-1}$, we can get a $J_{k-1}$ not below
$a_{1}$ in $\pi$. Then, that $J_{k-1}$ combining with $h_{k}$ will form an
$F_{k}$ in $\pi$, which contradicts the hypothesis.

###### Lemma 3.6

The board that is to the left of $b_{t+1}$ and above $a_{1}$ cannot contain a
$J_{t}$ in $\phi(\pi)$ with its highest $1$ below $b_{t}$ for
$t=1,2,\ldots,k-1$.

Proof. First we aim to prove the assertion for $1\leq t\leq k-2$. Suppose that
$H$ is such a $J_{t}$ in $\phi(\pi)$. Label the squares containing the
$1^{\prime}s$ of $H$ by $h_{1},h_{2},\ldots,h_{t}$ from left to right. We
claim that at least one of $b_{1},b_{2},\ldots,b_{t-1}$ must fall in $H$.
Otherwise, these $t$ $1^{\prime}s$, combining with
$a_{t+1},a_{t+2},\ldots,a_{k}$, would form an $H_{k}$ or $Q_{k}$ in $\pi$.
This contradicts the selection of $a_{1}$.

By applying the the horizontal slide algorithm repeatedly to $H$, we can get a
$J_{t}$ in $\pi$. It is easy to check that the obtained $J_{t}$ is below and
to the left of $a_{t+1}$ and above $a_{1}$. That $J_{t}$, combining with
$a_{t+1},a_{t+2},\ldots,a_{k}$, would form an $H_{k}$ or $Q_{k}$ in $\pi$.
This contradicts the selection of $a_{1}$. Thus, we have concluded that the
assertion holds for $1\leq t\leq k-2$.

Now we proceed to show that the assertion also holds for $t=k-1$. Suppose that
$G$ is a $J_{k-1}$ in $\phi(\pi)$, which is to the left of $b_{k}$ and below
$b_{k-1}$. We label the squares containing the $1^{\prime}s$ of $G$ by
$g_{1},g_{2},\ldots,g_{k-1}$, from left to right. We have three cases.

Case 1. $G$ is in $\phi_{1}(\pi)$. By repeating the horizontal slide
algorithm, we can get a $J_{k-1}$ in $\pi$, which is to the left of $b_{k}$
and above $a_{1}$. Moreover, since $s-1\in\mathcal{D}(\pi)$ and
$\mathcal{D}(\pi)=\mathcal{D}(\phi(\pi))$, we have
$s-1\in\mathcal{D}(\phi(\pi))$. Recall that $b_{k}$ is at column $s$. Thus,
the obtained $J_{k-1}$ combining with $a_{k}$ would form an $H_{k}$ in $\pi$.
This contradicts the selection of $a_{1}$.

Case 2. $G$ is in $\phi_{2}(\pi)$. If $g_{k-1}\neq f_{i}$, we can get a
$J_{k-1}$ in $\pi$ by repeating the horizontal slide algorithm, which is below
and to the left of $a_{k}$ and above $a_{1}$. We label the squares containing
the $1^{\prime}s$ of this $J_{k-1}$ by $m_{1},m_{2},\ldots,m_{k-1}$, from left
to right. If $m_{k-1}$ is below $e_{1}$, then $m_{2},m_{3},\ldots,m_{k-1}$,
combining with $a_{k},e_{1}$, would form a $Q_{k}$ in $\pi$, which contradicts
the selection of $a_{1}$. If $m_{k-1}$ is above $e_{1}$, then it is positioned
to the left of $c_{1}$ in $\pi$ since all the $1^{\prime}s$ positioned at
columns $s,s+1,\ldots,q_{k}-1$ form a $J_{q_{k}-s}$, and
$(\pi_{q_{k}-1},q_{k}-1)$ is below $e_{1}=(\pi_{q_{k}+1},q_{k}+1)$. Moreover,
since $s-1\in\mathcal{D}(\pi)$ and $\mathcal{D}(\pi)=\mathcal{D}(\phi(\pi))$,
we have $s-1\in\mathcal{D}(\phi(\pi))$. Recall that $c_{1}$ is at column $s$.
Thus, $m_{1},m_{2},\ldots,m_{k-1},a_{k}$ will form an $H_{k}$, which
contradicts the selection of $a_{1}$.

If $g_{k-1}=f_{i}$ for some $i$, then we can get a $J_{k-1}$ in $\pi$ by
repeating the horizontal slide algorithm and replacing $f_{j}^{\prime}s$ by
$e_{j}^{\prime}s$ whenever $f_{j}$ falls in $G$. Notice that the rightmost $1$
of the obtained $J_{k-1}$ is $e_{i}$. If $i=1$, then this $J_{k-1}$ combining
with $a_{k}$ would form a $Q_{k}$ in $\pi$. For $i>1$, this $J_{k-1}$
combining with $e_{i-1}$ would form a $Q_{k}$ in $\pi$. In both cases, we get
a $Q_{k}$ that is above $a_{1}$. This contradicts the selection of $a_{1}$.

Case 3. $G$ is in $\phi_{3}(\pi)$ or $\phi_{4}(\pi)$. When $g_{k-1}\neq
f_{i}$, according to the definition of $Q_{k}$, there contains no
$1^{\prime}s$ which are below and to the right of $a_{k-1}$, and to the left
of $a_{k}$. So $g_{k-1}$ is to the left of $a_{k-1}$. Recall that we have
shown that there is no $J_{k-2}$ in $\phi(\pi)$, which is to the left of
$b_{k-1}$ and below $b_{k-2}$. So $g_{k-1}$ is below and to the left of
$b_{k-1}$ (and $a_{k-1}$), and above and to the left of $b_{k-2}$. By
repeating the vertical slide algorithm, we can get a $J_{k-1}$ not below
$a_{1}$ in $\pi$, whose rightmost $1$ is positioned at $g_{k-1}$. Then this
$J_{k-1}$ combining with $a_{k-1}$ would form an $H_{k}$ in $\pi$, which
contradicts the selection of $a_{k-1}$. When $g_{k-1}=f_{i}$ for some $i\geq
1$, by the same way as in Case 2, we can get a $Q_{k}$ above $a_{1}$ in $\pi$.
This contradicts the selection of $a_{1}$.

Thus, we deduce that the assertion also holds for $t=k-1$. This completes the
proof.

###### Lemma 3.7

The rows above $a_{1}$ cannot contain an $H_{k}$ or $Q_{k}$ in $\phi(\pi)$.

In order to prove Lemma 3.7, we need the following two lemmas.

###### Lemma 3.8

Suppose that $G$ is an $H_{k}$ above $a_{1}$ in $\phi(\pi)$. Label the squares
containing the $1^{\prime}s$ of $G$ by $g_{1},g_{2},\ldots,g_{k}$, from left
to right. Then the squares $g_{k}$ and $g_{k-1}$ are also filled with
$1^{\prime}s$ in $\pi$.

Proof. Here we only prove the assertion for $\phi_{1}(\pi)$ and
$\phi_{4}(\pi)$. All the other cases can be verified by similar arguments. By
Lemma 3.6, there is no $J_{k-1}$ below $b_{k-1}$ and to the left of $b_{k}$ in
$\phi_{1}(\pi)$ and $\phi_{4}(\pi)$. This implies that neither $g_{k-1}$ nor
$g_{k}$ will be any of $b_{i}^{\prime}s$ for $1\leq i\leq k-2$ in
$\phi_{1}(\pi)$ and $\phi_{4}(\pi)$. Moreover, neither $g_{k-1}$ nor $g_{k}$
will be any of $f_{i}^{\prime}s$ in $\phi_{4}(\pi)$. Thus, we have deduced
that the assertion holds for $\phi_{4}(\pi)$.

In order to prove the assertion for $\phi_{1}(\pi)$, it remains to show that
neither $g_{k}$ nor $g_{k-1}$ will be any of $b_{k-1}$ and $d_{i}^{\prime}s$
in $\phi_{1}(\pi)$. We have four cases.

  * (1)

If $g_{k}=b_{k-1}$, then $g_{1},g_{2},\ldots,g_{k-1}$ form a $J_{k-1}$, which
is to the left of $b_{k}$ and below $b_{k-1}$ in $\phi_{1}(\pi)$. This
contradicts Lemma 3.6.

  * (2)

If $g_{k-1}=b_{k-1}$, then $g_{k}$ is above $b_{k-1}$ and to the left of
$E_{1}$. This implies the square $g_{k}$ is also filled with a $1$ in $\pi$.
Since $\mathcal{D}(\pi)=\mathcal{D}(\phi(\pi))$, the $1^{\prime}s$ positioned
at $b_{k-1}$ and $g_{k}$ belong to two different blocks of $\phi(\pi)$ imply
that those positioned at $a_{k-1}$ and $g_{k}$ also belong to two different
blocks of $\pi$. Thus, $a_{1},a_{2},\ldots,a_{k-1},g_{k}$ form an $H_{k}$ in
$\pi$. This contradicts the selection of $a_{k}$ since $g_{k}$ is above
$a_{k}$.

  * (3)

If $g_{k}=d_{i}$ for some $i$, then we have that $g_{k-1}$ is to the left of
$b_{k}$ since $d_{1}$, $d_{2}$, $\ldots,d_{q_{k}-s}$ lie in consecutive
columns and form a $J_{q_{k}-s}$. Thus, $g_{1},g_{2},\ldots,g_{k-1}$ will form
a $J_{k-1}$ in $\phi_{1}(\pi)$, which is to the left of $b_{k}$ and below
$b_{k-1}$. This contradicts Lemma 3.6. Hence, we have $g_{k}\neq d_{i}$ for
any $i\geq 1$.

  * (4)

If $g_{k-1}=d_{j}$ for some $j\geq 1$, then $g_{k}$ is to the right of $a_{k}$
since $d_{1}$, $d_{2}$, $\ldots,d_{q_{k}-s}$ lie in consecutive columns and
form a $J_{q_{k}-s}$. By repeating the horizontal slide algorithm for $\phi$
and replacing any of $d_{i}^{\prime}s$ that falls in $G$ by $c_{i}^{\prime}s$,
we will get a $J_{k-1}$ in $\pi$ whose rightmost $1$ is $c_{j}$. since
$\mathcal{D}(\pi)=\mathcal{D}(\phi(\pi))$ and $q_{k}\in\mathcal{D}(\pi)$, we
have $q_{k}\in\mathcal{D}(\phi(\pi))$. Thus, this $J_{k-1}$ combining with
$g_{k}$ will form an $H_{k}$ in $\pi$. This contradicts the selection of
$a_{1}$.

Hence, we have concluded that the assertion also holds for $\phi_{1}$, which
completes the proof.

###### Lemma 3.9

Suppose that $H$ is a $Q_{k}$ above $a_{1}$ in $\phi(\pi)$, in which the last
two $1^{\prime}s$ lie in two consecutive columns. Label the squares containing
the $1^{\prime}s$ of $H$ by $h_{1},h_{2},\ldots,h_{k}$, from left to right.
Then the squares $h_{k}$ and $h_{k-1}$ are also filled with $1^{\prime}s$ in
$\pi$.

Proof. Here we only prove the assertion for $\phi_{1}$ and $\phi_{4}$. All the
other cases can be verified by similar arguments. By Lemma 3.6, there is no
$J_{k-1}$ below $b_{k-1}$ and to the left of $b_{k}$ in $\phi_{1}(\pi)$. This
implies that neither $h_{k-1}$ nor $h_{k}$ will be any of $b_{i}^{\prime}s$
for $1\leq i\leq k-2$ in $\phi_{1}(\pi)$ and $\phi_{4}(\pi)$. Moreover,
neither $g_{k-1}$ nor $g_{k}$ will be any of $f_{i}^{\prime}s$ in
$\phi_{4}(\pi)$. Thus, we deduce that the assertion holds for $\phi_{4}$.

In order to prove the assertion for $\phi_{1}$, it remains to show that
neither $h_{k}$ nor $h_{k-1}$ will be any of $b_{k-1}$ and $d_{i}^{\prime}s$
in $\phi_{1}(\pi)$. Since $b_{k},d_{1},d_{2},\ldots,d_{q_{k}-s}$ lie in
consecutive columns and form a $J_{q_{k}-s+1}$ in $\phi_{1}(\pi)$, neither of
$d_{i}^{\prime}s$ can be $h_{k}$. Moreover, neither of $d_{i}^{\prime}s$ can
be $h_{k-1}$ for $1\leq i\leq q_{k}-s-1$. Thus we have $h_{k-1}=d_{q_{k}-s}$,
$h_{k-1}=b_{k-1}$ or $h_{k}=b_{k-1}$.

If $h_{k-1}=d_{q_{k}-s}$, then by applying the horizontal slide algorithm for
$\phi$ repeatedly to $h_{1},h_{2},\ldots,h_{k-2},h_{k}$ and replacing any of
$d_{i}^{\prime}s$ that falls in $h_{1},h_{2},\ldots,h_{k-2},h_{k}$ by
$c_{i}^{\prime}s$, we will get a $J_{k-1}$ above $a_{1}$ in $\pi$. Notice that
the rightmost $1$ of the obtained $J_{k-1}$ is $h_{k}$. This $J_{k-1}$,
combining with $a_{k}$, will form a $Q_{k}$ in $\pi$, which contradicts the
selection of $a_{1}$. If $h_{k}=b_{k-1}$, then $a_{1},a_{2},\ldots,a_{k-2}$,
combining with $h_{k-1}$ and $a_{k-1}$, will form a $Q_{k}$ in $\pi$, which
contradicts the selection of $a_{k-1}$. If $h_{k-1}=b_{k-1}$, then $h_{k}$ is
below $a_{k-1}$ and to the left of $b_{k}$. Then
$h_{1},h_{2},\ldots,h_{k-2},h_{k}$ form a $J_{k-1}$ in $\phi_{1}(\pi)$, which
is to the left of $b_{k}$ and below $b_{k-1}$. This contradicts Lemma 3.6.
Hence, we have proved that the assertion also holds for $\phi_{1}$.

The proof of Lemma 3.7. If not, suppose that $G$ is an $H_{k}$ above $a_{1}$
in $\phi(\pi)$. Label the squares containing $1^{\prime}s$ of $G$ by
$g_{1},g_{2},\ldots,g_{k}$, from left to right. Moreover, let $H$ be a $Q_{k}$
above $a_{1}$ in $\phi(\pi)$ such that the rightmost two $1^{\prime}s$ lie in
two consecutive columns. We label the squares containing the $1^{\prime}s$ of
$H$ by $h_{1},h_{2},\ldots,h_{k}$. According to the definition of $Q_{k}$,
there is a $Q_{k}$ above $a_{1}$ in $\phi(\pi)$ if and only if there exists
such an $H$.

We wish to replace some $1^{\prime}s$ of $G$ (resp. $H$ ) to form an $H_{k}$
(resp. $Q_{k}$) in $\pi$. Here we only consider the case when $G$ (resp. $H$)
is in $\phi_{1}(\pi)$. The other cases can be verified by the similar
arguments. Since the transformation $\phi_{1}$ does not change the positions
of any other $1^{\prime}s$, one of $b_{i}^{\prime}s$ and $d_{i}^{\prime}s$
must fall in $G$ (resp. $H$).

First, replace each $d_{i}$ by $c_{i}$ whenever $d_{i}$ falls in
$g_{1},g_{2},\ldots,g_{k-2}$ (resp. $h_{1},h_{2},\ldots,h_{k-2}$). Then, find
the largest $i$ such that $b_{i}$ falls in $g_{1},g_{2},\ldots,g_{k-2}$ (resp.
$h_{1},h_{2},\ldots,h_{k-2}$). We can apply the vertical slide algorithm
repeatedly to $g_{1},g_{2},\ldots,g_{k-2}$ (resp.
$h_{1},h_{2},\ldots,h_{k-2}$) until the following two cases appear.
(1) There is no $b_{i}$ that falls in $g_{1},g_{2},\ldots,g_{k-2}$ (resp.
$h_{1},h_{2},\ldots,h_{k-2}$) .
(2) There is such a $b_{i}$, but there is no $1$ positioned at the squares
$g_{1},g_{2},\ldots,g_{k-2}$ (resp. $h_{1},h_{2},\ldots,h_{k-2}$) that is to
the left of $b_{i}$ and to the right of $E_{1}$. Since there are at most $i$
$1^{\prime}s$ positioned at $g_{1},g_{2},\ldots,g_{k-2}$ (resp.
$h_{1},h_{2},\ldots,h_{k-2}$) that are not above $b_{i}$ and to the left of
$E_{1}$, we can replace these $1^{\prime}s$ by $a_{1},a_{2},\ldots,a_{i}$.

In both cases, we get a $J_{k-2}$ not below $a_{1}$ in $\pi$. From Lemmas 3.8
and 3.9, the squares $g_{k}$ and $g_{k-1}$ (resp. $h_{k}$ and $h_{k-1}$) are
also filled with $1^{\prime}s$ in $\pi$. Recall that
$\mathcal{D}(\pi)=\mathcal{D}(\phi(\pi))$ and the $1^{\prime}s$ positioned at
$g_{k-1}$ and $g_{k}$ belong to two different blocks of $\phi(\pi)$. This
yields that the $1^{\prime}s$ positioned at $g_{k-1}$ and $g_{k}$ also belong
to two different blocks of $\pi$. Thus, the obtained $J_{k-2}$, combining with
$g_{k-1}$ and $g_{k}$ (resp. $h_{k-1}$ and $h_{k}$) forms an $H_{k}$ (resp.
$Q_{k}$) in $\pi$. In the first case, the obtained $H_{k}$ (resp. $Q_{k}$) is
above $a_{1}$, which contradicts the selection of $a_{1}$. In the second case,
suppose that $g_{z}$(resp. $h_{z}$) is the first square containing a $1$ of
the obtained $H_{k}$ (resp. $Q_{k}$) that is to the right of $a_{i}$. clearly,
$g_{z}$ (resp. $h_{z}$) is above $b_{i}$ and $a_{i+1}$. If $g_{z}$ (resp.
$h_{z}$) is to the left of $a_{i+1}$, then the obtained $H_{k}$ (or $Q_{k}$)
contradicts the selection of $a_{i+1}$. Otherwise,
$a_{2},a_{3},\ldots,a_{i+1}$, combining with the $1^{\prime}s$ of the obtained
$H_{k}$ (resp. $Q_{k}$) that are to the right of $a_{i}$, would form an
$H_{k}$ (or $Q_{k}$ ) in $\pi$. This contradicts the selection of $a_{1}$,
which completes the proof.

###  3.2 The map $\Psi$ from the set $\mathcal{S}_{n}(H_{k},Q_{k})$ to the set
$\mathcal{S}_{n}(F_{k})$

Before we describe the map $\Psi$ we define three transformations, which will
play an essential role in the construction of the map $\Psi$.

Let $\sigma=\\{(\sigma_{1},1),(\sigma_{2},2),\ldots,(\sigma_{n},n)\\}$.
Suppose that $G$ is the submatrix of $\sigma$ at columns
$c_{1}<c_{2}<\ldots<c_{k}<c_{k}+1<c_{k}+2<\ldots<t$ and rows
$r_{1}<r_{2}<\ldots<r_{k-1}>r_{k}<\sigma_{c_{k}+1}<\sigma_{c_{k}+2}<\ldots<\sigma_{t}$,
in which the squares $(r_{i},c_{i})$ are filled with $1^{\prime}s$ for all
$i=1,2,\ldots,k$. Let $\delta(G)$ be the submatrix at the same rows and
columns as $G$, such that the squares $(r_{k},c_{1})$, $(r_{1},c_{2})$,
$\ldots$, $(r_{k-2},c_{k-1})$, $(\sigma_{c_{k}+1},c_{k})$,
$(\sigma_{c_{k}+2},c_{k}+1)$, $\ldots$, $(\sigma_{t},t-1)$, $(r_{k-1},t)$ are
filled with $1^{\prime}s$ and all the other squares are filled with
$0^{\prime}s$.

Suppose that $H$ is the submatrix of $\sigma$ at columns
$c_{1}<c_{2}<\ldots<c_{k-1}<t<t+1<\ldots<c_{k}$ and rows
$r_{1}<r_{2}<\ldots<r_{k-1}>\sigma_{t}>\sigma_{t+1}>\ldots>\sigma_{c_{k}}=r_{k}$,
in which the squares $(r_{i},c_{i})$ are filled with $1^{\prime}s$ for all
$i=1,2,\ldots,k$. Define $\gamma(H)$ to be the submatrix at the same columns
and rows as $H$, such that the squares $(r_{k},c_{1})$, $(r_{1},c_{2})$,
$\ldots$, $(r_{k-2},c_{k-1})$, $(r_{k-1},t)$, $(\sigma_{t},t+1)$,
$(\sigma_{t+1},t+2)$, $\ldots$, $(\sigma_{c_{k}-1},c_{k})$ are filled with
$1^{\prime}s$ and all the other squares are filled with $0^{\prime}s$.

The transformation $\psi$: Suppose that
$\sigma=\sigma_{1}\sigma_{2}\ldots\sigma_{n}$ is a permutation in
$\mathcal{S}_{n}$. First, find the lowest square $(p_{k},q_{k})$ containing a
$1$, such that there is an $F_{k}$ in $\sigma$ in which the $1$ positioned at
$(p_{k},q_{k})$ is its rightmost $1$. Then, find the lowest square
$(p_{k-1},q_{k-1})$ containing a $1$, such that there is an $F_{k}$ in
$\sigma$ in which the $1^{\prime}$ positioned at $(p_{k},q_{k})$ and
$(p_{k-1},q_{k-1})$ are the rightmost two $1^{\prime}s$. Find
$(p_{k-2},q_{k-2}),(p_{k-3},q_{k-3}),\ldots,(p_{1},q_{1})$ one by one as
$(p_{k-1},q_{k-1})$. Assume that there is no $H_{k}$ or $Q_{k}$ above row
$p_{k}$ in $\sigma$.

If $\sigma_{q_{k}-1}>\sigma_{q_{k}+1}$, then we wish to generate a permutation
$\pi$ from $\sigma$ by the considering the following two cases.

  1. Case 1.

$p_{k-1}=\sigma_{q_{k-1}}<\sigma_{q_{k-1}+1}<\ldots<\sigma_{q_{k}-1}>\sigma_{q_{k}}=p_{k}$
and $\sigma_{q_{k}+1}>p_{k-2}$. In this case, let $G$ be the submatrix of
$\sigma$ at columns $q_{1}<q_{2}<\ldots<q_{k-2}<q_{k}$ and rows
$p_{k}<p_{1}<p_{2}<\ldots<p_{k-2}$. Replace $G$ by $\theta^{-1}(G)$ and leave
all the other rows and columns fixed.

  2. Case 2.

Otherwise, find the least $t$ such that $t>q_{k}$ and
$t\in\mathcal{D}(\sigma)$. If such $t$ does not exist, set $t=n$. In this
case, let $G$ be the submatrix of $\sigma$ at columns
$q_{1}<q_{2}<\ldots<q_{k}<q_{k}+1<\ldots<t$ and rows $p_{1}<p_{2}<\ldots
p_{k-1}>p_{k}<\sigma_{q_{k}+1}<\sigma_{q_{k}+2}<\ldots<\sigma_{t}$. Replace
$G$ by $\delta(G)$ the other rows and columns fixed.

If $q_{k}=n$ or $\sigma_{q_{k}-1}<\sigma_{q_{k}+1}$, then we wish to generate
a permutation $\pi$ from $\sigma$ by considering the following two cases.

  1. Case 3.

If there exists an $s$ such that $q_{k-1}<s<q_{k}$ and
$\sigma_{s-1}>\sigma_{s}<\sigma_{s+1}$. Find the largest $t$ such that
$q_{k-1}<t\leq q_{k}$ and $t-1\in\mathcal{A}(\sigma)$. Let $G$ be the
submatrix of $\sigma$ at columns
$q_{1}<q_{2}<\ldots<q_{k-1}<t<t+1<\ldots<q_{k}$ and rows
$p_{1}<p_{2}<\ldots<p_{k-1}>\sigma_{t}>\sigma_{t+1}>\ldots>p_{k}$. Replace $G$
with $\gamma(G)$ and leave all the other rows and columns fixed.

  2. Case 4.

Otherwise, we have
$p_{k-1}=\sigma_{q_{k-1}}<\sigma_{q_{k-1}+1}<\ldots<\sigma_{t-1}>\sigma_{t}>\sigma_{t+1}>\ldots>\sigma_{q_{k}}=p_{k}$
for some $t$ with $q_{k-1}<t\leq q_{k}$. Let $G$ be the submatrix of $\sigma$
at columns $q_{1}<q_{2}<\ldots<q_{k-2}<q_{k-1}<t<t+1<\ldots<q_{k}$ and rows
$p_{1}<p_{2}<\ldots<p_{k-2}<p_{k-1}>\sigma_{t}>\sigma_{t+1}>\ldots>p_{k}$.
Replace $G$ with $\gamma(G)$ and leave all the other rows and columns fixed.

###### Remark 3.10

In Case $2$, the selection of $(p_{k},q_{k})$ ensures that
$p_{k}<\sigma_{q_{k}+1}$. If not, the the $1^{\prime}s$ positioned at
$(p_{1},q_{1}),(p_{2},q_{2}),\ldots,(p_{k-1},q_{k-1}),(\sigma_{q_{k}+1},q_{k}+1)$
would form an $F_{k}$, which contradicts the selection of $(p_{k},q_{k})$. In
Case $3$, the existence of such $s$ and the hypothesis that there is no
$H_{k}$ above row $p_{k}$ ensure that $p_{k-1}>\sigma_{t}$. If not, then the
$1^{\prime}s$ positioned at
$(p_{2},q_{2}),(p_{3},q_{3}),\ldots,(p_{k-1},q_{k-1}),(\sigma_{t},t)$ would
form an $H_{k}$ above row $p_{k}$ in $\sigma$. In Case $4$, the hypothesis
that there is no $Q_{k}$ above row $p_{k}$ ensures that $p_{k-1}>\sigma_{t}$.
If not, then the $1^{\prime}s$ positioned at
$(p_{2},q_{2}),(p_{3},q_{3}),\ldots,(p_{k-1},q_{k-1}),(\sigma_{t-1},t-1),(\sigma_{t},t)$
would form a $Q_{k}$ above row $p_{k}$ in $\sigma$.

###### Remark 3.11

We denote the resulting permutation in Case $1$, Case $2$, Case $3$ and Case
$4$ by $\psi_{1}(\sigma)$, $\psi_{2}(\sigma)$, $\psi_{3}(\sigma)$ and
$\psi_{4}(\sigma)$, respectively.

It is obvious that the transformation $\psi$ changes every occurrence of
$F_{k}$ to an occurrence of $H_{k}$ (or $Q_{k}$). Denote by $\Psi$ the
iterated transformation, that recursively transforms every occurrence of
$F_{k}$ into $H_{k}$ (or $Q_{k}$).

Using the notation of the algorithm for $\psi_{1}$, we label the squares
containing $1^{\prime}s$ in $G$ by $b_{1},b_{2},\ldots,b_{k}$, and the squares
containing $1^{\prime}s$ in $\theta^{-1}(G)$ by
$a_{1},a_{2},\ldots,a_{k-1},a_{k}$, from left to right, see Figure 4 for
example.

Using the notation of the algorithm for $\psi_{2}$, we label the squares
containing $1^{\prime}s$ in $G$ by
$b_{1},b_{2},\ldots,b_{k-1},b_{k},d_{1},d_{2},\ldots,d_{t-q_{k}}$, and the
squares containing $1^{\prime}s$ in $\delta(G)$ by
$a_{1},a_{2},\ldots,a_{k-1},c_{1},c_{2},\ldots,c_{t-q_{k}},a_{k}$, from left
to right, see Figure 2 for example.

Using the notation of the algorithm for $\psi_{3}$, we label the squares
containing $1^{\prime}s$ in $G$ by
$b_{1},b_{2},\ldots,b_{k-1},f_{1},f_{2},\ldots,f_{q_{k}-t},b_{k}$, and the
squares containing $1^{\prime}s$ in $\gamma(G)$ by
$a_{1},a_{2},\ldots,a_{k-1},a_{k},e_{1},e_{2},\ldots,e_{q_{k}-t}$, from left
to right. We also label the minimum entry of the block to which $f_{1}$
belongs by $c_{1}$, see Figure 3 for example.

Using the notation of the algorithm for $\psi_{4}$, we label the squares
containing $1^{\prime}s$ in $G$ by
$b_{1},b_{2},\ldots,b_{k-1},f_{1},f_{2},\ldots,f_{q_{k}-t},b_{k}$, and the
squares containing $1^{\prime}s$ in $\gamma(G)$ by
$a_{1},a_{2},\ldots,a_{k-1},a_{k},e_{1},e_{2},\ldots,e_{q_{k}-t}$, from left
to right, see Figure 5 for example.

In $\psi_{2}(\sigma)$ and $\psi_{3}(\sigma)$, let $E_{1}$ be the same board
defined in $\phi_{1}(\pi)$ and $\phi_{2}(\pi)$. Similarly, in
$\psi_{1}(\sigma)$ and $\psi_{4}(\sigma)$, let $E_{2}$ be the same board
defined in $\phi_{3}(\pi)$ and $\phi_{4}(\pi)$. From the selection of
$b_{i}^{\prime}s$ and the hypothesis that there is no $H_{k}$ above $a_{1}$,
it follows that there are no $1^{\prime}s$ inside $E_{1}$ (or $E_{2}$). In
other words, all the $1^{\prime}s$ are to the left or to the right of $E_{1}$
(or $E_{2}$) in $\psi(\pi)$.

Now we proceed to prove that the transformation $\psi$ have the following
properties, which are essential in the proof of Theorem 1.5.

###### Lemma 3.12

If there is no $H_{k}$ or $Q_{k}$ above $a_{1}$ in $\sigma$, then we have
$\mathcal{D}(\sigma)=\mathcal{D}(\psi(\sigma))$.

Proof. Since there are no $1^{\prime}s$ inside $E_{1}$ (or $E_{2}$) and no
$H_{k}$ or $Q_{k}$ above $a_{1}$, one can easily verify that
$\mathcal{D}(\pi)=\mathcal{D}(\psi(\sigma))$. The details are omitted here.

Properties

  * ($1^{\prime}$)

For any $1\leq i<j\leq k-1$, the rectangle with corners $a_{i}$ and $a_{j}$
cannot contain a $J_{j-i}$ with all its $1^{\prime}s$ strictly to the right of
$E_{1}$ (or $E_{2}$) in $\psi(\sigma)$.

  * ($2^{\prime}$)

For any $1\leq i\leq k-2$, the rectangle with corners $a_{i}$ and $a_{k}$
cannot contain a $J_{k-i-1}$ with all its $1^{\prime}s$ strictly to the right
of $E_{2}$ in $\psi_{1}(\sigma)$ (or $\psi_{4}(\sigma)$).

Proof.

  * $(1^{\prime})$

If there is a $J_{j-i}$ in this region, then $b_{1},b_{2},\ldots,b_{i-1}$,
combining with this $J_{j-i}$ and $b_{j},b_{j+1},b_{j+2},\ldots,b_{k}$, will
form an $F_{k}$ in $\sigma$, which contradicts the selection of $b_{j-1}$.

  * $(2^{\prime})$

If there is a $J_{k-1-i}$ in this region, then the rightmost $1$ of this
$J_{k-1-i}$ is to the left of $b_{k-1}$ since all the $1^{\prime}s$ lying
between $b_{k-1}$ and $a_{k}$ are to the left of $E_{2}$. Clearly, the
rightmost $1$ of this $J_{k-1-i}$ is below $b_{k-2}$. So
$b_{1},b_{2},\ldots,b_{i-1}$, combining with this $J_{k-1-i}$ and
$b_{k-1},b_{k}$, will form an $F_{k}$ in $\sigma$, which contradicts the
selection of $b_{k-2}$.

###### Lemma 3.13

$\psi(\sigma)$ contains no $F_{k}$ with at least one square in a row below
$a_{1}$.

Proof. If not, suppose $H$ is such an $F_{k}$ in $\psi(\sigma)$. Label the
squares containing the $1^{\prime}s$ of $H$ by $h_{1},h_{2},\ldots,h_{k}$ from
left to right. Then $h_{k}$ is below $a_{1}$. As in the proof of Lemma 3.5, we
shall replace some $1^{\prime}s$ of $H$ (except $h_{k}$) to form an $F_{k}$ in
$\pi$, which contradicts the selection of $b_{k}$.

By the selection of $b_{k}$, we have that $h_{k}$ must be at the left side of
$b_{k-1}$. From the construction of $\psi(\sigma)$, at least one of
$a_{1},a_{2},\ldots,a_{k-2}$ must fall in $H$. Otherwise, $H$ is also an
$F_{k}$ in $\sigma$, which contradicts the selection of $b_{k}$.

Find the least $i$ such that $a_{i}$ falls in $H$.

Vertical slide algorithm for $\psi$: If there is a $1$ of $H$ which is above
$a_{i}$ and to the left of $E$, find the leftmost square containing such a $1$
and denote it by $h_{y}$. find $x$ such that $h_{y}$ is to the right of
$a_{x}$ and to the left of $a_{x+1}$. Then by property ($1^{\prime}$), there
are at most $x+1-i$ $1^{\prime}s$ in $H$ that are below $a_{x+1}$ but not
below $a_{i}$, and to the right of $E_{1}$ (or $E_{2}$). So we can replace
these $1^{\prime}s$ by $a_{i},a_{i+1},\ldots,a_{x}$, and hence by those
positioned at $b_{i},b_{i+1},\ldots,b_{x}$.

We can repeat the vertical slide algorithm until one of the following two
cases appears.

  * (1)

There is no $a_{i}$ that falls in $H$. This ends the proof.

  * (2)

There is such an $a_{i}$, but $h_{y}$ does not exist. Then suppose $a_{v}$ is
the first square to the right of $h_{k}$. By property ($1^{\prime}$) , there
are at most $v-i$ $1^{\prime}s$ in $H$ that are below and to the left of
$a_{v}$, but not below $a_{i}$, and to the right of $E_{1}$ (or $E_{2}$). So
we can replace these $1^{\prime}s$ by $a_{i},a_{i+1},\ldots,a_{v-1}$, and
hence by $b_{i},b_{i+1},\ldots,b_{v-1}$. Then we have an $F_{k}$ in $\sigma$
with a square $h_{k}$ below $a_{1}$.

###### Lemma 3.14

If $\sigma$ contains no $H_{k}$ or $Q_{k}$ that is above $a_{1}$, neither does
$\psi(\sigma)$.

In order to prove Lemma 3.14, we need the following two lemmas.

###### Lemma 3.15

Suppose that $G$ is an $H_{k}$ above $a_{1}$ in $\psi(\sigma)$. Label the
squares containing the $1^{\prime}s$ of $G$ by $g_{1},g_{2},\ldots,g_{k}$,
from left to right. If $\sigma$ contains no $H_{k}$ or $Q_{k}$ that is above
$a_{1}$, then the squares $g_{k}$ and $g_{k-1}$ are also filled with
$1^{\prime}s$ in $\sigma$.

###### Lemma 3.16

Suppose that $H$ is a $Q_{k}$ above $a_{1}$ in $\psi(\sigma)$, in which the
last two $1^{\prime}s$ lie in two consecutive columns. Label the squares
containing the $1^{\prime}s$ of $H$ by $h_{1},h_{2},\ldots,h_{k}$, from left
to right. If $\sigma$ contains no $H_{k}$ or $Q_{k}$ that is above $a_{1}$,
then the squares $h_{k}$ and $h_{k-1}$ are also filled with $1^{\prime}s$ in
$\sigma$.

Before we prove Lemmas 3.15 and 3.16, we introduce the following horizontal
slide algorithm  for $\psi$.

Suppose $H$ is a $J_{k}$ in $\psi(\sigma)$. Label the squares containing the
$1^{\prime}s$ of $H$ by $h_{1},h_{2},\ldots,h_{k}$ from left to right.

Horizontal slide algorithm for $\psi_{2}$ (or $\psi_{3}$): Find the largest
$i$ such that $a_{i}$ falls in $H$ with $i\leq k-1$. If there is a $1$ of $H$
which is below $a_{i}$ to the left of $E_{1}$, find the rightmost squares
containing such a $1$ and denote it by $h_{y}$. Find $x$ such that $h_{y}$ is
below $a_{x}$, and above $a_{x-1}$. Then by property $(1^{\prime})$, there are
$i-x+1$ $1^{\prime}s$ in $H$ that are above $a_{x-1}$ but not above $a_{i}$,
and to the right of $E_{1}$. So we can replace these $1^{\prime}s$ by
$a_{x},a_{x+1},\ldots,a_{i}$, and hence by $b_{x-1},b_{x},\ldots,b_{i-1}$.

We can repeat this horizontal slide algorithm until one of the following two
cases appears.

  1. (1)

There is no $a_{i}$ that falls in $H$.

  2. (2)

There is such an $a_{i}$, but $h_{y}$ does not exist. Find $x$ such that
$h_{1}$ is below $a_{x+1}$ and above $a_{x}$. Then by property $(1^{\prime})$,
there are $i-x$ $1^{\prime}s$ in $H$ that are above $a_{x}$ but not above
$a_{i}$. So we can replace these $1^{\prime}s$ by
$a_{x+1},a_{x+2},\ldots,a_{i}$, and hence by $b_{x},b_{x+1},\ldots,b_{i-1}$.

Horizontal slide algorithm for $\psi_{1}$ (or $\psi_{4}$). Find the largest
$i$ such that $a_{i}$ falls in $H$ with $i\leq k-2$ or $i=k$. If there is a
$1$ of $H$ which is below $a_{i}$ to the left of $E_{2}$, find the rightmost
square containing such a $1$ and denote it by $h_{y}$. Find $x$ such that
$h_{y}$ is below $a_{x}$, and above $a_{x-1}$. If $i\leq k-2$, then by
property $(1^{\prime})$, there are $i-x+1$ $1^{\prime}s$ in $H$ that are above
$a_{x-1}$ but not above $a_{i}$, and to the right of $E_{2}$. So we can
replace these $1^{\prime}s$ by those positioned at
$a_{x},a_{x+1},\ldots,a_{i}$, and hence by $b_{x-1},b_{x},\ldots,b_{i-1}$. If
$i=k$, then by property $(2^{\prime})$, there are $k-x$ $1^{\prime}s$ in $H$
that are above $a_{x-1}$ but not above $a_{k}$, and to the right of $E_{2}$.
So we can replace these $1^{\prime}s$ by $a_{x},a_{x+1},\ldots,a_{k-2},a_{k}$,
and hence by $b_{x-1},b_{x},\ldots,b_{k-2}$.

We can repeat this horizontal slide algorithm until one of the following two
cases appears.

  1. (1)

There is no $a_{i}$ that falls in $H$.

  2. (2)

There is such an $a_{i}$, but $h_{y}$ does not exist. Find $x$ such that
$h_{1}$ is below $a_{x+1}$ and above $a_{x}$. If $i<k-2$, then by property
$(1^{\prime})$, there are $i-x$ $1^{\prime}s$ in $H$ that are above $a_{x}$
but not above $a_{i}$. So we can replace these $1^{\prime}s$ by
$a_{x+1},a_{x+2},\ldots,a_{i}$, and hence by $b_{x},b_{x+1},\ldots,b_{i-1}$.
If $i=k$, then by property $(2^{\prime})$, there are $k-1-x$ $1^{\prime}s$ in
$H$ that are above $a_{x}$ but not above $a_{k}$. So we can replace these
$1^{\prime}s$ by $a_{x+1},a_{x+2},\ldots,a_{k-2},a_{k}$, and hence by
$b_{x},b_{x+1},\ldots,b_{k-2}$.

The proof of Lemma 3.15. Here we only prove the assertion for
$\psi_{2}(\sigma)$ and $\psi_{4}(\sigma)$. The other cases can be verified by
similar arguments. In order to prove the assertion, it suffices to show that
neither $g_{k}$ nor $g_{k-1}$ will be any of the $a_{i}^{\prime}s$ and
$c_{i}^{\prime}s$ in $\psi_{2}(\sigma)$, and be any of the $a_{i}^{\prime}s$
for $i=1,2,\ldots,k-2,k$ and $e_{i}^{\prime}s$ in $\psi_{4}(\sigma)$.

We claim there is no $J_{k-1}$ which is below $b_{k-1}$ but above $a_{1}$, and
not to the right of $b_{k}$ in $\psi_{2}(\sigma)$ (or $\psi_{4}(\sigma)$). If
not, suppose that $R$ is such a $J_{k-1}$. When $J_{k-1}$ is in $\psi_{2}(G)$,
we can get a $J_{k-1}$ from $R$ by repeating the horizontal slide algorithm
for $\psi_{2}$. When $J_{k-1}$ is in $\psi_{4}(G)$, we can get a $J_{k-1}$
from $R$ by repeating the horizontal slide algorithm for $\psi_{4}$ and
replacing any $e_{i}$ by $f_{i}$ whenever $e_{i}$ fall in $R$. In both cases,
the obtained $J_{k-1}$ is below $b_{k-1}$ but above $a_{1}$, and to the left
of $b_{k}$. Then Then this $J_{k-1}$ combining with $b_{k}$ will form an
$F_{k}$ in $\sigma$, which contradicts the selection of $b_{k-1}$. Hence, the
claim is proved.

From the claim, it follows that neither $g_{k}$ nor $g_{k-1}$ will be any of
the $a_{i}^{\prime}s$ in $\psi_{2}(\sigma)$ for $i\leq k-1$. In order to prove
the assertion for $\psi_{2}(\sigma)$, it remains to show that neither $g_{k}$
or $g_{k-1}$ will be any of $a_{k}$ and $c_{i}^{\prime}s$ in
$\psi_{2}(\sigma)$. Clearly, $g_{k-1}$ cannot be $a_{k}$ since there is no
$1^{\prime}s$ above and to the right of $a_{k}$.

  * (1)

If $g_{k}$ is either $a_{k}$ or one of $c_{i}^{\prime}s$ in
$\psi_{2}(\sigma)$, then $g_{1},g_{2},\ldots,g_{k-1}$ form a $J_{k-1}$ which
is to the left of $b_{k}$ and below $b_{k-1}$ in $\phi_{2}(\sigma)$ since
$c_{1},c_{2},\ldots,c_{t-q_{k}},a_{k}$ lie in consecutive columns and form a
$J_{t-q_{k}+1}$. This contradicts the claim proved above.

  * (2)

If $g_{k-1}$ is one of $c_{i}^{\prime}s$ in $\psi_{2}(\sigma)$, then $g_{k}$
is to the right of $a_{k}$ since $c_{1},c_{2},\ldots,c_{t-q_{k}},$ $a_{k}$ lie
in consecutive columns and form a $J_{t-q_{k}+1}$. By repeating the horizontal
slide algorithm for $\psi_{2}$ and replacing any $c_{i}$ falling in $G$ by
$d_{i}$, we can get a $J_{k}$ above $a_{1}$ in $\sigma$ from $G$. Notice that
if $g_{k-1}=c_{j}$, then the rightmost two $1^{\prime}s$ of the obtained
$J_{k}$ are $g_{k}$ and $d_{j}$. Recall that $a_{k}$ is positioned at column
$t$. Since $\mathcal{D}(\sigma)=\mathcal{D}(\psi(\sigma))$ and
$t\in\mathcal{D}(\sigma)$, we have $t\in\mathcal{D}(\psi(\sigma))$. Thus, the
obtained $J_{k}$ is an $H_{k}$. This contradicts the fact that there contains
no $H_{k}$ above $a_{1}$ in $\sigma$.

Hence, we have concluded that the assertion holds for $\psi_{2}(\sigma)$.

From the claim that is no $J_{k-1}$ which is below $b_{k-1}$ but above
$a_{1}$, and not to the right of $b_{k}$ in $\psi_{4}(\sigma)$, it follows
that neither $g_{k}$ nor $g_{k-1}$ will be any of the $a_{i}^{\prime}s$ for
$i=1,2,\ldots,k-2,k$ and $e_{i}^{\prime}s$ in $\psi_{1}(\sigma)$. Hence, we
deduce that the assertion also holds for $\psi_{4}(\sigma)$, which completes
the proof.

The proof of Lemma 3.16. Here we only prove the assertion for
$\psi_{2}(\sigma)$ and $\psi_{4}(\sigma)$. The other cases can be verified by
similar arguments. In order to prove the assertion, it suffices to show that
neither $h_{k}$ nor $h_{k-1}$ will be any of the $a_{i}^{\prime}s$ and
$c_{i}^{\prime}s$ in $\psi_{2}(\sigma)$, and be any of the $a_{i}^{\prime}s$
for $i=1,2,\ldots,k-2,k$ and $e_{i}^{\prime}s$ in $\psi_{4}(\sigma)$.

Recall that we have proved the claim in the proof of Lemma 3.15 that there is
no $J_{k-1}$ which is below $b_{k-1}$ but above $a_{1}$, and not to the right
of $b_{k}$ in $\psi_{4}(\sigma)$. It follows that neither $h_{k}$ nor
$h_{k-1}$ will be any of the $a_{i}^{\prime}s$ for $i=1,2,\ldots,k-2,k$ and
$e_{i}^{\prime}s$ in $\psi_{4}(\sigma)$. Thus, the assertion holds for
$\psi_{4}(\sigma)$.

Similarly, from the claim proved in the proof of Lemma 3.15, it follows that
neither $h_{k}$ nor $h_{k-1}$ will be any of the $a_{i}^{\prime}s$ for
$i=1,2,\ldots,k-1$ in $\psi_{2}(\sigma)$. In order to prove the assertion for
$\psi_{2}(\sigma)$, it remains to verify that neither $h_{k}$ nor $h_{k-1}$
will be any of $a_{k}$ and $c_{i}^{\prime}s$ in $\psi_{2}(\sigma)$. Recall
that $c_{1},c_{2},\ldots,c_{q_{k}-t},a_{k}$ lie in consecutive columns and
form a $J_{q_{k}-t+1}$ in $\psi_{1}(\sigma)$. It implies that if $h_{k}$ or
$h_{k-1}$ is one of $c_{1},c_{2},\ldots,c_{q_{k}-t},a_{k}$, then we have
either $h_{k-1}=a_{k}$ or $h_{k}=c_{1}$.

In the former case, we can get a $J_{k-1}$ above $a_{1}$ in $\sigma$ from the
$J_{k-1}$ consisting of $h_{1},h_{2},\ldots,h_{k-2},h_{k}$, by repeating the
horizontal slide algorithm for $\psi_{2}$ and replacing any $c_{i}$ by
$d_{i}$. Since $\mathcal{D}(\sigma)=\mathcal{D}(\psi_{1}(\sigma))$ and $a_{k}$
is above $h_{k}$, we have that $d_{t-q_{k}}$ is above $h_{k}$. Notice that the
rightmost $1$ of the obtained $J_{k-1}$ is $h_{k}$. Thus, this $J_{k-1}$,
combining with $d_{t-q_{k}}$, will form a $Q_{k}$ above $a_{1}$ in $\sigma$,
which contradicts the hypothesis that $\sigma$ contains no $Q_{k}$ above
$a_{1}$.

In the latter case, $h_{k-2}$ is not above $a_{k-1}$ since $c_{1}$ is below
$a_{k}$ (and $b_{k-1}$) and there is no $1^{\prime}s$ inside $E_{1}$. If
$h_{k-2}$ is to the left of $a_{k-1}$ (and $b_{k-1}$), then by repeating the
horizontal slide algorithm, we can obtain a $J_{k-2}$ above $a_{1}$ in
$\sigma$ from the $J_{k-2}$ consisting of $h_{1},h_{2},\ldots,h_{k-2}$. Notice
that the rightmost $1$ of the resulting $J_{k-2}$ is below $b_{k-2}$ and to
the left of $b_{k-1}$. Then, this $J_{k-2}$, combining with $b_{k-1}$ and
$b_{k}$, will form an $F_{k}$ in $\sigma$. This contradicts the selection of
$b_{k-2}$.

Now suppose that $h_{k-2}$ is either equal to $a_{k-1}$ or is at the right of
$a_{k-1}$ (and $b_{k-1}$), then by the claim obtained in the proof of Lemma
3.15, $h_{k-1}$ is above $b_{k-1}$ and to the left of $E_{1}$. If $h_{k-2}\neq
a_{k-1}$, then $b_{1},b_{2},\ldots,b_{k-1},h_{k-1}$ form an $H_{k}$ above
$a_{1}$ in $\sigma$, which contradicts the hypothesis. If $h_{k-2}=a_{k-1}$,
then we have $c_{1}$ is above $b_{k-2}$ (and $a_{k-1}$). Thus, according to
the definition of $\psi_{2}$, there must exists $s$ such that
$s\in\mathcal{D}(\sigma)$ and $q_{k-1}\leq s<q_{k}-1$. Recall that $c_{1}$ and
$h_{k-1}$ lie in columns $q_{k}$ and $q_{k-1}$, respectively. From the
equality $\mathcal{D}(\sigma)=\mathcal{D}(\psi(\sigma))$, it follows that
$b_{1},b_{2},\ldots,b_{k-1},h_{k-1}$ form an $H_{k}$ above $a_{1}$ in
$\sigma$, which contradicts the hypothesis. Hence, we have concluded that the
assertion also holds for $\psi_{2}(\sigma)$.

The proof of Lemma 3.14. If not, suppose that $G$ is an $H_{k}$ above $a_{1}$
in $\psi(\sigma)$. Label the $1^{\prime}s$ in $G$ by
$g_{1},g_{2},\ldots,g_{k}$, from left to right. Moreover, let $H$ be a $Q_{k}$
above $a_{1}$ in $\psi(\sigma)$ such that the rightmost two $1^{\prime}s$ lie
in two consecutive columns. We label its $1^{\prime}s$ in $H$ by
$h_{1},h_{2},\ldots,h_{k}$. According to the definition of $Q_{k}$, there is a
$Q_{k}$ above $a_{1}$ in $\psi(\sigma)$ if and only if there exists such an
$H$.

We wish to replace some $1^{\prime}s$ of $G$ (resp. $H$ ) to form an $H_{k}$
(resp. $Q_{k}$) above $a_{1}$ in $\sigma$, which contradicts the hypothesis
that there is no $H_{k}$ (resp. $Q_{k}$) above $a_{1}$ in $\sigma$. Here we
only consider the case when $G$ (resp. $H$) is in $\psi_{2}(\sigma)$. The
other cases can be verified by the similar arguments. Since the map $\psi_{2}$
does not change the positions of any other $1^{\prime}s$, one of
$a_{i}^{\prime}s$ and $c_{i}^{\prime}s$ must fall in $G$ (resp. $H$).

We can get a $J_{k-2}$ above $a_{1}$ in $\sigma$ from the $J_{k-2}$ consisting
of $g_{1},g_{2},\ldots,g_{k-2}$ (resp, $h_{1},h_{2},\ldots,h_{k-2}$), by
repeating the horizontal slide algorithm and replacing each $c_{j}$ by $d_{j}$
whenever $c_{j}$ falls in $G$ (resp. $H$). From Lemmas 3.15 and 3.16, it
follows that the squares $g_{k}$ and $g_{k-1}$ (resp. $h_{k}$ and $h_{k-1}$)
are also filled with $1^{\prime}s$ in $\sigma$. Hence, the obtained $J_{k-2}$
combining with $g_{k}$ and $g_{k-1}$ (resp. $h_{k}$ and $h_{k-1}$) will form a
$J_{k}$ (resp, $G_{k}$) in $\sigma$. Since $h_{k-1}$ and $h_{k}$ lie in two
consecutive columns, the obtained $G_{k}$ is a $Q_{k}$. Recall that
$\mathcal{D}(\pi)=\mathcal{D}(\psi(\sigma))$ and the $1^{\prime}s$ positioned
at $g_{k-1}$ and $g_{k}$ belong to two different blocks of $\psi(\sigma)$.
This yields that the $1^{\prime}s$ positioned at $g_{k-1}$ and $g_{k}$ also
belong to two different blocks of $\pi$. Thus, the obtained $J_{k}$ is an
$H_{k}$. This completes the proof.

###### Lemma 3.17

If $\sigma$ contains no $H_{k}$ or $Q_{k}$ that is above $a_{1}$, then

  * (1)

there exists no $1$ that is above and to the left of $a_{k}$ such that this
$1$, combining with $a_{1},a_{2},\ldots,a_{k-1}$, forms an $H_{k}$ in
$\psi(\sigma)$;

  * (2)

there exists no $1$ that is to the left of $a_{k}$ in $\psi_{1}(\sigma)$ (or
$\psi_{4}(\sigma)$), such that this $1$, combining with
$a_{1},a_{2},\ldots,a_{k-1}$, forms a $Q_{k}$ in $\psi_{1}(\sigma)$ ( or
$\psi_{4}(\sigma)$);

  * (3)

for $1\leq t\leq k-2$, the board that is above and to the right of $a_{t}$
cannot contain an $H_{k-t}$ or $Q_{k-t}$ in $\psi(\sigma)$ such that the
lowest $1$ of this $H_{k-t}$ or $Q_{k-t}$ is to the left of $a_{t+1}$, and
this $H_{k-t}$ or $Q_{k-t}$ , combining with $a_{1},a_{2},\ldots,a_{t}$, forms
an $H_{k}$ or $Q_{k}$ in $\psi(\sigma)$.

Proof. (1) If there is such a $1$, then this $1$, combining with
$b_{1},b_{2},\ldots,b_{k-1}$, forms an $H_{k}$ in $\sigma$ since
$\mathcal{D}(\sigma)=\mathcal{D}(\psi(\sigma))$. This contradicts the
hypothesis that there is no $H_{k}$ above $a_{1}$ in $\sigma$.

(2) The result follows immediately from the fact that there is no
$1^{\prime}s$ below and to the right of $b_{k-1}$ (and $a_{k-1}$), and the
left of $a_{k}$.

(3) If not, suppose that $G$ is such an $H_{k-t}$ (or $Q_{k-t}$) in $\psi(T)$.
Label its $1^{\prime}s$ by $g_{t+1},g_{t+2},\ldots,g_{k}$, from left to right.
By hypothesis, $g_{t+1}$ is to the left of $a_{t+1}$. By the same reasoning as
in the proof of Lemmas 3.15 and 3.16, one can verify that both the squares
$g_{k}$ and $g_{k-1}$ are also filled with $1^{\prime}s$ in $\sigma$. This
ensures that by repeating the horizontal slide algorithm and replacing each
$c_{j}$ (resp. $e_{j}$) by $d_{j}$ (resp. $f_{j}$) in $\psi_{2}(\sigma)$
(resp. $\psi_{3}(\pi)$ and $\psi_{4}(\pi)$), we can get an $H_{k-t}$ (or
$Q_{k-t}$) in $\sigma$, in which $g_{t+1}$ is leftmost $1$. This $H_{k-t}$ (or
$Q_{k-t}$), combining with $b_{1},b_{2},\ldots,b_{t}$, forms an $H_{k}$ (or
$Q_{k}$) in $\sigma$, which is above $a_{1}$. This contradicts the hypothesis
that there is no $H_{k}$ or $Q_{k}$ above $a_{1}$. This completes the proof.

The proof of Theorem 1.5.  First, we aim to show that the map $\Phi$ is well
defined, that is, after finitely many iterations of $\phi$, there will be no
occurrences of $H_{k}$ or $Q_{k}$. Suppose that we start with some
$\tau\in\mathcal{S}_{n}(F_{k})$. At the $t$th application of $\phi$ we select
a copy of $H_{k}$ (or $Q_{k}$) in $\phi^{t-1}(\tau)$. This has its lowest $1$
in some row $r$. By Lemma 3.7, the $H_{k}$ (or $Q_{k}$) we will select in
$\phi^{t}(\tau)$ cannot have its lowest $1$ anywhere above row $r$. If it is
in row $r$, then we know it is further to the right than at the previous
iteration, because there is only one $1$ in that row, and we have just moved
it to the right,from $a_{1}$ to $b_{k}$. It follows that each iteration the
selection of $a_{1}$ can only go down or slide right, and therefore the map
$\Phi$ is well defined.

Next we aim to show that $\mathcal{D}(\tau)=\mathcal{D}(\Phi(\tau))$. We prove
by induction on $t$. Suppose that for any $j<t$, we have
$\mathcal{D}(\phi^{j-1}(\tau))=\mathcal{D}(\phi^{j}(\tau))$. We wish to show
that $\mathcal{D}(\phi^{t-1}(\tau))=\mathcal{D}(\phi^{t}(\tau))$. At the $t$th
application of $\phi$ we select a copy of $H_{k}$ (or $Q_{k}$) in
$\phi^{t-1}(\tau)$. This has its lowest $1$ in some row $a_{1}$. Recall that
we have shown that each iteration the selection of lowest square of the
selected $H_{k}$ (or $Q_{k}$) can only go down or slide right. By Lemma 3.5,
there is no $F_{k}$ with at least one square below $a_{1}$ in
$\phi^{t-1}(\tau)$. From Lemma 3.4, it follow that
$\mathcal{D}(\phi^{t-1}(\tau))=\mathcal{D}(\phi^{t}(\tau))$.

Now we proceed to show that the map $\Psi$ is the inverse of the map $\Phi$.
To this end, it suffices to show that $\psi(\phi^{t}(\tau))=\phi^{t-1}(\tau)$.
For our convenience, let $\pi=\phi^{t-1}(\tau)$ and $\sigma=\phi^{t}(\tau)$.
Suppose that at the $t$th application of $\phi$ we select a copy of $H_{k}$
(or $Q_{k}$) in $\pi$, in which the $1^{\prime}s$ are positioned in the
squares $(p_{1},q_{1}),(p_{2},q_{2}),\ldots,(p_{k},q_{k})$, from left to
right. We have four cases.

Case 1. The selected $1^{\prime}s$ form a copy of $H_{k}$, and
$\pi_{q_{k}-1}>\pi_{q_{k}+1}$ or $q_{k}=n$. In this case, find the largest $s$
such that $q_{k-1}<s<q_{k}$ and $s-1\in\mathcal{D}(\pi)$. By the construction
of the transformation $\phi$, the squares $(p_{2},q_{1})(p_{3},q_{2}),\ldots,$
$(p_{k},q_{k-1}),(p_{1},s),(\pi_{s},s+1),\ldots,(\pi_{q_{k}-1},q_{k})$ are
filled with $1^{\prime}s$ in $\sigma$, and all the other rows and columns are
the same as $\pi$. Note that the $1^{\prime}s$ positioned at the squares
$(p_{2},q_{1})(p_{3},q_{2}),\ldots,$ $(p_{k},q_{k-1}),(p_{1},s)$ form an
$F_{k}$ in $\sigma$. Lemmas 3.5 and 3.6 ensure that when we apply the map
$\psi$ to $\sigma$, the squares we selected are just
$(p_{2},q_{1})(p_{3},q_{2}),\ldots,$ $(p_{k},q_{k-1}),(p_{1},s)$. By Lemma
3.7, there is no $H_{k}$ or $Q_{k}$ above row $p_{1}$. This implies that
$\psi(\sigma)$ is well defined. Suppose that
$\sigma=\\{(\sigma_{1},1),(\sigma_{2},2),\ldots,(\sigma_{n},n)\\}$. Clearly,
we have $\sigma_{q_{i}}=p_{i+1}$ for $i=1,2,\ldots,k-1$, $\sigma_{s}=p_{1}$
and $\sigma_{j}=\pi_{j-1}$ for $j=s+1,s+2,\ldots,q_{k}$.

We claim that $\sigma_{s-1}>\sigma_{s+1}$. If $s-1\neq q_{k-1}$, then we have
$\sigma_{s-1}=\pi_{s-1}$. Since $s-1\in\mathcal{D}(\pi)$, we have
$\pi_{s-1}>\pi_{s}$. In this case, we have
$\sigma_{s-1}=\pi_{s-1}>\pi_{s}=\sigma_{s+1}$. If $s-1=q_{k-1}$, then we have
$\sigma_{s-1}=p_{k}$. Recall that we have $\pi_{s}<\pi_{s+1}<\ldots<p_{k}$.
This implies that $\sigma_{s-1}=p_{k}>\pi_{s}=\sigma_{s+1}$. Hence, we have
concluded that $\sigma_{s-1}>\sigma_{s+1}$.

We claim that if
$\sigma_{q_{k-1}}<\sigma_{q_{k-1}+1}<\ldots<\sigma_{s-1}>\sigma_{s}$, then we
have $\sigma_{q_{k-2}}>\sigma_{s+1}$. If not, since
$\sigma_{q_{k-2}}=p_{k-1}=\pi_{q_{k-1}}$ and $s-1\in\mathcal{D}(\pi)$, we have
$s-1\neq q_{k-1}$. Then the $1^{\prime}s$ positioned at the squares
$(p_{2},q_{2}),(p_{3},q_{3}),\ldots,(p_{k-1},q_{k-1}),(\pi_{s-1},s-1),(\pi_{s},s)$
will form a $Q_{k}$ above row $p_{1}$ in $\pi$, which contradicts the
selection of $(p_{1},q_{1})$. Hence the claim is proved.

Then, according to the definition of map $\psi$, we have
$\psi(\sigma)=\psi_{2}(\sigma)$. Since we have
$\mathcal{D}(\pi)=\mathcal{D}(\sigma)$ and $\pi_{s}<\pi_{s+1}<\ldots<p_{k}$,
we have $\sigma_{s}<\sigma_{s+1}<\ldots<\sigma_{q_{k}}$. Recall that there are
no $1^{\prime}s$ inside $E_{1}$, we have either $q_{k}=n$ or
$q_{k}\in\mathcal{D}(\pi)$. This yields that we have either $q_{k}=n$ or
$q_{k}\in\mathcal{D}(\phi(\pi))$ Hence, when we apply the the map $\psi_{2}$
to $\sigma$, $q_{k}$ is the largest integer $m$ such that $m>s$ and
$m\in\mathcal{D}(\sigma)$ or $m=n$. Thus, it is easily seen that
$\psi_{2}(\sigma)=\pi$, that is, $\psi(\phi^{t}(\tau))=\phi^{t-1}(\tau)$.

Case 2. The selected $1^{\prime}s$ form a copy of $H_{k}$ and
$\pi_{q_{k}-1}<\pi_{q_{k}+1}$. In this case, find the least $t$ such that
$t>q_{k}$ and $t\in\mathcal{A}(\pi)$ or $t=n$. By the construction of the map
$\phi$, the squares $(p_{2},q_{1})(p_{3},q_{2}),\ldots,$
$(p_{k},q_{k-1}),(\pi_{q_{k}+1},q_{k}),(\pi_{q_{k}+2},q_{k}+1),\ldots,(\pi_{t},t-1)(p_{1},t)$
are filled with $1^{\prime}s$ in $\sigma$, and all the other rows and columns
are the same as $\pi$. Note that the $1^{\prime}s$ positioned at the squares
$(p_{2},q_{1})(p_{3},q_{2}),\ldots,$ $(p_{k},q_{k-1}),(p_{1},t)$ form an
$F_{k}$ in $\sigma$. Lemmas 3.5 and 3.6 ensure that when we apply the map
$\psi$ to $\sigma$, the squares we selected are just
$(p_{2},q_{1})(p_{3},q_{2}),\ldots,$ $(p_{k},q_{k-1}),(p_{1},t)$. By Lemma
3.7, there is no $H_{k}$ or $Q_{k}$ above row $p_{1}$. This implies that
$\psi(\sigma)$ is well defined. Clearly, we have $\sigma_{q_{i}}=p_{i+1}$ for
$i=1,2,\ldots,k-1$, $\sigma_{t}=p_{1}$ and $\sigma_{j}=\pi_{j+1}$ for
$j=q_{k},q_{k}+1,\ldots,t-1$.

Since $t\in\mathcal{A}(\pi)$ or $t=n$, we have $\pi_{t}<\pi_{t+1}$ or $t=n$.
This implies that $\sigma_{t-1}=\pi_{t}<\pi_{t+1}=\sigma_{t+1}$ or $t=n$. By
Remark 3.1, we see that there exits an $s$ such that $s-1\in\mathcal{D}(\pi)$
and $q_{k-1}<s<q_{k}$. This implies that $\pi_{s-1}>\pi_{s}<\pi_{s+1}$. Since
$\mathcal{D}(\pi)=\mathcal{D}(\sigma)$, we have
$\sigma_{s-1}>\sigma_{s}<\sigma_{s+1}$ and $p_{k-1}<s<q_{k}<t$. Then,
according to the definition of map $\psi$, we have
$\psi(\sigma)=\psi_{3}(\sigma)$. When we apply the the map $\psi_{3}$ to
$\sigma$, since we have $\mathcal{D}(\pi)=\mathcal{D}(\sigma)$ and
$\pi_{q_{k}-1}<\pi_{q_{k}}>\pi_{q_{k}+1}>\ldots>\pi_{t}$, $q_{k}$ is the
largest integer $m$ such that $m-1\in\mathcal{A}(\sigma)$ and $q_{k-1}<m\leq
t$. Thus, it is easily seen that $\psi_{3}(\sigma)=\pi$, that is,
$\psi(\phi^{t}(\tau))=\phi^{t-1}(\tau)$.

Case 3. The selected $1^{\prime}s$ form a copy of $Q_{k}$ and
$q_{k}\in\mathcal{A}(\pi)$. By the construction of the map $\phi$, the squares
$(p_{2},q_{1})(p_{3},q_{2}),\ldots,$ $(p_{k},q_{k-2}),(p_{1},q_{k})$ are
filled with $1^{\prime}s$ in $\sigma$, and all the other rows and columns are
the same as $\pi$. Note that the $1^{\prime}s$ positioned at the squares
$(p_{2},q_{1})(p_{3},q_{2}),\ldots,$ $(p_{k},q_{k-2}),(p_{1},q_{k})$ form an
$F_{k}$ in $\sigma$. Lemmas 3.5 and 3.6 ensure that when we apply the map
$\psi$ to $\sigma$, the squares we selected are just
$(p_{2},q_{1})(p_{3},q_{2}),\ldots,$ $(p_{k},q_{k-2}),(p_{1},q_{k})$. By Lemma
3.7, there is no $H_{k}$ or $Q_{k}$ above row $p_{1}$. This implies that
$\psi(\sigma)$ is well defined. Clearly, we have $\sigma_{q_{i}}=p_{i+1}$ for
$i=1,2,\ldots,k-3$, $\sigma_{q_{k-2}}=p_{k}$ and $\sigma_{q_{k}}=p_{1}$.

According to the definition of $Q_{k}$, we have
$\pi_{q_{k-1}}<\pi_{q_{k-1}+1}<\ldots<\pi_{q_{k}-1}>\pi_{q_{k}}$. Moreover, we
have $\sigma_{j}=\pi_{j}$ for $j=q_{k-1},q_{k-1}+1,\ldots,q_{k}-1$. Thus, we
have
$\sigma_{q_{k-1}}<\sigma_{q_{k-1}+1}<\ldots<\sigma_{q_{k}-1}>p_{1}=\sigma_{q_{k}}$
and $\sigma_{q_{k-2}}=p_{k}=\pi_{q_{k}}<\pi_{q_{k}+1}=\sigma_{q_{k}+1}$. Then,
according to the definition of map $\psi$, we have
$\psi(\sigma)=\psi_{1}(\sigma)$. Thus, it is easily seen that
$\psi_{1}(\sigma)=\pi$, that is, $\psi(\phi^{t}(\tau))=\phi^{t-1}(\tau)$.

Case 4. The selected $1^{\prime}s$ form a copy of $Q_{k}$, and
$\pi_{q_{k}}>\pi_{q_{k}+1}$ or $q_{k}=n$. In this case, let $t$ be the least
such that $t>q_{k}$ and $t\in\mathcal{A}(\pi)$ or $t=n$. By the construction
of the map $\phi$, the squares $(p_{2},q_{1})(p_{3},q_{2}),\ldots,$
$(p_{k},q_{k-2}),(\pi_{q_{k}+1},q_{k}),(\pi_{q_{k}+2},q_{k}+1),\ldots,(\pi_{t},t-1)(p_{1},t)$
are filled with $1^{\prime}s$ in $\sigma$, and all the other rows and columns
are the same as $\pi$. Note that the $1^{\prime}s$ positioned at the squares
$(p_{2},q_{1})(p_{3},q_{2}),\ldots,$ $(p_{k},q_{k-2}),(p_{1},t)$ form an
$F_{k}$ in $\sigma$. Lemmas 3.5 and 3.6 ensure that when we apply the map
$\psi$ to $\sigma$, the squares we selected are just
$(q_{2},p_{1})(q_{3},p_{2}),\ldots,$ $(p_{k},q_{k-1}),(p_{1},t)$. By Lemma
3.7, there is no $H_{k}$ or $Q_{k}$ above row $p_{1}$. This implies that
$\psi(\sigma)$ is well defined. Clearly, we have $\sigma_{q_{i}}=p_{i+1}$ for
$i=1,2,\ldots,k-3$, $\sigma_{q_{k-2}}=p_{k}$, $\sigma_{t}=p_{1}$ and
$\sigma_{j}=\pi_{j+1}$ for $j=q_{k},q_{k}+1,\ldots,t-1$.

Since $t\in\mathcal{A}(\pi)$ or $t=n$, we have $\pi_{t}<\pi_{t+1}$ or $t=n$.
This implies that $\sigma_{t-1}=\pi_{t}<\pi_{t+1}=\sigma_{t+1}$ or $t=n$.
According to the definition of $Q_{k}$, we have
$\pi_{q_{k-1}}<\pi_{q_{k-1}+1}<\ldots<\pi_{q_{k}-1}>\pi_{q_{k}}$. Thus, we
have
$\sigma_{q_{k-1}}<\sigma_{q_{k-1}+1}<\ldots<\sigma_{q_{k}-1}>\sigma_{q_{k}}>\sigma_{q_{k}+1}>\ldots>\sigma_{t}=p_{1}$.
Then, according to the definition of map $\psi$, we have
$\psi(\sigma)=\psi_{4}(\sigma)$. Thus, it is easily seen that
$\psi_{4}(\sigma)=\pi$, that is, $\psi(\phi^{t}(\tau))=\phi^{t-1}(\tau)$.

So far, we have deduced that $\psi(\phi^{t}(\tau))=\phi^{t-1}(\tau)$.

Now we proceed to to show that the map $\Psi$ is well defined, that is, after
finitely many iterations of $\psi$, there will be no occurrences of $F_{k}$.
Suppose that we start with some $\tau\in\mathcal{S}_{n}(H_{k},Q_{k})$. At the
$t$th application of $\psi$ we select a copy of $F_{k}$ in $\psi^{t-1}(\tau)$.
This has its lowest $1$ in some row $r$. By Lemma 3.13, the $F_{k}$ we will
select in $\phi^{t}(\tau)$ cannot have its lowest $1$ anywhere below row $r$.
If it in row $r$, then we know it is further to the left than at the previous
iteration, because there is only one $1$ in that row, and we have just moved
it to the left, from $b_{k}$ to $a_{1}$. It follows that at each iteration the
selection of $b_{k}$ can only go up or slide left. Moreover, Lemma 3.14
implies that there is no $H_{k}$ or $Q_{k}$ above $b_{k}$. Therefore, after
finitely many iterations of $\psi$, there will be no occurrences of $F_{k}$.

Next we aim to show that $\mathcal{D}(\tau)=\mathcal{D}(\Psi(\tau))$. We prove
by induction on $t$. Suppose that for any $j<t$, we have
$\mathcal{D}(\psi^{j-1}(\tau))=\mathcal{D}(\psi^{j}(\tau))$. We wish to show
that $\mathcal{D}(\psi^{t-1}(\tau))=\mathcal{D}(\psi^{t}(\tau))$. At the $t$th
application of $\psi$ we select a copy of $F_{k}$ in $\psi^{t-1}(\tau)$. This
has its lowest $1$ in some row $b_{k}$. Recall that we have shown that each
iteration the selection of lowest square of the selected $F_{k}$ can only go
up or slide left. By Lemma 3.14, there is no $H_{k}$ or $Q_{k}$ above $b_{k}$
in $\psi^{t-1}(\tau)$. Hence, from Lemma 3.12, it follow that
$\mathcal{D}(\psi^{t-1}(\tau))=\mathcal{D}(\psi^{t}(\tau))$.

By the same reasoning as in the proof of the equality
$\psi(\phi^{t}(\tau))=\phi^{t-1}(\tau)$, we can prove the equality
$\phi(\psi^{t}(\tau))=\psi^{t-1}(\tau)$ relying on Lemmas 3.14 and 3.17, and
the equality $\mathcal{D}(\psi^{t-1}(\tau))=\mathcal{D}(\psi^{t}(\tau))$. The
details are omitted here. This completes the proof.

Acknowledgments. The author was supported by the National Natural Science
Foundation of China.

## References

  * [1] E. Babson, J. West, and G. Xin, Wilf-equivalence for singleton classes, Adv. Appl. Math. 38 (2007), 133–148.
  * [2] J. Bloom, D. Saracino, On bijections for pattern-avoiding permutations, J. Combin. Theory Ser. A 116(2009), 1271–1284.
  * [3] J. Bloom, D. Saracino, Another look at bijections for pattern-avoiding permutations, Adv. Appl. Math. 45 (2010), 395–409.
  * [4] J. Bloom, A refinement of Wilf-equivalence for patterns of length 4, J. Combin. Theory Ser. A 124 (2014), 166–177.
  * [5] M. Bóna, Combinatorics of Permutations. CRC Press, 2004.
  * [6] M. Bóna, On a family of conjectures of Joel Lewis on alternating Permutations, Graphs Combin. 30 (2014), 521–526.
  * [7] A. Claesson, S. Kitaev, Classification of bijections between 321-and 132-avoiding permutations, S$\acute{e}$m. Lothar. Combin. 60 (2008/09), Art. B60d, 30pp.
  * [8] E. Deutsch, A. Robertson, D. Saracino, Refined restricted involutions, European J. Combin. 28 (2007), 481–498.
  * [9] T. Dokos, T. Dwyer, B. P. Johnson, B.E. Sagan, K. Selsor, Permutation patterns and statistics, Discrete Math. 312 (2012), 2760–2775.
  * [10] S. Elizalde, Fixed points and exceedances in restricted permutations, Electron. J. Combin. 18 (2011), P29.
  * [11] N. Gowravaram and R. Jagadeesan, Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux, Electron. J. Combin. 20:4 (2013), P17.
  * [12] S. Kitaev, Patterns in permutations and words. Springer Verlag (EATCS monographs in Theoretical Computer Science book series), 2011.
  * [13] J. B. Lewis, Generating trees and pattern avoidance in alternating permutations, Electronic J. Combin. 19:1 (2012), P21.
  * [14] A. Robertson, D. Saracino, D. Zeilberger, Refined restricted permutations, Ann.Comb. 6 (2002), 427–444.
  * [15] J. West, Permutations with forbidden subsequences and stack-sortable permutations, phD thesis, Massachuetts Institute of Technology (1990).