
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P58}{20(3)}{2013}

\usepackage{amsthm,amssymb,amsfonts,amsmath, psfrag,eepic,colordvi,enumerate}
\newcommand{\rmnum}[1]{\romannumeral #1}

%\newcommand{\light}[1]{{#1}}
%\newcommand{\bulletcolor}[1]{{#1}}

% we recommend these ams packages
\usepackage{amsthm,amsmath,amssymb}

% we recommend the graphicx package for importing figures
\usepackage{graphicx}

% use this command to create hyperlinks (optional and recommended)
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}

% use these commands for typesetting doi and arXiv references in the bibliography
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

% all overfull boxes must be fixed; i.e. there must be no text protruding into the margins
% use \sloppy to avoid overly wide text
\sloppy

% declare theorem-like environments

\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}\newtheorem{example}[theorem]{Example}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{property}[theorem]{Property}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{notation}[theorem]{Notation}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}



%\def\pf{\noindent {\it Proof.} }
%\def\qed{\hfill \rule{4pt}{7pt}}




%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

% if needed include a line break (\\) at an appropriate place in the title

\title{\bf On Wilf equivalence for\\ alternating permutations}


% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address


  \author{
  Sherry H. F. Yan \\
\small Department of Mathematics  \\[-0.8ex]
\small Zhejiang Normal University\\[-0.8ex]
\small Jinhua 321004, P.R. China\\
\small\tt  huifangyan@hotmail.com
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Mar 27, 2013}{Sep 21, 2013}{Oct 7, 2013}\\
\small Mathematics Subject Classifications: 05A05, 05C30}
\begin{document}
\maketitle
% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.



\begin{abstract}
 In this paper, we obtain several new classes of  Wilf-equivalent patterns for  alternating permutations. In particular, we prove that for any nonempty pattern $\tau$,  the patterns
$12\ldots k\oplus\tau$ and $k\ldots 21\oplus\tau$    are  Wilf-equivalent for  alternating permutations, paralleling a result
  of Backelin, West, and Xin for  Wilf-equivalence for permutations.

% keywords are optional
\bigskip\noindent \textbf{Keywords:} alternating permutation; pattern avoiding;  Wilf-equivalent;  alternating Young diagram.

 \end{abstract}





%===========================================================================

\section{Introduction}



A permutation $\pi=\pi_1\pi_2\ldots\pi_n$ of length $n$ on
$[n]=\{1,2,\ldots, n\}$ is said to be an {\em   alternating}
permutation if $\pi_1<\pi_2>\pi_3<\pi_4>\cdots$. Similarly, $\pi$
is said to be a {\em reverse } alternating permutation if
$\pi_1>\pi_2<\pi_3>\pi_4<\cdots$.  We denote by $\mathcal{A}_n$ and
$\mathcal{A'}_n$ the set of  alternating  and reverse alternating
permutations of length $n$, respectively.

 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 {\em 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  {\em avoid } the pattern $\tau$ or be {\em
$\tau$-avoiding}.

Pattern avoiding permutations have been extensively studied  over last decade.
For a thorough summary of the
current status of research,
see B\'{o}na's  book \cite{bona} and Kitaev's book \cite{kitaev}.
Analogous to  the  ordinary permutations,     Mansour \cite{mansour} initiated the  study of  alternating permutations avoiding a given pattern.  For any pattern of length $3$, the number of alternating permutations of a given length  avoiding that pattern is given by Catalan numbers, see \cite{mansour, stanley1}.  Recently,  Lewis \cite{Lewis1} considered  the  enumeration of alternating permutations avoiding a given pattern of length
$4$.  Let $\mathcal{A}_n(\tau)$ and
$\mathcal{A'}_n(\tau)$ be the set of $\tau$-avoiding alternating  and
reverse alternating  permutations of length $n$, respectively.
Lewis \cite{Lewis1} showed that there is a bijection between $\mathcal{A}_{2n}(1234)$ and the set of  standard Young tableaux of shape $(n,n,n)$, and
between the set $\mathcal{A}_{2n+1}(1234)$ and the set of standard Young tableaux of shape $(n+1, n,
n-1)$. Using the hook length formula for  standard Young tableaux
\cite{stanley2},  he deduced that  $|\mathcal{A}_{2n}(1234)|={2(3n)!\over
n!(n+1)!(n+2)!}$ and  $|\mathcal{A}_{2n+1} (1234)|={16(3n)!\over (n-1)!(n+1)!(n+3)!}$.   Later, Lewis \cite{Lewis2} showed that the generating trees  for
$2143$-avoiding   alternating permutations of even length and odd length   are isomorphic to the generating trees  for
   standard Young tableaux
of shape $(n,n,n)$ and shifted standard Young tableaux of shape $(n+2, n+1, n)$, respectively.
In his paper \cite{Lewis2},   Lewis  posed  several conjectures   on the enumeration of alternating permutations avoiding a given pattern of length $4$ and $5$.  Some of these conjectures were proved by B\'{o}na \cite{bona2},   Chen et al. \cite{ccz} and Xu et al. \cite{xy}.


The {\em reverse} of a permutation $\pi=\pi_1\pi_2\ldots\pi_n$ is given by $\pi^r=\pi_n\pi_{n-1}\ldots \pi_1$ and the {\em complement} by $\pi^c=(n+1-\pi_1)(n+1-\pi_2)\ldots(n+1-\pi_n)$.
Recall that two   patterns $\alpha$ and $\beta$ are said to be  Wilf-equivalent if $|\mathcal{S}_n(\alpha)|=|\mathcal{S}_{n}(\beta)|$ for all natural numbers $n$. We denote this by $\alpha\sim \beta$.   It is clear that $\sigma\sim \sigma^c\sim\sigma^r\sim\sigma^{rc}$.   It is easily seen that the reverse and complement operation of an   alternating permutation of even length gives another   alternating permutations, and the reverse of an   alternating permutation of odd length  gives another   alternating permutation.  Thus, given a pattern $\sigma$, we have $|\mathcal{A}_{2n}(\sigma)|=|\mathcal{A}_{2n}(\sigma^{rc})|$ and $|\mathcal{A}_{2n+1}(\sigma)|=|\mathcal{A}_{2n+1}(\sigma^{r})|$ for all $n\geq 0$.
In this context,  $\sigma$ and $\sigma^{rc}$ are said to be  {\em trivially } Wilf-equivalent for alternating permutations of even length. Similarly, $\sigma$ and $\sigma^{r}$ are  said to be  {\em trivially } Wilf-equivalent for alternating permutations of odd length.


\begin{definition}
The direct sum of two permutations  $\alpha=\alpha_1\alpha_2\ldots \alpha_k\in \mathcal{S}_k$ and $\beta=\beta_1\beta_2\ldots \beta_l\in \mathcal{S}_l $, denoted by $\alpha\oplus\beta$,  is the permutation $\alpha_1\alpha_2\ldots \alpha_k(\beta_1+k)(\beta_2+k)\ldots(\beta_l+k)$.
\end{definition}


\begin{definition}
The skew sum of two permutations  $\alpha=\alpha_1\alpha_2\ldots \alpha_k\in \mathcal{S}_k$ and $\beta=\beta_1\beta_2\ldots \beta_l\in \mathcal{S}_l $, denoted by $\alpha\ominus \beta$,  is the permutation $(\alpha_1+l)(\alpha_2+l)\ldots (\alpha_k+l) \beta_1 \beta_2 \ldots \beta_l $.
\end{definition}

In this paper, we are mainly concerned  with  the  Wilf-equivalent classes of patterns for alternating permutations, which are the analogue of a result  for permutations proved by  Backelin, West, Xin \cite{BWX} and for involutions  proved by
  Bousquet-M\'elou and  Steingr\'imsson \cite{BS}.  We obtain the following non-trivial Wilf equivalence for alternating permutations.






\begin{theorem}\label{main1}
Let  $n\geq 1$ and $k\geq 2$.  The equality  $|\mathcal{A}_n(12\ldots k\oplus\tau)|=|\mathcal{A}_{n}(k\ldots 21\oplus\tau) |$ holds  for any nonempty pattern $\tau$.
\end{theorem}

\begin{theorem}\label{main2}
Let  $n\geq 1$ and $k\geq 2$.  The equality  $|\mathcal{A}_n(k-1\ldots 21k\oplus\tau)|=|\mathcal{A}_{n}(k\ldots 21\oplus\tau)| $ holds  for any nonempty  pattern $\tau$.
\end{theorem}


 \begin{theorem}\label{main4}
Let  $n\geq 1$ and $k\geq 3$.  The equality  $|\mathcal{A}_{2n+1}( 23\ldots k1\ominus \tau)|=|\mathcal{A}_{2n+1}(12\ldots k\ominus\tau)| $
holds  for any nonempty pattern $\tau$.
\end{theorem}

  \begin{theorem}\label{main5}
Let  $n\geq 1$ and $k\geq 3$.  The equality   $|\mathcal{A}_{2n}(   23\ldots k1 \ominus \tau)|=|\mathcal{A}_{2n}(   12\ldots k \ominus \tau )|$
 holds  for any (possibly empty) pattern $\tau$.
\end{theorem}





Note that Theorems \ref{main1} through \ref{main5}   were proved by  Gowravaram and Jagadeesan  \cite{gj} for $k=2,3$.










\section{Alternating-shape-Wilf-equivalence for alternating   Young diagrams }





 In this section, we follow the approach given in \cite{BW}, \cite{BWX},  \cite{BS} and \cite{gj}. We    study pattern avoidance for slightly more general objects than alternating permutation, namely, {\em transversals of   alternating Young diagrams}. Let us begin with some necessary definitions and notations.  We draw Young
diagrams in English notation and use matrix coordinates, and for example $(1, 2)$ is the second
square in the first row of a Young diagram.
\begin{definition}
Let $\lambda$ be a Young diagram with $k$ columns and $D$ be a subset of nonconsecutive positive  integers  of $[k]$. If for  any $i\in D$   column $i$ and column $i+1$ have the same length, then we call the pair $(\lambda, D)$ an alternating Young diagram.
An alternating Young diagram $(\lambda, D)$ is said to be a  strict alternating Young diagram if $D\subseteq [k-1]$.
\end{definition}


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

\begin{figure}[h,t]
\begin{center}
\begin{picture}(80,115)
\setlength{\unitlength}{1.5mm}

\put(0,0){\framebox(5,5){$1$} }

 \put(0,5){\framebox(5,5){$0$}  } \put(5,5){\framebox(5,5)  {$0$}}  \put(10,5){\framebox(5,5) {$1$} }
 \put(0,10){\framebox(5,5){$0$}  } \put(5,10){\framebox(5,5)  {$1$}}  \put(10,10){\framebox(5,5) {$0$} }

 \put(0,15){\framebox(5,5){$0$}  } \put(5,15){\framebox(5,5)  {$0$}}  \put(10,15){\framebox(5,5) {$0$} }\put(15,15){\framebox(5,5) {$1$} }

     \put(0,20){\framebox(5,5){$0$}  } \put(5,20){\framebox(5,5)  {$0$}}  \put(10,20){\framebox(5,5) {$0$} }\put(15,20){\framebox(5,5) {$0$} }


     \put(20,20){\framebox(5,5){$1$}  }



  \end{picture}
\end{center}
\caption{ The transversal $T=\{(1,5), (2,4), (3,2), (4, 3), (5,1)\}$.}\label{fig1}
\end{figure}

   The   notion of pattern  avoidance is extended to transversals of a Young diagram in \cite{BW} and \cite{BWX}.
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 $n$ by $n$ matrix $M$ in which the entry on column $i$ and row $\pi_i$ is $1$ and all the other entries are zero.





 Given a permutation $\alpha$ of $[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]$, $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.  In this context,  the permutation $\alpha$   is  called a {\em pattern}.  Denote by $\mathcal{S}_{\lambda}(\alpha)$  the set of all transversals of Young diagram $\lambda$ that avoid $\alpha$.  Two  patterns $\alpha$ and $\beta$ are said to be {\em shape-Wilf-equivalent}, denoted by $\alpha \sim_{s} \beta$,  if for all Young diagram $\lambda$, we have $|\mathcal{S}_{\lambda}(\alpha)|=|\mathcal{S}_{\lambda}(\beta)|$.

 \begin{definition}
Let $\lambda$ be a Young diagram with $k$ columns. Given a transversal $T=\{(t_i,i)\}_{i=1}^{k}$ of an alternating  Young diagram $(\lambda, D)$, let $Peak(T)=\{i|t_{i-1}<t_i>t_{i+1}\}$ with the assumption $t_0=t_{k+1}=0$.   Then $T$ is  said to be a valid transversal of $(\lambda, D)$  if we have   $D\subseteq Peak(T)$.
\end{definition}
Denote by $\mathcal{T}_{\lambda}^{D}$ the set of all  valid transversals of alternating Young diagram $(\lambda, D)$. Similarly, denote by  $\mathcal{T}_{\lambda}^{D}(\alpha)$ the set of all transversals of alternating Young diagram $(\lambda, D)$ that avoid $\alpha$.

\begin{definition}
Two patterns $\alpha$ and $\beta$ are called alternating-shape-Wilf-equivalent if $|\mathcal{T}_{\lambda}^{D}(\alpha)|=|\mathcal{T}_{\lambda}^{D}(\beta)|$ for all alternating Young
 diagrams $(\lambda, D)$.   We denote this by $\alpha\sim_{as}\beta$. Similarly,  two patterns $\alpha$ and $\beta$ are called strict-alternating-shape-Wilf-equivalent if $|\mathcal{T}_{\lambda}^{D}(\alpha)|=|\mathcal{T}_{\lambda}^{D}(\beta)|$ for all strict alternating Young
 diagrams $(\lambda, D)$. We denote this by $\alpha\sim_{sas}\beta$.
\end{definition}



Backelin, West, Xin \cite{BWX} proved the following shape-Wilf equivalences for transversals of Young diagrams.  Let $I_k=12\ldots k$ ,  $J_k=k\ldots 21$ and $F_k=(k-1)\ldots 21k$.
\begin{theorem}\label{BWX1}
(\cite{BWX}, Proposition 2.3 )
For any patterns $\alpha, \beta$ and $\sigma$, if $\alpha\sim_{s}\beta$, then $ \alpha\oplus\sigma\sim_{s} \beta\oplus\sigma $.
\end{theorem}

\begin{theorem}\label{BWX2}
(\cite{BWX}, Proposition 3.1)
For all $k\geq 2$,   $ F_k\sim_{s} J_k $.
\end{theorem}




\begin{theorem}\label{BWX3}
(\cite{BWX}, Proposition 2.2)
For all $k\geq 2$,   $ I_k\sim_{s} J_k $.
\end{theorem}


In this section, we will adapt their proof of Theorem \ref{BWX1} to obtain the following theorem.
\begin{theorem}\label{main8}
For any nonempty patterns $\alpha, \beta$ and $\sigma$, if $\alpha\sim_{sas}\beta$, then $ \alpha\oplus\sigma\sim_{as} \beta\oplus\sigma $.
\end{theorem}

\begin{proof} For any Young diagram $\lambda$ with $k$ columns and a subset $D$ of non-consecutive integers of $[k-1]$, let $f^{D}_{\lambda}: \mathcal{T}_{\lambda}^{D}(\alpha)\rightarrow \mathcal{T}_{\lambda}^{D}(\beta)$ implied by the hypothesis. Now fix Young diagram $\lambda$ and a subset $D$ of non-consecutive integers of $[k-1]$. We proceed to construct a bijection $g_{\lambda}^{D}:\mathcal{T}_{\lambda}^{D}(\alpha\oplus\sigma)\rightarrow \mathcal{T}_{\lambda}^{D}(\beta\oplus\sigma)$. Given a transversal  $T\in \mathcal{T}_{\lambda}^{D}(\alpha\oplus\sigma)$, we color the cell $(r,c)$ of $\lambda$ by white if the board of $\lambda$ lying above and to the right of it contains $\sigma$, or gray otherwise.  Then find the $1's$ coloured by gray, and colour the corresponding rows and columns gray. Denote   the white board by $\lambda'$.

  The white board $\lambda'$ is a Young diagram since if a cell is colored white, then each cell to the left and above it.
    Suppose that $c\in D$.  It is easily seen that if $c\in D$ and the cell $(r,c)$ is filled with a $1$ in $T$, then if the cell $(r,c)$ is coloured by white, then all the  cell  $(r',c+1)$ is also colored by white for all $r'\leq r$.
     This implies that  the white board form a strict alternating  Young diagram.  Denote this  by $(\lambda', D')$. Denote by $T'$ the
      the transversal $T$ restricted to the strict alternating Young diagram $(\lambda', D')$. Next we aim to show that $T'$ is a valid transversal of $(\lambda', D')$.  Suppose that  $c\in D$,    the squares $(r_1,c-1)$, $(r_2,c)$ and $(r_3, c+1)$ are filled with  $1's$ in $T$, and the square $(r_2, c)$ is coloured by white. Then the squares $(r_1,c-1)$ and $(r_3, c+1)$ are also coloured by white. This implies that
               $T'$ is a valid transversal of $(\lambda', D')$.  Since $T$ avoids $\alpha\oplus\sigma$, we have
                $T'\in \mathcal{T}_{\lambda'}^{D'}(\alpha)$. Applying  the map $f_{ \lambda'}^{  D'}$ to $T'$, we get a valid transversal in $\mathcal{T}_{ \lambda'}^{ D'}(\beta)$. Restoring the gray cells of $\lambda$ and their contents, we obtain a transversal $L$ of the  alternating Young diagram $(\lambda, D)$ avoiding the pattern $\beta\oplus \sigma$. It is easy to check that $L$ is a valid transversal of the  alternating Young diagram $(\lambda, D)$.




In order to show that the map $g_{\lambda}^{D}$ is a bijection, we  show that the above procedure is invertible. It is obvious that the map $g_{\lambda}^{D}$ only changes the white cells and leaves the gray cells fixed.  Hence when applying the inverse map $(g_{\lambda}^{D})^{-1}$,  the coloring of $L$ will result in the same semi-standard Young diagram $(\lambda', D')$ on which to apply the inverse transformation $(f_{\lambda'}^{D'})^{-1}$.  This completes the proof.
\end{proof}





In the next section, we will give a bijective proof of  the following analogous result of Theorem \ref{BWX2} given in  \cite{BWX}.

\begin{theorem}\label{prop2}
 For all $k\geq 3$,   $F_k\sim_{sas} J_k$.
\end{theorem}


 In order to prove Theorem \ref{main2}, we also need   the following Wilf equivalence for  alternating permutations, which was proved by
    Gowravaram and Jagadeesan     \cite{gj}.



\begin{theorem}\label{prop3} (\cite{gj}, Theorem 4.4 )
 Fix $n\geq 1$. For any nonempty patterns  $\sigma$,  we have $ |\mathcal{A}_{n}(12\oplus\sigma)|=|\mathcal{A}_n(21 \oplus\sigma) |$.
\end{theorem}
Note that      Theorem \ref{prop3} can also be proved  by similar reasoning as in the proof of Theorem \ref{main8}.



\bigskip

\noindent {\bf The proofs of Theorems \ref{main1} through \ref{main5}.}
   Combining Theorems \ref{main8} and  \ref{prop2}, we deduce that
    $ F_k\oplus\sigma\sim_{as} J_k\oplus\sigma $    for any nonempty pattern $\sigma$ and $k\geq 3$.
 Note that the permutation matrix of an alternating  (resp. reverse alternating)   permutation of length $n$ is a valid transversal of an alternating Young diagram $(\lambda, D)$, where $\lambda$ is a $n$ by $n$ square diagram and $D=\{2, 4, \ldots, \lfloor {n\over 2}\rfloor\}$ (resp.   $D=\{1, 3, \ldots,  \lceil {n\over 2}\rceil\}$).      Hence
 for $n\geq 0$ and $k\geq 3$, the equalities
 \begin{equation}\label{eq1}
  |\mathcal{A}_n(k-1\ldots 21k\oplus\tau)|=|\mathcal{A}_{n}(k\ldots 21\oplus\tau) |
  \end{equation}
  and
   \begin{equation}\label{eq2}
   |\mathcal{A'}_n(k-1\ldots 21k\oplus\tau)|=|\mathcal{A'}_{n}(k\ldots 21\oplus\tau) |
   \end{equation}
     hold  for any for any nonempty pattern $\tau$.


 When $\lambda$ is a  $2n$ by $2n$ square diagram  and $D=\{1, 3, \ldots, 2n-1\}$,   a valid transversal of $(\lambda, D)$ is the permutation matrix of an reverse  alternating permutations of even length. Therefore    for $n\geq 1$ and $k\geq 3$,    Theorem \ref{prop2} leads to the equality
  \begin{equation}\label{eq3}
  |\mathcal{A'}_{2n}(k-1\ldots 21k)|=|\mathcal{A'}_{2n}(k\ldots 21)|.
  \end{equation}


 Since  the complement  map  is a bijection between the set $\mathcal{A}_n$ and the
set $\mathcal{A'}_n$,  we obtain  Theorems \ref{main4} and \ref{main5} by combining Formulae (\ref{eq1}), (\ref{eq2}) and (\ref{eq3}).
  Combining Theorem   \ref{prop3} and Formula \ref{eq1}, we get Theorem \ref{main2}. From Theorem \ref{main2}, we immediately get Theorem \ref{main1}. This completes the proof. \qed

\section{The bijection}

In this section, we will prove Theorem \ref{prop2} by establishing a bijection between $\mathcal{T}_{\lambda}^{D}(F_k)$ and $\mathcal{T}_{\lambda}^{D}(J_k)$ for  every  strict alternating Young diagram  $(\lambda, D)$. Let us first describe two transformations defined by Backelin, West and Xin \cite{BWX}




\noindent{\bf The transformation $\phi$} Given a transversal $L$ of a Young diagram $\lambda$, if $L$ contains no $J_k$, we simply define $\phi(L)=L$. Otherwise, find the highest square $(a_1, b_1)$ containing a $1$, such that   there is a $J_k$ in $L$ in which $(a_1, b_1)$ is the leftmost $1$.  Then, find the leftmost $(a_2, b_2)$ containing a $1$, such that there is a $J_k$ in $L$ in which $(a_1, b_1)$ and $(a_2, b_2)$ are the leftmost two $1$'s. Finally, find $ (a_3, b_3), (a_4, b_4), \ldots, (a_k, b_k) $ one by one as $(a_2, b_2)$.  Let $\phi(L)$ be a transversal of $\lambda$ such that the squares $(a_2, b_1), (a_3, b_2), \ldots, (a_{k}, b_{k-1}), (a_1, b_k)$ are filled with $1's$ and the other rows and columns are the same as $L$.

\noindent{\bf The transformation $\psi$} Given a transversal $L$ of a Young diagram $\lambda$, if $L$ contains no $F_k$, we simply define $\psi(L)=L$. Otherwise, find the lowest square $(a_1, b_1)$ containing a $1$, such that   there is a $F_k$ in $L$ in which $(a_1, b_1)$ is the rightmost $1$.  Then, find the lowest $(a_2, b_2)$ containing a $1$, such that there is a $F_k$ in $L$ in which $(a_1, b_1)$ and $(a_2, b_2)$ are the rightmost two $1$'s. Finally, find $ (a_3, b_3), (a_4, b_4), \ldots, (a_k, b_k) $ one by one as $(a_2, b_2)$. Let $\psi(L)$ be a transversal of $\lambda$ such that the squares $(a_1, b_k), (a_{k}, b_{k-1}), \ldots, (a_{2}, b_1)$ are filled with $1's$ and the other rows and columns are the same as $L$.

\begin{example}\label{ex1}
 Let $k=3$.  Given a transversal $L=\{(1,2), (2,4), (3,3), (4,1)\}$ of  $4$ by $4$ square diagram $\lambda$, by applying the transformation $\phi$, we get a transversal $L'=\{(1,2), (2,3), (3,1), (4,4)\}$ as shown in Figure \ref{fig2}, where the selected $J_k$ is illustrated in bold.  Conversely, given a  transversal $L'=\{(1,2), (2,3),$ $ (3,1), (4,4)\}$ of a square diagram $\lambda$ we can recover the transversal $L$ by applying the transformation $\psi$ as shown in figure \ref{fig2}, where the selected $F_k$ is illustrated in bold.
 \end{example}
 
 \begin{figure}[h,t]
\begin{center}
\begin{picture}(240,90)
\setlength{\unitlength}{1.5mm}

\put(0,0){\framebox(5,5){$\textbf{1}$} }\put(5,0){\framebox(5,5){$0$} }\put(10,0){\framebox(5,5){$0$} }\put(15,0){\framebox(5,5){$0$} }
 \put(0,5){\framebox(5,5){$0$} }\put(5,5){\framebox(5,5){$0$} }\put(10,5){\framebox(5,5){$\textbf{1}$} }\put(15,5){\framebox(5,5){$0$} }
 \put(0,10){\framebox(5,5){$0$} }\put(5,10){\framebox(5,5){$0$} }\put(10,10){\framebox(5,5){$0$} }\put(15,10){\framebox(5,5){$\textbf{1}$} }
 \put(0,15){\framebox(5,5){$0$} }\put(5,15){\framebox(5,5){$1$} }\put(10,15){\framebox(5,5){$0$} }\put(15,15){\framebox(5,5){$0$} }


\put(25, 10){$\longrightarrow$}
\put(26, 12){$\phi$}
\put(25, 8){$\longleftarrow$}
 \put(26, 6){$\psi$}


\put(35,0){\framebox(5,5){$0$} }\put(40,0){\framebox(5,5){$0$} }\put(45,0){\framebox(5,5){$0$} }\put(50,0){\framebox(5,5){$\textbf{1}$} }
 \put(35,5){\framebox(5,5){$\textbf{1}$} }\put(40,5){\framebox(5,5){$0$} }\put(45,5){\framebox(5,5){$0$} }\put(50,5){\framebox(5,5){$0$} }
 \put(35,10){\framebox(5,5){$0$} }\put(40,10){\framebox(5,5){$0$} }\put(45,10){\framebox(5,5){$\textbf{1}$} }\put(50,10){\framebox(5,5){$0$} }
 \put(35,15){\framebox(5,5){$0$} }\put(40,15){\framebox(5,5){$1$} }\put(45,15){\framebox(5,5){$0$} }\put(50,15){\framebox(5,5){$0$} }

  \end{picture}
\end{center}
\caption{ An example of the transformations $\phi$ and $\psi$.} \label{fig2}
\end{figure}



Backelin, West and Xin \cite{BWX} proved the following properties of $\phi$ and $\psi$, which were essential in the construction of their bijection between $\mathcal{S}_\lambda(F_k)$ and $\mathcal{S}_{\lambda}(J_k)$. In the following lemmas, for all $1\leq i\leq k$,  let $(a_i, b_i)$ be the square selected in the application of   the  transformations $\phi$ and $\psi$.
\begin{lemma} \label{phi1}
 (\cite{BWX}, Lemma 4.1) There is no $J_k$ strictly above   row $a_1$ in $\phi(L)$.
\end{lemma}
\begin{lemma}\label{phi2}
(\cite{BWX}, Lemma 4.2) If $L$ contains no $F_k$ with at least one square below row $a_1$, then $\phi(L)$ contains no such $F_k$.
\end{lemma}
\begin{lemma}\label{phi3}
(\cite{BWX}, Lemma 4.3) There is no $J_t$ above $a_1$,  below row $a_{t+1}$ and to the left of column $b_{t+1}$ in $\phi(L)$.
\end{lemma}

\begin{lemma}\label{psi1}
(\cite{BWX}, Lemma 4.4)  If $L$ contains no $F_k$ with at least one square below row $a_1$, then  $\psi(L)$ contains no such $F_k$.
\end{lemma}
\begin{lemma}\label{psi2}
(\cite{BWX}, Lemma 4.5) If $L$ contains no $J_k$  that is above  row $a_1$, then $\psi(L)$ contains no such $J_k$.
\end{lemma}

\begin{lemma}\label{psi3}
(\cite{BWX}, Lemma 4.6)
If L contains no  $J_k$ that is above row $a_1$, the board that is above and to the right of $(a_t, b_{t-1})$
cannot contain a $J_{k-t}$ in $\psi(L)$ such that the lowest $1$ of this $J_{k-t}$   is to the left of $(a_{t+1}, b_{t})$, and this
$J_{t-k}$ , combining with the $1's$ positioned at squares  $(a_1, b_1),$ $(a_2,b_2)$, $\ldots$,    $(a_t, b_{t-1})$ forms a $J_k$ in $\psi(L)$.
\end{lemma}


  Combining Lemmas \ref{phi2} and  \ref{phi3} yields  the following result.
  \begin{lemma}\label{lem1}
  If $L$ is a transversal containing no $F_k$ with at least one square below row $a_1$, then we have $\psi(\phi(L))=L$.
  \end{lemma}
   Lemmas \ref{psi2} and  \ref{psi3} imply the following result.
  \begin{lemma}\label{lem2}
  If $L$ is a transversal containing no $J_k$ above row $a_1$, then we have $\phi(\psi(L))=L$.
  \end{lemma}
It is obvious that the transformation $\phi$ (resp. $\psi$) changes every occurrence of $J_k$ (resp. $F_k$) to an occurrence of $F_k$(resp. $J_k$).
Lemmas  \ref{phi1} and \ref{psi1} imply that after finitely many iterations of $\phi$ (resp. $\psi$), there will be no occurrence of $J_k$ (resp. $F_k$) in $L$. Denote by    $\phi^*$  (resp. $\psi^*$)  the iterated transformation, that recursively transforms every occurrence of $J_k$ (resp. $F_k$) into $F_k$ (resp. $J_k$). Backelin, West and Xin \cite{BWX} proved the following theorem.
  \begin{theorem}
  (\cite{BWX}, Proposition 3.1)  For every Young diagram $\lambda$, the transformations $\phi^*$ and $\psi^*$ induce a bijection between $\mathcal{S}_\lambda(F_k)$ and $\mathcal{S}_\lambda(J_k)$.
  \end{theorem}

In Example \ref{ex1}, it is easily seen that $L$ is a valid transversal of the  strict alternating Young diagram $(\lambda, D)$ with  $D=\{1,3\}$, while  the transversal $L'$ is not a valid transversal of   $(\lambda, D)$.  Hence, in order to establish a   bijection between $\mathcal{T}_{\lambda}^{D}(F_k)$ and $\mathcal{T}_{\lambda}^{D}(J_k)$ for  any  strict alternating Young diagram  $(\lambda, D)$, we need to
define two transformations  $\Phi$ and $\Psi$ on  valid transversals of the strict alternating Young diagram $(\lambda, D)$  by slightly modifying   the transformations $\phi$ and $\psi$.


 \noindent {\bf The transformation $\Phi$}  Given a valid transversal $L $ of a strict  alternating Young diagram $(\lambda, D)$, if $L$ contains no $J_k$, we simply define $ \Phi(L)=L$. Otherwise,  applying  the map $\phi$ to $L$, we get a transversal $\phi(L)$. Suppose that when we apply the map $\phi$ to $L$, the selected $1's$ are positioned at   $(a_1, b_1), (a_2, b_2), \ldots,    (a_k, b_k) $, where $b_1<b_2<\ldots<b_k$.
   Suppose that the squares $(a', b_k-1)$ and $(a'', b_k+1)$ are filled with $1's$ in $\phi(L)$. Define $\Phi(L)$ as follows:
    \begin{enumerate}
    \item[($\rmnum{1}$)]  if   $b_k-1, b_k+1 \notin D$,  then let $\Phi(L)=\phi(L)$;
        \item[($\rmnum{2}$)] if $b_k-1\in D$ and $b_k+1\notin D$,  then let   $\Phi(L)$ be a transversal in which    $(a_1, b_k-1)$ and $(a', b_k)$ are filled with $1's$, and all other rows and columns are the same as $\phi(L)$;
       \item[($\rmnum{3}$)] if   $b_k-1\in D$ and $b_k+1 \in D$,  then  let   $\Phi(L)$ be a transversal in which   $(a_1, b_k-1)$ and $(a', b_k)$ are filled with $1's$, and all other rows and columns are the same as $\phi(L)$ when $a'<a''$, and  let   $\Phi(L)$ be a transversal in which    $(a_1, b_k+1)$ and $(a'', b_k)$ are filled with $1's$, and all other rows and columns are the same as $\phi(L)$ when $a'>a''$;
         \item[ ($\rmnum{4}$)] if   $b_k-1\notin D$  and  $b_k+1 \in D$,  then let   $\Phi(L)$ be a transversal in which   $(a_1, b_k+1)$ and $(a'', b_k)$ are filled with $1's$, and all other rows and columns are the same as $\phi(L)$;
    \end{enumerate}


  \noindent  {   \bf The transformation $\Psi$}   Given a valid transversal $L $ of a strict  alternating Young diagram $(\lambda, D)$, if $L$ contains no $F_k$, we simply define $ \Psi(L)=L$.  Otherwise, find the lowest square $(a_1, b_1)$ containing a $1$, such that   there is a $F_k$ in $L$ in which $(a_1, b_1)$ is the rightmost $1$.  Then, find the lowest $(a_2, b_2)$ containing a $1$, such that there is a $F_k$ in $L$ in which $(a_1, b_1)$ and $(a_2, b_2)$ are the rightmost two $1$'s. Finally, find $ (a_3, b_3), (a_4, b_4), \ldots, (a_k, b_k) $ one by one as $(a_2, b_2)$.   We define $L'$ as follows:
   \begin{enumerate}
    \item[ ($\rmnum{1}'$)] if  $b_1\notin D$,  then let $L'=L$;
    \item[($\rmnum{2}'$)] if  $b_1\in D$, then suppose that the squares $(a', b_1-1)$ and  $(a'', b_1+1)$ are  filled with $1's$ in $L$.
     If   $a'>a''$, then
         let $L'$ be a transversal in which  the squares  $(a_1, b_1-1)$   and $(a', b_1)$ are filled with $1's$,  and all other rows and columns are the same as $L$;      If   $a'<a''$, then
         let $L'$ be a transversal in which  the squares  $(a_1, b_1+1)$   and $(a'', b_1)$are filled with $1's$,  and all other rows and columns are the same as $L$;
   \end{enumerate}
Set $\Psi(L)=\psi(L')$.



Now we proceed to  verify that $\Phi$ and $\Psi$ have the following  analogous properties  of $\phi$ and $\psi$.
   \begin{lemma}\label{Phi1}
 Fix $k\geq 3$. There is no $J_k$  strictly above   row $a_1$ in $\Phi(L)$. Moreover, if $\Phi(L)$ contains a $J_k$ whose leftmost $1$ is positioned at the square $(a_1, b'_1)$, then we have $b'_1>b_1$.
 \end{lemma}

 \begin{proof} By Lemma \ref{phi1}, there is no $J_k$ above row $a_1$ in $\phi(L)$. From the definition of $\Phi$, it is easily seen that there is  no $J_k$ above row $a_1$ in $\Phi(L)$.  Also, it is easy to check that for $k\geq 3$,  if $\Phi(L)$ contains a $J_k$ whose leftmost $1$ is positioned at the square $(a_1, b'_1)$, then we have $b'_1>b_1$.  This completes the proof. 
 \end{proof}

\begin{lemma}\label{Phi2}
Fix $k\geq 3$. If $L$ contains no $F_k$ with at least one square below row $a_1$, then $\Phi(L)$ contains no such $F_k$.
\end{lemma}

 \begin{proof}   Suppose that $H$ is a copy of $F_k$  with at least one square below row $a_1$ in $\Phi(L)$.  By Lemma \ref{phi2}, there is no $F_k$ with at least one square below row $a_1$ in $\phi(L)$. Hence the $1$ positioned at $(a', b_k)$ or $(a'', b_k)$ must fall in $H$. Moreover, we have $a'<a_1$ and $a''<a_1$. Thus, neither $(a', b_k)$ nor $(a'', b_k)$ is the rightmost square of $H$. Suppose that the rightmost $1$ of $H$ is positioned at $(r,c)$ in $\Phi(L)$. Then the $1's$ positioned at squares $(a_1,b_1), (a_2,, b_2), \ldots, (a_{k-1}, b_{k-1}), (r,c)$ will form a $F_k$ in $L$. This contradicts the fact that $L$ contains no $F_k$ with at least one square below $a_1$.  Thus $\Phi(L)$ contains no $F_k$ with at least one row below $a_1$.
This completes the proof. 
\end{proof}

\begin{lemma}\label{Psi1}
Fix $k\geq 3$.  If $L$ contains no $F_k$ with at least one square below row $a_1$  and no $J_k$ strictly above the row $a_1$ , then  $\Psi(L)$ contains no such $F_k$. Moreover, if $\Psi(L)$ contains a copy of $F_k$ whose rightmost $1$ is positioned at $(a_1, b'_1)$, then we have $b
'_1<b_1$.
\end{lemma}

 \begin{proof}  First we need to show that there is no $F_k$ with at least one square below row $a_1$ in $L'$.   If $b_1\notin D$, then we have $L'=L$. Thus it is obvious that $L'$ contains no $F_k$ with at least one square below row $a_1$ and contains a $F_k$ whose rightmost $1$ is positioned at the square $(a_1, b_1)$. If $b_1\in D$, then we have the following  two cases: $a'<a''$ or $a'>a''$ since  the squares $(a', b_1-1)$ and  $(a'', b_1+1)$ are  filled with $1's$ in $L$.   According to the construction of $L'$,  it is easily seen that in $L'$  the squares $(a_1, b_1+1)$ and $(a'', b_1)$ are filled with $1's$  in the former case, while  the squares $(a_1, b_1-1)$ and $(a', b_1)$ are filled with $1's$   in the latter case, and  the other rows and columns are the same as $L$.


    We claim that there is no $F_k$  with at least one row below $a_1$ in $L'$. If not, suppose that $G$ is such a $F_k$. Then  at least one of the squares $(a'', b_1)$ and $(a_1, b_1+1)$ must fall in $G$ when $a'<a''$ and at least one of the squares $(a_1, b_1-1)$ and $(a', b_1)$ must fall in $G$ when $a'>a''$.   Since $b_1\in D$ and $L$ is valid, we have $a'<a_1$ and $a''<a_1$. Thus the $1's$ positioned at  rows $b_1-1$, $b_1$ and $b_1+1$ cannot be the rightmost $1$ of   $G$.  Suppose that the rightmost $1$  of $G$ is positioned at the square $(r,c)$.  Then we have $c\geq b_1+2$.  Then the $1's$ positioned at the squares $(r,c), (a_2, b_2), \ldots, (a_k, b_k)$ will form a $F_k$ in $L$ and the square $(r,c)$ is below row $a_1$. This contradicts  the  fact that  $L$ contains no $F_k$ with at least one square below row $a_1$. Thus we conclude that  $L'$ contains no $F_k$ with at least one square below row $a_1$.



   Next we aim to show that  when $b_1\in D$  the transversal  $L'$ contains  a $F_k$ whose rightmost $1$  is at row $a_1$.  Clearly,  the statement is true  for the case when $a'<a''$ and $b_1\notin D$.  It remains to consider the case when $a'>a''$.  Since $L$ contains no $J_k$ above row $a_1$, we have $b_2\neq b_1-1$. Thus the $1's$ positioned at squares $(a_1, b_1-1)$, $(a_2, b_2)$, $\cdots$, $(a_k, b_k)$ form a $F_k$ in $L'$.
    Recall that we have shown that there is no $F_k$ whose rightmost $1$ is strictly above row $a_1$. Therefore,   we select a    copy of $F_k$ whose rightmost $1$ is at row $a_1$ in the application of $\psi$ to $L'$.  From Lemma \ref{psi1}, it follows that $\Psi(L)$ contains no $F_k$ with at least one square below row $a_1$.




   Suppose that $\Psi(L)$ contains a  $F_k$ whose rightmost $1$ is positioned at the square $(a_1, b'_1)$. Recall that when we apply the map $\psi$ to the transversal $L'$,   the rightmost $1$  of the selected $F_k$ is positioned at the square $(a_1, b_1)$ when $b_1\notin D$. Moreover, when $b_1\in D$,  the rightmost $1$  of the selected $F_k$ is positioned at the $(a_1, b_1+1)$  (resp. $(a_1, b_1-1)$) if $a'<a''$ (resp. $a'>a''$).  Since we move the $1$ positioned at row $a_1$ to the left in the application of $\psi$ to $L'$, we conclude that $b'_1<b_1$.
    This completes the proof. 
    \end{proof}


\begin{lemma}\label{Psi2}
Fix $k\geq 3$. If $L$ contains no  $J_k$ above row $a_1$, then $\Psi(L)$ contains no such $J_k$.
\end{lemma}

 \begin{proof}  It is easy to check that $L'$ contains no $J_k$ above row $a_1$. Recall that in the proof of Lemma \ref{Psi1}, we have shown that when we apply $\psi$ to $L'$,    we select a copy of $F_k$ whose rightmost $1$ is at row $a_1$. By Lemma \ref{psi2}, we deduce that $\Psi(L)$ contains no  $J_k$ above row $a_1$. This completes the proof.
 \end{proof}


  Lemma \ref{Phi1} states that   the square $(a_1, b_1)$  we find in the transformation $\Phi$ can only go down or slide right. Similarly,
  Lemmas  \ref{Psi1} and \ref{Psi2} tells us that the square $(a_1, b_1)$ selected in the application of the transformation $\Psi$ can only go up or slide left.  Hence,   there will no  $J_k$  (resp. $F_k$)  in the resulting transversal
   after finitely many   iterations of $\Phi$ (resp. $\Psi$).
 Denote by  $\Phi^*(L)$  (resp. $\Psi^*(L)$) the resulting transversal.

The key to  our paper is the following theorem.

 \begin{theorem}\label{main}
  Fix  $k\geq 3$. For any  strict alternating  Young diagram $(\lambda, D)$, the transformations $\Phi^*$ and $\Psi^*$ induce a bijection between $\mathcal{T}_\lambda^{D}(F_k)$ and $\mathcal{T}_\lambda^{D}(J_k)$.
  \end{theorem}

 \section{The proof}

In this section, we will give a proof of Theorem \ref{main}.  First we need to show  that the transformations $\Phi$ and $\Psi$ transform a valid transversal into a valid transversal. Denote by $\Phi^0(L)=L$ and $\Psi^0(L)=L$ for any transversal $L$.

 \begin{theorem}\label{th1}
 Fix $n\geq 0$ and $k\geq 3$. For any strict alternating Young diagram $(\lambda, D)$ and  any  transversal $L\in \mathcal{T}_{\lambda}^{D}(F_k)$,  the transversal $\Phi^n(L)$ is a valid transversal  of    $(\lambda, D)$.
 \end{theorem}

\begin{proof} We   proceed     by induction on $n$. Clearly, the theorem holds for $n=0$.   For $n\geq 1$,  assume that $\Phi^{n-1}(L) $ is a valid transversal  of $(\lambda, D)$. Now we aim to show that  $\Phi^{n}(L) $ is also a valid transversal  of $(\lambda, D)$.
 Let $c\in D$.   Suppose that the squares  $(r_1, c-1)$, $(r_2, c)$ and $(r_3, c+1)$ are filled with $1's$ in $\Phi^{n} (L)$. In order to show that $\Phi^n(L)$ is a valid transversal, it suffices to show that $r_1<r_2>r_3$.


  Suppose that when we apply $\Phi$ to $\Phi^{n-1}(L)$, we select a copy of  $J_k$ whose $1's$ are positioned at squares $(a_1, b_1)$, $(a_2, b_2)$, $\ldots$, $(a_k, b_k)$.     First we need to show that  $b_k\notin D$. If not, then suppose that $b_k
 \in D$ and the square $(r, b_k+1)$ is filled with a  $1$ in $\Phi^{n-1}(L)$.   Since $\Phi^{n-1}(L)$ is valid, we have  $a_k>r$. Thus the $1's$ positioned at   squares $(a_2, b_2)$, $(a_3, b_3)$, $\ldots$, $(a_k,b_k)$ and $(r, b_k+1)$ will form a $J_k$ in $\Phi^{n-1}(L)$, which contradicts the selection of $(a_1, b_1)$. Thus we conclude that $b_k\notin D$.

Next we proceed to prove $r_1<r_2>r_3$  by considering the following cases.

\medskip\textbf{Case 1.}   The square $(a_1, b_k)$ is filled with a $1$ in $\Phi^n(L)$: According to the definition of $\Phi$, we have $b_k-1, b_k+1\notin D$.  Moreover,   the squares $(a_2, b_1)$, $(a_3, b_2)$, $\ldots$, $(a_k,b_{k-1})$ and $(a_1, b_k)$ are filled with $1's$ in $\Phi^n(L)$ and all the other rows and columns  are the same as $\Phi^{n-1}(L)$.  In order to show that $r_1<r_2>r_3$, it suffices to consider the case when at least one of $c-1, c, c+1$ belongs to the set $\{b_1, b_2, \ldots, b_k\}$.

\medskip\textbf{Subcase 1.1.}  $c=b_t$  for  some  integer $t\leq k-1$:   According to the definition of $\Phi$, we have $r_2=a_{t+1}$. Suppose that the square $(r'_1, c-1)$ is filled with a  $1$ in $\Phi^{n-1}(L)$.  Since $\Phi^{n-1}(L)$ is valid and $b_t\in D$, we have   $r'_1<a_t$. This implies that   $c-1\neq b_{t-1}$.  Thus $r_1=r'_1$.  We claim that $r_1<a_{t+1}=r_2$. If not, suppose that $r_1>a_{t+1}$. Then the $1's$ positioned at squares $(a_1, b_1), (a_2, b_2)$, $\ldots$, $(a_{t-1}, b_{t-1})$, $(r_1, b_t-1), (a_{t+1}, b_{t+1}), \ldots, (a_k, b_k)$ will form a $J_k$ in $\Phi^{n-1}(L)$, which contradicts  the selection  of $(a_t, b_t)$. It remains to show that $a_{t+1}>r_3$. We have two cases. If  $c+1=b_{t+1}$, then we have $r_3=a_{t+2}$ according to the definition of $\Phi$. In this case, we have $ r_2=a_{t+1}> a_{t+2}=r_3$. If $c+1\neq b_{t+1}$, then the square $(r_3, c+1)$ is also filled with a $1$ in $\Phi^{n-1}(L)$. Since $\Phi^{n-1}(L)$ is valid,  we have $a_t>r_3$. We claim that $r_2=a_{t+1}>r_3$. If not, then suppose that $a_{t+1}<r_3$. Then the $1's$ positioned at squares $(a_2, b_2)$, $(a_3, b_3)$, $\ldots$, $(a_t,b_t)$  $(r_3, b_t+1)$, $(a_{t+1}, b_{t+1})$, $\ldots$, $(a_k, b_k)$ will form a $J_k$ in $L$, which contradicts the selection of $(a_1, b_1)$. Thus we conclude that $r_1<r_2>r_3$.

\medskip\textbf{Subcase 1.2.} $c+1=b_{t}$ and $c\neq b_{t-1}$ for  some  integer $t\leq k-1$:    According to the definition of  $\Phi$,  we have $r_3=a_{t+1}$ and the square  $(r_2, c)$ is also filled with a $1$ in $\Phi^{n-1}(L)$. Since $\Phi^{n-1}(L)$ is valid,  we have $r_2>a_t$. If $c-1\neq b_{t-1}$, then the square $(r_1, c-1)$ is also filled with a $1$ in $\Phi^{n-1}(L)$. Thus we have $r_1<r_2>a_t>a_{t+1}=r_3$.
         If $c-1= b_{t-1}$, then we have $r_1=a_t$.  Since $r_2>a_t$, we have $r_1<r_2>a_t>a_{t+1}=r_3$.

\medskip\textbf{Subcase 1.3.} $c-1=b_t$  and $c+1\neq b_{t+1}$ for some integer $t\leq k-1$:
        According to the definition of   $\Phi$,  we have $r_1=a_{t+1}$. Moreover, the squares $(r_2, c)$ and $(r_3, c+1)$ are also filled with $1's$ in $\Phi^{n-1}(L)$.  Thus we have $r_2>r_3$ and $r_2>a_t$. This implies that $ r_1=a_{t+1}<a_t<r_2>r_3$.
        
\medskip\textbf{Case 2.}   The square $(a_1, b_k-1)$ is filled with a $1$ in $\Phi^n(L)$ and $b_{k-1}=b_k-1$: According to the definition of $\Phi$, we have $b_k-1\in D$. Moreover,
    the squares  $(a_2, b_1)$, $\ldots$, $(a_{k-1}, b_{k-2}) $,
      $(a_1, b_{k-1})$  are filled with $1's$ in $\Phi^n(L)$ and all the other rows and columns are the same as $\Phi^{n-1}(L)$.
       In order to show that $r_1<r_2>r_3$, it suffices to consider the case when at least one of $c-1, c, c+1$ belongs to the set $\{b_1, b_2, \ldots, b_{k-1}\}$. Here we only consider the case when   $c=b_{k-1}$.   The other cases can be verified by similar arguments  as in the proofs of Case $1$.  It is obvious that when $c=b_{k-1}$ the squares $(r_1, c-1)$ and $(r_3, c+1)$ are also filled with $1's$ in $\Phi^{n-1}(L)$. By the induction hypothesis,     we have $r_1<a_{k-1}>a_k=r_3$. Since $r_2=a_{1}$  and $a_1>a_{k-1}>a_k$, we have  $r_1<r_2>r_3$.

\medskip\textbf{Case 3.}  The square $(a_1, b_k-1)$ is filled with a $1$ in $\Phi^n(L)$ and $b_{k-1}\neq b_k-1$: Recall that $\phi(\Phi^{n-1}(L))$ is a transversal in which squares $(a_2, b_1)$, $(a_3, b_2)$, $\ldots$, $(a_{k}, b_{k-1})$,  $(a_1, b_k)$ are filled with $1's$ and all the other rows and columns are the same as $\Phi^{n-1}(L)$.
    Suppose that the squares $(a', b_k-1)$ and $(a'', b_{k}+1)$ are filled with $1's$ in $\phi(\Phi^{n-1}(L))$. Since $b_{k-1}\neq b_k-1$, the squares $(a', b_k-1)$ and $(a'', b_k+1)$ are also filled with $1's$ in $\Phi^{n-1}(L)$.   According to   the definition of   $\Phi$, we have $b_k-1\in D$. Moreover, the squares $(a_2, b_1)$, $\ldots$, $(a_{k}, b_{k-1})$  $(a_{1}, b_k-1)$ and $(a', b_k)$ are filled with $1's$ in $\Phi^n(L)$  and all the other rows and columns are the same as $\Phi^{n-1}(L)$.
       In order to show that $r_1<r_2>r_3$, it suffices to consider the case when at least one of $c-1, c, c+1$ belongs to the set $\{b_1, b_2, \ldots, b_{k-1}, b_k-1, b_k \}$. Here we only consider the case when $c=b_k-1$ or $c-1=b_k$. The other cases can be treated in the same manner as Case 1.

\medskip\textbf{Subcase 3.1.} $c=b_k-1$"  According to the definition of $\Phi$, we have $r_2=a_1$ and $r_3=a'$.  By Lemma \ref{Phi2}, there is no $F_k$ with at least one square below row $a_1$ in $\Phi^{n-1}(L)$. This implies that   $a'<a_1$. Thus we have $r_2>r_3=a'$. It remains to show that $r_1<r_2$. We consider two cases.  If $c-1=b_{k-1}$, then $r_1=a_k$. Thus $r_1=a_k<a_1=r_2$. If $c-1\neq b_{k-1}$, then the square $(r_1, c-1)$ is also filled with a $1$ in $\Phi^{n-1}(L)$. Recall that the squares $(r_1, c-1)$ and $(a', c)$ are filled with $1's$ in $L$.   By the induction hypothesis, it follows that $r_1<a'$. Thus we have $r_1<a'<a_1=r_2$.

\medskip\textbf{Subcase 3.2.}  $c-1=b_k$:    According to the definition of $\Phi$, we have $a'<a''$,  $r_1=a'$ and $r_2=a''$. Moreover, the squares $(r_3, c+1)$  and $(r_2, c)$ are also    filled with  $1's$ in $\Phi^{n-1}(L)$. By the induction hypothesis, it follows that  $r_2>r_3$.  Thus we have $r_1<r_2>r_3$.



\medskip\textbf{Case 4.} 
                The square $(a_1, b_k+1)$ is filled with a $1$ in $\Phi^n(L)$:  Recall that $\phi(\Phi^{n-1}(L))$ is a transversal in which squares $(a_2, b_1)$, $(a_3, b_2)$, $\ldots$, $(a_{k}, b_{k-1})$,  $(a_1, b_k)$ are filled with $1's$ and all the other rows and columns are the same as $\Phi^{n-1}(L)$.    Suppose that the squares $(a', b_k-1)$ and $(a'', b_{k}+1)$ are filled with $1's$ in $\phi(\Phi^{n-1}(L))$.
                                                    Since the map $\phi$ only changes   columns $b_1, b_2, \ldots, b_{k}$, the square $(a'', b_k+1)$ is also  filled with a $1$ in $ \Phi^{n-1}(L) $.
                  According to   the definition of $\Phi$, we have $b_k+1\in D$. Moreover, the squares $(a_2, b_1)$, $\ldots$, $(a_{k}, b_{k-1})$  $(a_{1}, b_k+1)$ and $(a'', b_k)$ are filled with $1's$  in $\Phi^n(L)$ and all the other rows and columns are the same as $\Phi^{n-1}(L)$.

                   We claim that $b_k-1\neq b_{k-1}$. If not, suppose that $b_{k}-1=b_{k-1}$. Then we have $a'=a_k$.  Recall that the squares $(a_k, b_k)$ and $(a'', b_k+1)$ are filled with $1's$ in $\Phi^{n-1}(L)$. By the induction hypothesis, since $b_k+1\in D$, we have   $a_k>a''$. Thus the $1's$ positioned at   squares $(a_2, b_2)$, $(a_3, b_3)$, $\ldots$, $(a_k, b_k)$, $(a'', b_{k}+1)$ will form a $J_k$ in $\Phi^{n-1}(L)$, which contradicts  the selection of $(a_1, b_1)$. Thus the square $(a', b_k-1)$ is also filled with a $1$ in $\Phi^n(L)$ and $\Phi^{n-1}(L)$.

        In order to show that $r_1<r_2>r_3$, it suffices to consider the case when at least one of $c-1, c, c+1$ belongs to the set $\{b_1, b_2, \ldots,  b_k, b_k+1 \}$.  Here we only consider the case when $c=b_k+1$ or $c+1=b_k$. The other cases can be treated in the same manner as Case 1.

\medskip\textbf{Subcase 4.1.} $c=b_k+1$:   Thus we have $r_1=a''$ and $r_2=a_1$. By Lemma \ref{Phi2}, there is no $F_k$ with at least one square below row $a_1$ in $\Phi^{n-1}(L)$.  Recall that the square $(a'', b_k+1)$ is filled with a $1$ in $\Phi^{n-1}(L)$. Thus we have $a''<a_1$. This implies that $r_1<r_2$. It remains to show that $r_2>r_3$. According to the definition of $\Phi$, the squares $(r_3, b_k+2)$ and $(a'', b_k+1)$ are also filled with $1's$ in $\Phi^{n-1}(L)$. Since $b_k+1\in D$, by the induction hypothesis   we have $a''>r_3$.  Thus we have $r_3<a''<a_1=r_2$.

\medskip\textbf{Subcase 4.2.}   $c+1=b_{k}$:   In this case, we have $r_3=a''$.    Recall that the square $(r_2, b_k-1)$ is also filled with a $1$ in $ \Phi^{n-1}(L)$ and $\phi(\Phi^{n-1}(L))$. Thus we have $r_2=a'$.
                        Note that $b_k-1, b_k+1\in D$ and  the squares $(a', b_k-1)$ and $(a'', b_k+1)$ are filled with $1's$ in $\phi(\Phi^{n-1}(L))$.  According to the definition of $\Phi$, we have $a'>a''$. Thus we have $r_2=a'>a''=r_3$.
                                    Now it remains to show that $r_1<r_2$.   If $c-1\neq b_{k-1}$, then the square $(r_1, c-1)$ is also filled with $1$ in $\Phi^{n-1}(L)$. By the induction hypothesis, it follows that $r_1<r_2$.  If $c-1= b_{k-1}$, then we have $r_1=a_k$. Recall that the squares $(a', b_k-1)$ and $(a_k, b_k)$ are filled with $1's$ in $\Phi^{n-1}(L)$ and $b_k-1\in D$. By the induction hypothesis, we have $a'>a_k$. Thus we deduce that $r_1<r_2$.

\medskip
This completes the proof.
\end{proof}


 \begin{theorem}\label{th2}
 Fix $n\geq 0$ and $k\geq 3$. For  any strict alternating Young diagram $(\lambda, D)$  and  any  transversal $L\in \mathcal{T}_{\lambda}^{D}(F_k)$,  the transversal $\Psi^n(L)$ is a valid transversal  of $(\lambda, D)$.
 \end{theorem}

 \begin{proof} We   proceed     by induction on $n$. Clearly, the theorem holds for $n=0$.   For $n\geq 1$,  assume that $\Psi^{n-1}(L) $ is a valid transversal  of $(\lambda, D)$. Now we aim to show that  $\Psi^{n}(L) $ is also a valid transversal  of $(\lambda, D)$.  Suppose that when we apply $\Psi$ to $\Psi^{n-1}(L)$, we select a copy of  $F_k$ whose $1's$ are positioned at squares $(a_1, b_1), (a_2, b_2)$, $\ldots$, $(a_k, b_k)$, where $b_1>b_2>\ldots>b_k$. Assume that the squares $(a', b_1-1)$ and $(a'', b_1+1)$ are filled with $1's$ in $\Psi^{n-1}(L)$.



   Let $c\in D$. Suppose that the squares  $(r_1, c-1)$, $(r_2, c)$ and $(r_3, c+1)$ are filled with $1's$ in $\Psi^{n} (L)$. In order to show that $\Psi^n(L)$ is a valid transversal, it suffices to show that $r_1<r_2>r_3$. We consider the following cases.





\medskip\textbf{Case 1.} $b_1\notin D$: According to the selection of $(a_1,b_1)$, we have $b_1-1, b_1+1\notin D$.  Otherwise,   either the $1's$ positioned at squares
 $(a', b_1-1), (a_2, b_2), \cdots, (a_k, b_k)$ or those positioned at squares $(a', b_1-1), (a_2, b_2), \cdots, (a_k, b_k)$ will form a $F_k$ in $\Psi^{n-1}(L)$, hence contradicting the selection of $(a_1, b_1)$.
 From  the definition of $\Psi$, it follows that $\Psi^n(L)$ is a transversal in which   squares $(a_1, b_k)$, $(a_k,b_{k-1})$, $\ldots$, $(a_2, b_1)$ are filled with $1's$ in  and all the other rows and columns are the same as $\Psi^{n-1}(L)$. In order to show that $r_1<r_2>r_3$, it suffices to consider the case when at least one of $c-1, c, c+1$ belongs to the set $\{b_1, b_2, \ldots, b_k\}$.

\medskip\textbf{Subcase 1.1.} $c=b_t$ for some integer  $1< t\leq k$: It is easily seen that  the square  $(r_1, c-1)$ is also filled with a $1$ in $\Psi^{n-1}(L)$. Moreover, we have $r_2=a_{t+1}$ for $t<1$ and $r_2=a_1$ otherwise.
         Recall that the square $(a_t, b_t)$ is filled with a $1$ in $\Psi^{n-1}(L)$. Since $b_t\in D$, by the induction hypothesis we have $r_1<a_t$. Thus we have $r_1<a_t<a_{t+1}< a_1$.  Thus we deduce that  $r_1<r_2$. It remains to show that $r_2>r_3$. We have two cases. If $c+1=b_{t-1}$, then we have $r_3=a_t$, which implies that $r_3<r_2$. If $c+1\neq b_{t-1}$, then the square $(r_3, c+1)$ is also filled with a $1$ in $\Psi^{n-1}(L)$.  Since $b_t\in D$, by the induction hypothesis  we have $a_t>r_3$. Thus we have  $r_2=a_{t+1}>a_t>r_3$.

\medskip\textbf{Subcase 1.2.} $c+1=b_t$ and $c\neq b_{t+1}$  for some integer  $1<t<k$: It is easily seen that $r_3=a_{t+1}$ and the square $(r_2,c)$ is also filled with a $1$ in $\Psi^{n-1}(L)$. Since $c\in D$, by the induction hypothesis  we have $r_2>a_{t}$.  We claim that $r_2>a_{t+1}$. If not, then suppose that $r_2<a_{t+1}$. Then the $1's$ positioned at squares $(a_1, b_1), \ldots, (a_{t-1}, b_{t-1})$, $(r_2, b_t-1)$, $(a_{t+1, b_{t+1}})$, $\ldots, (a_k, b_k)$  will form a $F_k$ in $\Psi^{n-1}(L)$, which   contradicts  the selection of $(a_t, b_t)$. Thus we have $r_2>r_3$. It remains to show that $r_1<r_2$. We have three cases.
          $ (\rmnum{1})$ If $c-1\neq b_{t+1}$, then  the square $(r_1, c-1)$ is also filled with a $1$ in $\Psi^{n-1}(L)$. Since $c\in D$, by the induction hypothesis we have  $r_1<r_2$.
          $ (\rmnum{2})$ If $c-1=b_{t+1}$ and $t<k-1$, then  $r_1=a_{t+2}$. We claim  that $r_1<r_2$. If not, suppose that $a_{t+2}>r_2$.  Since $r_2>a_{t+1}$, we will get a contradiction with the selection of $(a_{t+1}, b_{t+1})$. $ (\rmnum{3})$ If $c-1=b_{k}$, then $r_1=a_1$. We claim that $a_1<r_2$.  If not, suppose that $a_1>r_2$.  Recall that the squares $(r_2, c)$ and $(a_k, c-1)$ are filled with $1's$ in $\Psi^{n-1}(L)$. Since $c\in D$, by the induction hypothesis we have $r_2>a_k$.  Thus the $1's$ positioned at squares   $(a_1, b_1),(a_3,b_3), \ldots, (a_k, b_k)(r_2, c)$ will form a $F_k$ in $\psi^{n-1}(L)$, which contradicts the selection of $(a_2,b_2)$. Thus we have $r_1=a_1<r_2$.

\medskip\textbf{Subcase 1.3.}  $c+1=b_{k}$: It is easy to check that $r_3=a_1$ and the squares $(r_1, c-1)$ and $(r_2, c)$ are also filled with $1's$ in $\Psi^{n-1}(L)$.  Since $c\in D$, by the induction hypothesis we have  $r_1<r_2$ and $r_2>a_k$. We claim that $r_2>r_3$. If not, then suppose that $r_2<a_1$. Then the $1's$ positioned at squares    $(a_1, b_1),(a_3,b_3), \ldots, (a_k, b_k)(r_2, b_k-1)$ will form a $F_k$ in $L$, which contradicts the selection of $(a_2,b_2)$. Thus we have $r_2>a_1=r_3$.


\medskip\textbf{Subcase 1.4.}  $c-1=b_{t}$ and $c+1\neq b_{t-1}$ for some integer $1<t\leq k $: It is easy to check that   the squares $(r_2,c)$  and $(r_3, c+1)$ are also filled with $1's$ in $\psi^{n-1}(L)$. Moreover,  we have $r_1=a_{t+1}$ when $t<k$ and $r_1=a_1$ otherwise.
               Since $c\in D$, by the induction hypothesis,    we have  $a_{t}<r_2>r_3$.  We claim that $r_2>r_1$.
               If not, then suppose that $r_2<a_{t+1}=r_1$ when $t<k$ and $r_2<a_1$ otherwise. Then  the $1's$ positioned at squares $(a_1, b_1), (a_2, b_2), \ldots, (a_{t-1}, b_{t-1}), (r_2, b_t+1), (a_{t+1}, b_{t+1}), \ldots, (a_k,b_k)$  form a  $F_k$ in $\Psi^{n-1}(L)$ in the former case, while  those positioned at  squares $(a_1, b_1), (a_2, b_2), \ldots,    (a_{k-1},b_{k-1})(r_2, c)$ form a  $F_k$ in $\Psi^{n-1}(L)$ in the latter case.  Both of them contradict    the selection of $(a_t, b_t)$. Thus we conclude that $r_1<r_2$.

\medskip\textbf{Case 2.} $b_1\in D$ and $a'<a''$: Let us first recall    the procedure of constructing $\Psi^n(L)$ from $\Psi^{n-1}(L)$. First we get a transversal $L'$ in which   $(a'', b_1)$  and $(a_1, b_1+1)$ are filled with $1's$  and all the other rows and columns are the same as $\Psi^{n-1}(L)$. Then,  we apply    $\psi$ to $L'$ to get $\Psi^n(L)$.  By Lemma \ref{Psi2}, there is no $J_k$ above the row $a_1$ in $\Psi^{n-1}(L)$.  Thus we have $a''>a'\geq a_2$.

\medskip\textbf{Subcase 2.1.} $a''<a_3$:  We claim that  when we apply   $\psi$ to $L'$ the $1's$ selected are positioned at   squares  $(a_1, b_1+1)$, $(a'', b_1)$, $(a_3, b_3)$, $\ldots$, $(a_k, b_k)$.   If not, suppose that $G$ is a copy of $F_k$  selected in the application of  $\psi$ to $L'$  such that at least one of the squares $(a_1, b_1+1)$, $(a'', b_1)$,  $(a_2, b_2)$, $(a_3, b_3)$, $\ldots$, $(a_k, b_k)$ does not fall in $G$. We label the $1's$ of $G$ from right to left by $g_1, g_2, \ldots, g_k$. Obviously,   $g_1$ and $g_2$ are positioned at the
         squares  $(a_1, b_1+1)$ and   $(a'', b_1)$, respectively.      When $a'=a_2$, let $p$ be the least integer such that $g_p$ is not positioned at $(a_p, b_p)$ for $p\geq 3$. Clearly, $g_p$ is below row $a_p$.  Then the $1's$ positioned at the squares $(a_1, b_1)$,  $(a_2, b_2)$ , $\ldots$, $(a_{p-1}, b_{p-1})$ combining with $g_p,   \ldots, g_k$, form a $F_k$ in $\Psi^{n-1}(L)$. This contradicts the selection of $(a_p, b_p)$.  When $a'>a_2$, then  the $1's$ positioned at the squares $(a_1, b_1)$  and $(a', b_1-1)$, combining  $g_3,   \ldots, g_k$, form a $F_k$ in $\Psi^{n-1}(L)$, hence contradicting  the selection of $(a_2, b_2)$.







        By the definition of $\Psi$,  the transversal $\Psi^n(L)$ is a transversal in which  squares $(a_1, b_k)$,  $(a_k, b_{k-1})$,  $\ldots$, $(a_4, b_3)$,  $(a_3, b_1)$ are filled with $1's$ in $\Psi^n(L)$ and all the other rows and columns are the same as $\Psi^{n-1}(L)$. In order to show that $r_1<r_2>r_3$, it suffices to consider the case when at least one of $c-1, c, c+1$ belongs to the set $\{ b_1, b_3, \ldots, b_k\}$. Here we only consider the case when $c=b_1$. The other cases can be treated similarly as Case 1. Let  $c=b_1$.  It is easy to check that the square $(a', b_1-1)$ is also filled with a $1$ in $\Psi(L)$. Thus we have $r_1=a'$. Note  that $r_2=a_3$ and $r_3=a''$. Since $a'<a''>a_3$, we have $r_1<r_2>r_3$.



\medskip\textbf{Subcase 2.2.} $a''>a_3$: Recall that the squares $(a'', b_1)$  and $(a_1, b_1+1)$ are filled with $1's$ in $L'$ and all the other rows and columns are the same as $\psi^{n-1}(L)$.

        We claim that  the selected $1's$ of a copy of $F_k$ are positioned at
                    squares  $(a_1, b_1+1)$, $(a_2, b_2)$, $(a_3, b_3)$, $\ldots$, $(a_k, b_k)$  in the procedure of applying  $\psi$ to $L'$.
          If not, suppose that $G$ is a copy of $F_k$ when we apply the map $\psi$ to $L'$  such that at least one of the squares $(a_1, b_1+1)$, $(a_2, b_2)$, $(a_3, b_3)$, $\ldots$, $(a_k, b_k)$ does not fall in $G$. We label the $1's$ of $G$ from right to left by $g_1, g_2, \ldots, g_k$. Thus $g_1$ and $g_2$ must be positioned at the squares $(a_1, b_1+1)$ and $(a'', b_1)$. Since $a''>a_3$, thus $g_3$ must be below row $a_3$. Since there is no $J_k$ above row $a_1$ in $\Psi^{n-1}(L)$, we have $a'\geq a_2$.  When $a'=a_2$, then the $1's$ positioned at the squares $(a_1, b_1)$ and $(a_2, b_2)$, combining with $g_3,   \ldots, g_k$, form a $F_k$ in $\Psi^{n-1}(L)$. This contradicts the selection of $(a_3, b_3)$. When $a'>a_2$, then  the $1's$ positioned at the squares $(a_1, b_1)$  and $(a', b_1-1)$, combining  $g_3,   \ldots, g_k$, form a $F_k$ in $\Psi^{n-1}(L)$. This also   contradicts the selection of $(a_2, b_2)$.



           By the definition of $\Psi$, the squares $(a_1, b_k)$,  $(a_k, b_{k-1})$, $\ldots$, $(a_2, b_1+1)$, $(a'', b_1)$ are filled with $1's$ in $\Psi^n(L)$ and all the other rows and columns are the same as $\Psi^{n-1}(L)$. In order to show that $r_1<r_2>r_3$, it suffices to consider the case when at least one of $c-1, c, c+1$ belongs to the set $\{b_1+1,   b_1,   b_2, \ldots, b_k\}$. Here we only consider the case when $c=b_1$ or $c-1=b_1+1$.  The discussion for other cases is the same as Case 1.

       Suppose that $c=b_1$.  It is easy to check that $r_2=a''$ and $r_3=a_2$. Since $a''>a_3>a_2$, we have $r_2>r_3$. Next we aim to show that $r_1<r_2$. We have two cases.  $ (\rmnum{1})$ If $b_1-1=b_2$, then we have $r_1=a_3$, which implies that $r_1<r_2$.  $ (\rmnum{2})$ If $b_1-1\neq b_2$, then the square $(r_1, c-1)$ is also filled with a $1$ in $\Psi^{n-1}(L)$. Thus we have $r_1=a'$. Since $a'<a''$, we deduce that $r_1<r_2$.



              Suppose that $c-1=b_1+1$.   Obviously, the squares $(r_2, c)$ and $(r_3, c+1)$ are also filled with $1's$ in $\psi^{n-1}(L)$.
                  Since $c\in D$, by the induction hypothesis we
                   have $r_2>r_3$. We claim that $a_2<r_2$. Otherwise, the squares $(a_k, b_k)$, $(a_{k-1}, b_{k-1}), \ldots, (a_2, b_2), (r_2, c)$ will form a $J_k$ above  row $a_1$. This contradicts the fact that there is no $J_k$ above  row $a_1$ in $\Psi^{n-1}(L)$. Thus we have $r_1=a_2<r_2$.

\medskip\textbf{Case 3.} $b_1\in D$ and $a'>a''$:   Let us first recall    the procedure of constructing $\Psi^n(L)$ from $\Psi^{n-1}(L)$. First we get a transversal $L'$ in which   $(a_1, b_1-1)$  and $(a', b_1)$ are filled with $1's$  and all the other rows and columns are the same as $\Psi^{n-1}(L)$. Then,  we apply    $\psi$ to $L'$ to get $\Psi^n(L)$.  By Lemma \ref{Psi2}, there is no $J_k$ above the row $a_1$ in $\Psi^{n-1}(L)$.  Thus we have $ a'\neq  a_2$.



         We claim that  when we apply  $\psi$   to $L'$,  the selected  $1's$  are positioned at  squares  $(a_1, b_1-1)$, $(a_2, b_2)$, $(a_3, b_3)$, $\ldots$, $(a_k, b_k)$. If not, suppose that $G$ is a copy of $F_k$ when we apply the map $\psi$ to $L'$  such that at least one of the squares $(a_1, b_1-1)$, $(a_2, b_2)$, $(a_3, b_3)$, $\ldots$, $(a_k, b_k)$ does not fall in $G$. We label the $1's$ of $G$ from right to left by $g_1, g_2, \ldots, g_k$.  According to the choice of $(a_1, b_1)$, we have that $g_1$ must be  positioned at $(a_1, b_1-1)$.
           Let $p$ be the least integer such that $g_p$ is not positioned at $(a_p, b_p)$. It follows that $g_p$ is below row $a_p$. Thus the $1's$ positioned at the squares $(a_1, b_1)$, $(a_2, b_2)$, $\ldots$, $(a_{p-1}, b_{p-1})$, combining $g_p, \ldots, g_{k}$ will form a $F_k$ in  $\Psi^{n-1}(L)$, hence contradicting the selection of $(a_p, b_p)$.





          By the definition of $\Psi$,  the  squares $(a_1, b_k)$,  $(a_k, b_{k-1})$, $\ldots$, $(a_2, b_1-1)$, $(a', b_1)$ are filled with $1's$ in $\Psi^n(L)$ and all the other rows and columns are the same as $\Psi^{n-1}(L)$. In order to show that $r_1<r_2>r_3$, it suffices to consider the case when at least one of $c-1, c, c+1$ belongs to the set $\{   b_1, b_1-1,  b_2, \ldots, b_k\}$. Here we only consider the case when $c=b_1$ or $c+1=b_1-1$. The other cases can be treated similarly as Case 1.

 Suppose that  $c=b_1$.          It is easy  to check that $r_2=a'$ and $r_3=a''$ and $r_1=a_2$. Since $a'>a''$, we have $r_2>r_3$.  By Lemma \ref{Psi2}, there is no   no $J_k$ above   row $a_1$ in $\Psi^{n-1}(L)$.  Thus we have $a'>a_2$.  This implies that $r_1<r_2$.


            Suppose that $c+1=b_1-1$.  It is easy to check that $r_3=a_2$.  By Lemma \ref{Psi2}, there is no $J_k$  above row $a_1$ in $\Psi^{n-1}(L)$.  Thus we have $b_2\notin D$ and $a_2<a'$. Thus,  the square $(r_2, c)$ is also filled with a $1$ in $\psi^{n-1}(L)$.
                Since $c\in D$, by the induction hypothesis we have    $r_2>a'$. Thus we have $r_2>a'>a_2=r_3$.  Next we proceed to show that $r_1<r_2$. We have two cases. If $c-1\neq b_2$, then the square $(r_1, c-1)$ is also filled with a $1$ in $\Psi^{n-1}(L)$. Since $c\in D$, by the induction hypothesis we have $ r_1<r_2$. If  $c-1= b_2$, then we have  $r_1=a_3$.  Recall that the squares $(a_2, c-1)$ and $(r_2, c)$ are filled with $1's$ in $\Psi^{n-1}(L)$. Since $c\in D$, by the induction hypothesis we have $a_2<r_2$. We claim that $r_1<r_2$. If not, then the $1's$ positioned at squares $(a_1, b_1), (r_2, c), (a_3, b_3), \ldots, (a_k, b_k)$ will form a $F_k$ in $\Psi^{n-1}(L)$, which contradicts   the selection of $(a_2, b_2)$. Thus we conclude that $r_1<r_2$.



\medskip
This completes the proof. 
\end{proof}


\begin{proof}[Proof of Theorem \ref{main}.] 
By Theorems \ref{th1} and \ref{th2},
it suffices to show that $\Phi^*$  and $\Psi^*$ are inverses of each other. First, we aim to show
$\Psi(\Phi^n(L))=\Phi^{n-1}(L)$ for any $L\in \mathcal{T}^{D}_{\lambda}(F_k) $. Assume that  $\Phi^n(L)\neq \Phi^{n-1}(L)$.

 Suppose that at the $n$th application of  $\Phi$ to $\Phi^{n-1}(L)$ we select a copy of $J_t$ in $\Phi^{n-1}(L)$. Assume that the selected  $1's$  are positioned at  the squares $(a_1, b_1)$,  $(a_2, b_2), \ldots, (a_k, b_k)$, where $b_1<b_2<\ldots<b_k$.

  By Lemmas \ref{lem1} and \ref{Phi2}, we have $\psi(\phi(\Phi^{n-1}(L)))=\Phi^{n-1}(L)$. In order to show that $\Psi(\Phi^n(L))=\Phi^{n-1}(L)$, it suffices to show that $\Psi(\Phi^n(L))=\psi(\phi(\Phi^{n-1}(L)))$. There are four cases to consider.

\medskip\textbf{Case 1.} The square $(a_1, b_k)$ is filled with a $1$ in $\Phi^{n}(L)$:  In this case,  we have $\Phi(\Phi^{n-1}(L))=\phi(\Phi^{n-1}(L))$.  This implies that  the squares $(a_1, b_k), (a_2, b_1),$ $\ldots, (a_k, b_{k-1})$ are filled with $1's$ in $\Phi^{n}(L)$ and the other rows and columns are the same as $\Phi^{n-1}(L)$.  By Lemma \ref{Phi2}, there is no $F_k$ with at least one square below row $a_1$ in $\Phi^{n-1}(L)$. Thus,  Lemmas \ref{phi2} and  \ref{phi3}  guarantee that when we apply $\Psi$ to $\Phi^{n}(L)$, the selected $1's$  of a copy of $F_k$  are positioned at  the squares $(a_1, b_k), (a_2, b_1),$ $ \ldots, (a_k, b_{k-1})$.  We claim that $b_k\notin D $. If not, suppose that $b_k\in D$ and the square $(r,b_k+1)$ is filled with a $1$ in $\Phi^{n-1}(L)$. By Theorem \ref{th1},  the transversal $\Phi^{n-1}(L)$ is valid.   This implies that $a_k>r$. Then the squares $(a_2, b_2), \ldots (a_k, b_k), (r, b_k+1)$ will form a $J_k$ in $\Phi^{n-1}(L)$. This contradicts the selection of $(a_1, b_1)$.  Thus we conclude that $b_k\notin D$.      According to the definition of $\Psi$, we have $\Psi(\Phi^{n}(L))=\psi(\Phi^{n}(L))=\psi(\phi(\Phi^{n-1}(L)))$.

  \medskip\textbf{Case 2.}   The square $(a_1, b_k-1)$ is filled with a $1$ in $\Phi^{n}(L)$ and $b_{k-1}=b_k-1$:  From the definition of $\Phi$, we have $b_k-1\in D$. Moreover, the squares   $(a_2, b_1)$, $\ldots$, $(a_{k-1}, b_{k-2}) $,
      $(a_1, b_k-1)$  are filled with $1's$ in $\Phi^{n}(L)$ and all the other rows and columns are the same as $\Phi^{n-1}(L)$. Note that the squares   $(a_2, b_1)$, $\ldots$, $(a_{k-1}, b_{k-2}), (a_k, b_k-1) $,
      $(a_1, b_k)$  are filled with $1's$ in $\phi(\Phi^{n-1}(L))$ and all the other rows and columns are the same as $\Phi^{n-1}(L)$.   Suppose that the square  $(a', b_k-2)$ is  filled with a $1$ in $\Phi^{n}(L)$. Since $b_k-1\in D$, we have $b_k-2\neq b_{k-2}$. This implies that the square $(a', b_k-2)$ is also filled with a $1$ in both $\Phi^{n-1}(L)$ and $\phi(\Phi^{n-1}(L))$. By Theorem \ref{th1}, the transversal $\Phi^{n-1}(L)$ is valid. Thus we have  $a'<a_{k-1}$.    Lemmas \ref{phi2}, \ref{phi3}, \ref{Phi1} and  \ref{Phi2}  ensure that when we apply the map $\Psi$ to $\Phi^n(L)$,  the selected $1's$ of a copy of $F_k$ are positioned at the squares $(a_2, b_1)$, $\ldots$, $(a_{k-1}, b_{k-2}), (a', b_k-2) $,
      $(a_1, b_k-1)$.     By Lemma \ref{Phi1}, there is no $J_k$ above row $a_1$ in $\Phi^n(L)$. This implies that  $a'<a_k$.  Recall that the squares $(a_k, b_k)$ and $(a', b_k-2)$   are filled with  a $1's$ in $\Phi^n(L)$, we have $\Psi(\Phi^n(L))=\psi(\phi(\Phi^{n-1}(L)))$.

\medskip\textbf{Case 3.}   The square $(a_1, b_k-1)$ is filled with a $1$ in $\Phi^{n}(L)$ and $b_{k-1}\neq b_k-1$:  Suppose that $(a', b_k-1)$  is filled with a $1$ in $\Phi^{n-1}(L)$.
  From the definition of $\Phi$, we have $b_k-1\in D$. Moreover, the squares   $(a_2, b_1)$, $\ldots$, $(a_{k-1}, b_{k-2}) $,
      $(a_k, b_{k-1})$, $(a_1, b_k-1)$  and $(a', b_k)$ are filled with $1's$ in $\Phi^{n}(L)$ and all the other rows and columns are the same as $\Phi^{n-1}(L)$. Note that the squares   $(a_2, b_1)$, $\ldots$, $(a_{k-1}, b_{k-2}), (a_k, b_{k-1}) $,
      $(a_1, b_k)$  are filled with $1's$ in $\phi(\Phi^{n-1}(L))$ and all the other rows and columns are the same as $\Phi^{n-1}(L)$.        Lemmas \ref{phi2}, \ref{phi3} and \ref{Phi2} guarantee that  when we apply the map $\Psi$ to $\Phi^n(L)$,  the selected $1's$  of  a copy of $F_k$ are positioned at the squares $(a_2, b_1)$, $\ldots$, $(a_{k-1}, b_{k-2}) $,      $(a_k, b_{k-1})$, $(a_1, b_k-1)$.

      Next we aim to show that $\Psi(\Phi^n(L))=\psi(\phi(\Phi^{n-1}(L)))$. We have two cases.
         If $b_{k-1}=b_k-2$, then we have $a_k<a'$ since $b_k-1\in D$.  Recall that the squares $(a', b_k)$ and $(a_k, b_k-2)$ are filled with $1's$ in $\Phi^n(L)$.  By the definition of $\Psi$, we have $\Psi(\Phi^n(L))=\psi(\phi(\Phi^{n-1}(L)))$.
        If $b_{k-1}\neq b_k-2$, then  suppose that $(a'', b_k-2)$ is filled with a $1$ in $\Phi^n(L)$. Then the square $(a'', b_k-2)$ is also filled with a $1$ in $\Phi^{n-1}(L)$.  By Theorem \ref{th1}, the transversal $\Phi^{n-1}(L)$ is valid. Since $b_k-1\in D$, we have $a''<a'$.
         Recall that  the squares $(a'', b_k-2)$ and $(a', b_k)$ are  filled with  $1's$ in $\Phi^{n}(L)$.
         Thus, by the definition of $\Psi$, we have $\Psi(\Phi^n(L))=\psi(\phi(\Phi^{n-1}(L)))$.

\medskip\textbf{Case 4.}   The square $(a_1, b_k+1)$ is filled with a $1$ in $\Phi^{n}(L)$:     Suppose that $(a', b_k+1)$ and $(a'', b_k+2)$ are filled with  $1's$ in $\Phi^{n-1}(L)$.
  From the definition of $\Phi$, we have $b_k+1\in D$. Moreover, the squares   $(a_2, b_1)$, $\ldots$, $(a_{k-1}, b_{k-2}) $,
      $(a_k, b_{k-1})$, $(a_1, b_k+1)$  and $(a', b_k)$ are filled with $1's$ in $\Phi^{n}(L)$ and all the other rows and columns are the same as $\Phi^{n-1}(L)$. Note that the squares   $(a_2, b_1)$, $\ldots$, $(a_{k-1}, b_{k-2}), (a_k, b_{k-1}) $,
      $(a_1, b_k)$  are filled with $1's$ in $\phi(\Phi^{n-1}(L))$ and all the other rows and columns are the same as $\Phi^{n-1}(L)$.        Lemmas \ref{phi2}, \ref{phi3} and \ref{Phi2} guarantee that  when we apply the map $\Psi$ to $\Phi^n(L)$, the selected $1's$ of a copy of $F_k$ are positioned at   squares $(a_2, b_1)$, $\ldots$, $(a_{k-1}, b_{k-2}) $,      $(a_k, b_{k-1})$, $(a_1, b_k+1)$.
          By Theorem \ref{th1}, the transversal $\Phi^{n-1}(L)$ is valid.   Since $b_k+1\in D$, we have $a'>a''$.  Recall that the squares $(a', b_k)$ and $(a'', b_k+2)$ are filled with $1's$ in $\Phi^n(L)$. Thus,
          by the definition of $\Psi$, we have $\Psi(\Phi^n(L))=\psi(\phi(\Phi^{n-1}(L)))$.

\medskip
 Our next goal is to show that $\Phi(\Psi^n(L))=\Psi^{n-1}(L)$ for any $L\in \mathcal{T}_{\lambda}^{D}(J_k)$.  Assume that $\Psi^{n}(L)\neq \Psi^{n-1}(L)$. Suppose that at the $n$th application of  $\Psi$ to $\Psi^{n-1}(L)$,  we select a copy of $F_k$ in $\Psi^{n-1}(L)$. Assume that the selected  $1's$ of this $F_k$ are positioned at   squares $(a_1, b_1)$, $(a_2, b_2)$, $\ldots, (a_k, b_k)$, where $b_1>b_2\ldots>b_k$.
  Suppose that the squares  $(a', b_1-1)$ and $(a'', b_1+1)$ are filled with $1's$ in $\Psi^{n-1}(L)$.
   We consider the following   cases.

\medskip\textbf{Case 1.} $b_1\notin D$: According to the selection of $(a_1,b_1)$, we have $a', a''< a_1$.  This implies that $b_1-1, b_1+1\notin D$.    Since $   b_1 \notin D$, we have $\Psi^n(L)=\psi(\Psi^{n-1}(L))$.  This implies that   the squares $(a_1, b_k)$, $(a_k,b_{k-1})$, $\ldots$, $(a_2, b_1)$ are filled with $1's$ in $\Psi^n(L)$ and all the other rows and columns are the same as $\Psi^{n-1}(L)$. Lemmas \ref{psi2}, \ref{psi3} and \ref{Psi2} guarantee that when we apply $\Phi$ to $\Psi^{n}(L)$, we will select a copy of $J_k$ whose $1's$ are positioned at squares $(a_1, b_k)$, $(a_k,b_{k-1})$, $\ldots$, $(a_2, b_1)$.  Since $b_1-1, b_1+1\notin D$, we have
       $\Phi(\Psi^n(L))=\phi(\Psi^n(L))=\phi(\psi(\Psi^{n-1}(L)))$.  By Lemmas \ref{lem2} and $\ref{Psi2}$, we have $\phi(\psi(\Psi^{n-1}(L)))=\Psi^{n-1}(L)$.

  \medskip\textbf{Case 2.} $b_1\in D$ and $a'<a''$:  Let us first recall    the procedure of constructing $\Psi^n(L)$ from $\Psi^{n-1}(L)$. First we get a transversal $L'$ in which   $(a'', b_1)$  and $(a_1, b_1+1)$ are filled with $1's$  and all the other rows and columns are the same as $\Psi^{n-1}(L)$. Then,  we apply    $\psi$ to $L'$ to get $\Psi^n(L)$.  Lemma \ref{Psi2} ensure there is no $J_k$ above  row $a_1$ in $\Psi^{n-1}(L)$, which implies that $a''>a'\geq a_2$.   Recall that in the proof  of Theorem \ref{th2}  we have proved that   if $a''<a_3$, the  $1's$ selected are positioned at   squares  $(a_1, b_1+1)$, $(a'', b_1)$, $(a_3, b_3)$, $\ldots$, $(a_k, b_k)$ in the application of $\psi$ to $L'$.  Moreover, if $a''>a_3$,   the selected $1's$ are positioned at
                    squares  $(a_1, b_1+1)$, $(a_2, b_2)$, $(a_3, b_3)$, $\ldots$, $(a_k, b_k)$  in the procedure of applying  $\psi$ to $L'$ .










        By the definition of $\Psi$,  we have $\Psi^n(L)=\psi(L')$.   Thus, when $a''<a_3$,  $\Psi^n(L)$ is a transversal in which the squares $(a'', b_1+1)$, $(a_3, b_2)$, $(a_4, b_3)$, $\ldots$, $(a_1, b_k)$ are filled with $1's$ and all the rows and columns are the same as $L'$.  when $a''>a_3$,    $\Psi^n(L)$ is a transversal in which the squares $(a_2, b_1+1)$, $(a_3, b_2)$, $(a_4, b_3)$, $\ldots$, $(a_1, b_k)$ are filled with $1's$ and all the rows and columns are the same as $L'$. Since there is no $J_k$ above row $a_1$ in $L'$ and $\Psi^n(L)=\psi(L')$ , by Lemmas \ref{psi2} and \ref{psi3}, when we apply $\Phi$ to $\Psi^n(L)$  we select a copy of $J_k$ which is just created by the application of $\psi$ to $L'$. Thus we have $\phi(\Psi^n(L))=\phi(\psi(L'))=L'$.         By the definition of $\Phi$, we have $\Phi(\Psi^n(L))=\Psi^{n-1}(L)$.


\medskip\textbf{Case 3.} $b_1\in D$ and $a'>a''$: Since there is no $J_k$ above row $a_1$ in $\Psi^{n-1}(L)$ according to Lemma \ref{Psi2}, we have $b_1-1\neq b_2$. Let us describe the procedure of constructing $\Psi^n(L)$ from $\Psi^{n-1}(L)$. First we get a transversal $L'$ in which
     the squares $(a_1, b_1-1)$  and $(a', b_1)$ are filled with $1's$  and all the other rows and columns are the same as $\Psi^{n-1}(L)$.
     Recall that we have shown  that the $1's$ selected in the application of $\psi$ to $L'$ are positioned at   squares  $(a_1, b_1-1)$, $(a_2, b_2)$, $(a_3, b_3)$, $\ldots$, $(a_k, b_k)$ in the proof of Theorem \ref{th2}.
       Since there is no $J_k$ above row $a_1$ in $L'$ and $\Psi^n(L)=\psi(L')$, by Lemmas \ref{psi2} and \ref{psi3}, when we apply $\Phi$ to $\Psi^n(L)$  we select a copy of $J_k$ which is just created by the application of $\psi$ to $L'$. That is, these $1's$ are positioned at squares $(a_2, b_1-1)$, $(a_3, b_2)$, $(a_4, b_3)$, $\ldots$, $(a_1, b_k)$.  Thus we have $\phi(\Psi^n(L))=\phi(\psi(L'))=L'$.         Hence   we have $\Phi(\Psi^n(L))=\Psi^{n-1}(L)$.

\medskip This completes the proof. 
 \end{proof}







\subsection*{Acknowledgments}   The author  would like to thank the referee for helpful suggestions. This work was supported by the
National Natural Science Foundation of China(No. 10901141).

%--------------------------
\begin{thebibliography}{100}
\bibitem{BW}
E. Babson and  J. West, The permutation $123p_4\ldots p_t$ and $321p_4\ldots p_t$ are Wilf-eqivalent.  {\em Graphs Combin.},   16:373--380,  2001.
\bibitem{BWX}
J. Backelin, J. West, and G. Xin, Wilf-equivalence for singleton classes.  {\em Adv. Appl.
Math.},   38:133--148,   2007.

\bibitem{BS}
 M. Bousquet-M\'elou, E. Steingr\'imsson,   Decreasing subsequences in permutations and Wilf equivalence for involutions. {\em
J. Algebraic Combin.},   22:383--409,  2005.
 \bibitem{bona}
 M. B\'{o}na,  Combinatorics of Permutations. CRC Press, 2004.
 \bibitem{bona2}
  M. B\'{o}na, On a family of conjectures of Joel Lewis on alternating Permutations.  {\em Graphs  Combin.},  2013. \doi{10.1007/s00373-013-1291-2}.



\bibitem{ccz}
 J. N. Chen, W. Y. C. Chen and R. D. P. Zhou, On pattern avoiding alternating permutations,   \arxiv{1212.2697v1}.

\bibitem{gj}
 N.  Gowravaram and  R. Jagadeesan, Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux,  \arxiv{1301.6796v1}.

\bibitem{kitaev}
S. Kitaev, Patterns in permutations and words. Springer Verlag (EATCS monographs in Theoretical Computer Science book series), 2011.

\bibitem{Lewis1}
J. B. Lewis, Pattern avoidance for alternating permutations and Young tableaux.
{\em J.  Combin.  Theory  Ser. A},   118:1436--1450,   2011.

\bibitem{Lewis2}
J. B. Lewis, Generating trees and pattern avoidance
in alternating permutations.
{\em Electronic J. Combin.},  19(1):P21,   2012.

\bibitem{mansour}
T. Mansour, Restricted 132-alternating permutations and Chebyshev polynomials. {\em Ann.  Combin.},    7:201--227,  2003.

 \bibitem{stanley2}
R. P. Stanley, Enumerative Combinatorics, Volume 2. Cambridge University Press, 2001.

\bibitem{stanley1}
R. P. Stanley,  Catalan addendum. \url{http://www-math.mit.edu/~rstan/ec/catadd.pdf},  2012.

\bibitem{xy}
Y. Xu and S. H. F. Yan,   Alternating
 permutations with restrictions   and standard Young tableaux.  {\em Electronic J. Combin.},   19(2):P49, 2012.
\end{thebibliography}
\end{document}
