\documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amssymb,amsfonts,amsmath, psfrag,eepic,colordvi} \parskip 6pt\setlength{\unitlength}{1mm} \newcommand{\rmnum}[1]{\romannumeral #1} \topmargin 0 pt \textheight 46\baselineskip \advance\textheight by \topskip \setlength{\parskip}{0pt plus 0pt minus 0pt} \setlength{\textwidth}{145mm} \setlength{\oddsidemargin}{5.6mm} \setlength{\evensidemargin}{5.6mm} %\setcounter{section}{-1} \newcommand{\light}[1]{{#1}} \newcommand{\bulletcolor}[1]{{#1}} % only use standard LaTeX packages % only include essential packages % 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 26, 2013}{Sep 14, 2013}\\ \small Mathematics Subject Classifications: 05A05, 05C30} \begin{document} %\includegraphics[width=\textwidth]{pageHeader} \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}(50,40) \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_1t_{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} \pf 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.\qed 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}. \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}(80,30) \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_1a''$; \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{itemize} \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{itemize} \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'b_1$. \end{lemma} \pf 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. \qed \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} \pf 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''$ 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''$. Since $b_1\in D$ and $L$ is valid, we have $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''$). Since we move the $1$ positioned at row $a_1$ to the left in the application of $\psi$ to $L'$, we conclude that $b'_1r_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_1r_3$ by considering the following cases. \begin{itemize} \item[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_1r_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\}$. \begin{itemize} \item[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'_1a_{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$. \item[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_1a_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_1a_t>a_{t+1}=r_3$. \item[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}r_3$. \end{itemize} \item[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_1r_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_1a_k=r_3$. Since $r_2=a_{1}$ and $a_1>a_{k-1}>a_k$, we have $r_1r_3$. \item[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_1r_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. \begin{itemize} \item[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'r_3=a'$. It remains to show that $r_1r_3$. Thus we have $r_1r_3$. \end{itemize} \item[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_1r_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. \begin{itemize} \item[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''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_3a''$. Thus we have $r_2=a'>a''=r_3$. Now it remains to show that $r_1a_k$. Thus we deduce that $r_1b_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_1r_3$. We consider the following cases. \begin{itemize} \item[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_1r_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\}$. \begin{itemize} \item[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_1r_3$. We have two cases. If $c+1=b_{t-1}$, then we have $r_3=a_t$, which implies that $r_3r_3$. Thus we have $r_2=a_{t+1}>a_t>r_3$. \item[Subcase 1.2.] $c+1=b_t$ and $c\neq b_{t+1}$ for some integer $1a_{t}$. We claim that $r_2>a_{t+1}$. If not, then suppose that $r_2r_3$. It remains to show that $r_1r_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_1r_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_1a_k$. We claim that $r_2>r_3$. If not, then suppose that $r_2a_1=r_3$. \item[Subcase 1.4.] $c-1=b_{t}$ and $c+1\neq b_{t-1}$ for some integer $1r_3$. We claim that $r_2>r_1$. If not, then suppose that $r_2a'\geq a_2$. \begin{itemize} \item[Subcase 2.1] $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_1r_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_3$, we have $r_1r_3$. \item[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_1r_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_1r_3$. We claim that $a_2a''$. 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_1r_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_1a'$. Thus we have $r_2>a'>a_2=r_3$. Next we proceed to show that $r_1r$. 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)))$. \item[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''$. 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)))$. \end{itemize} 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. \begin{itemize} \item[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)$. \item[Case 2.] $b_1\in D$ and $a'a'\geq a_2$. Recall that in the proof of Theorem \ref{th2} we have proved that 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_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)$. \item[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)$. \end{itemize} This completes the proof. \qed \noindent{\bf 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.}, 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: math.CO \,1212.2697v1. \bibitem{gj} N. Gowravaram and R. Jagadeesan, Beyond alternating permutations: Pattern avoidance in Young diagrams and tableaux, arXiv: math.CO \,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. Available online at http://www-math.mit.edu/$\sim$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}