\documentclass[12pt]{article}
 \usepackage{e-jc}

\usepackage[enableskew]{youngtab}
\usepackage{amssymb,amsfonts,amsmath, psfrag,eepic,colordvi}
\newcommand{\rmnum}[1]{\romannumeral #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
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

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

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

\title{\bf Alternating
permutations with restrictions\\  and standard Young tableaux}


% 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{Yuexiao  Xu   \\
\small Department of Mathematics  \\[-0.8ex]
\small Zhejiang Normal University\\[-0.8ex]
\small Jinhua 321004, P.R. China\\
\small\tt xyx1985@163.com\\
\and
  Sherry H. F. Yan\thanks{Corresponding author.} \\
\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{May 2, 2012}{June 15, 2012}\\
\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}
\noindent {\bf Abstract.}   In this paper, we   establish
 bijections between the set of $4123$-avoiding down-up alternating permutations
of length $2n$ and the set of standard Young tableaux of shape
$(n,n,n)$, and  between the set of $4123$-avoiding down-up alternating
permutations of length $2n-1$ and the set of shifted  standard Young
tableaux of shape $(n+1, n, n-1)$ via an intermediate structure of
Yamanouchi words. Moreover,  we show that   $4123$-avoiding  up-down alternating permutations of  length $2n+1$  are in one-to-one correspondence with   standard Young tableaux of shape $(n+1,n,n-1)$, and $4123$-avoiding  up-down alternating permutations of  length $2n $  are in bijection with   shifted standard Young tableaux of shape $(n+2,n,n-2)$.


% keywords are optional
\bigskip\noindent \textbf{Keywords:} alternating permutation; pattern avoiding;  Yamanouchi word; standard Young tableau; shifted standard Young tableau.
\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 up-down  alternating}
permutation if $\pi_1<\pi_2>\pi_3<\pi_4>\cdots$. Similarly, $\pi$
is said to be a {\em down-up} alternating permutation if
$\pi_1>\pi_2<\pi_3>\pi_4<\cdots$.  We denote by $\mathcal{UD}_n$ and
$\mathcal{DU}_n$ the set of up-down and down-up alternating
permutations of length $n$, respectively. Note that the {\em complement} map
$\pi=\pi_1\pi_2\ldots \pi_n \longmapsto (n+1-\pi_1)(n+1-\pi_2)\ldots
(n+1-\pi_n)$ is a bijection between the set $\mathcal{UD}_n$ and the
set $\mathcal{DU}_n$.

 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{UD}_n(\tau)$ and
$\mathcal{DU}_n(\tau)$ be the set of $\tau$-avoiding up-down and
down-up alternating  permutations of length $n$, respectively.
Lewis \cite{Lewis1} provided bijections between the set $\mathcal{UD}_{2n}(1234)$ and the set of  standard Young tableaux of shape $(n,n,n)$, and
between the set $\mathcal{UD}_{2n+1}(1234)$ and the set of standard Young tableaux of shape $(n+1, n,
n-1)$. By applying  the hook length formula for  standard Young tableaux
\cite{stanley2}, the number of $1234$-avoiding up-down
alternating permutations of length $2n$ is given by ${2(3n)!\over
n!(n+1)!(n+2)!}$, and the number of $1234$-avoiding up-down
alternating permutations of length $2n+1$ is given by ${16(3n)!\over (n-1)!(n+1)!(n+3)!}$.  Using the method of generating trees,
Lewis \cite{Lewis2} constructed   recursive bijections between the set $\mathcal{UD}_{2n}(2143)$ and the set of standard Young tableaux
of shape $(n,n,n)$, and between the set $\mathcal{UD}_{2n+1}(2143)$ and the set of shifted standard Young tableaux of shape $(n+2, n+1, n)$.
Using computer simulations,  Lewis \cite{Lewis2} came up with several conjectures   on the enumeration of alternating permutations avoiding a given pattern of length $4$ and $5$. Recently, B\'{o}na \cite{bona2} proved generalized versions of some conjectures of Joel Lewis on the number of alternating permutations avoiding certain patterns. He  showed that $|\mathcal{UD}_n(12\ldots k)|=|\mathcal{UD}_n(21\ldots k)|$   and  $|\mathcal{UD}_{2n}(12 \ldots (k-1) k)|=|\mathcal{UD}_{2n}(12\ldots k(k-1))|$ for all  $n$ and all $k$.


In this paper, we are concerned with the enumeration of $4123$-avoiding down-up and up-down alternating
permutations of even and odd length. We  establish     bijections between the set  $\mathcal{DU}_{2n}(4123)$ and
the set of standard Young tableaux of shape $(n,n,n)$, and between  the set  $\mathcal{DU}_{2n-1}(4123)$ and   the set of shifted  standard
Young tableaux of shape $(n+1, n, n-1)$ via an intermediate structure of Yamanouchi words. Consequently,  we prove the conjectures, posed by Lewis \cite{Lewis2}, that $|\mathcal{UD}_{2n}(1432)|=|\mathcal{UD}_{2n}(1234)|$ and $|\mathcal{UD}_{2n+1}(1432)|=|\mathcal{UD}_{2n+1}(2143)|$ in the sense that
$|\mathcal{UD}_n(1432)|=|\mathcal{DU}_n(4123)|$ by the operation of
complement.


Applying the  bijections between $4123$-avoiding  down-up alternating permutations and   standard Young tableaux, we show that
$4123$-avoiding  up-down alternating permutations of  length $2n+1$  are in one-to-one correspondence with   standard Young tableaux of shape $(n+1,n,n-1)$, and $4123$-avoiding up-down alternating permutations of length $2n$  are in bijection  with  shifted  standard Young tableaux of shape $(n+2, n, n-2)$. By the hook length formula for shifted standard Young tableaux \cite{ck},  we derive that  the number of shifted standard Young tableaux  of shape $(n+2,n,n-2)$ is equal to ${2(3n)!\over n!(n+1)!(n+2)!}.$ As a result, we deduce that
$|\mathcal{UD}_{2n}(4123)|=|\mathcal{UD}_{2n}(1234)| $ and   $|\mathcal{UD}_{2n+1}(4123)|=|\mathcal{UD}_{2n+1}(1234)|$, as conjectured by Lewis \cite{Lewis2}.

The paper is organized as follows. In Section $2$, we introduce the bijections between the set $\mathcal{DU}_{2n}(4123)$ and the set of standard Young tableaux
of shape $(n,n,n)$, and between  the set  $\mathcal{DU}_{2n-1}(4123)$ and   the set of shifted  standard Young tableaux of shape $(n+1, n, n-1)$. In Section 3,  we construct bijections between the set
$\mathcal{UD}_{2n+1}(4123)$  and the set of  standard Young tableaux of shape $(n+1,n,n-1)$, and between the set $\mathcal{UD}_{2n}(4123)$  and the set of   shifted standard Young tableaux of shape $(n+2,n,n-2)$.

\section{$4123$-avoiding down-up alternating permutations }
In this section, we aim to establish    bijections between the set  $\mathcal{DU}_{2n}(4123)$ and the set of standard Young tableaux of shape $(n,n,n)$, and between
the set  $\mathcal{DU}_{2n-1}(4123)$ and   the set of shifted  standard Young tableaux of shape $(n+1, n, n-1)$.

\subsection{Preliminaries}
In this subsection, we   give some
definitions and notations  that will be used throughout the rest of the paper.
Moreover, we   provide two lemmas that will be essential in the construction of the bijections.

Given a word $w=w_1w_2\ldots w_n$ on the alphabet $\{1,2,\ldots\}$, we define $c_i$ to be the number of   occurrences of the letter $i$
in $w$  and the  {\em type} of the word $w$ to
be the sequence $(c_1, c_2, c_3, \ldots)$.  The subword
$w_1w_2\ldots w_j$ is said to be a {\em left} subword for $1\leq j\leq n$. Similarly, the subword $w_{n+1-j}w_{n+2-j}\ldots w_{n}$ is said to be a {\em right} subword for $1\leq j\leq n $.  The word $w$ is said to be a  {\em Yamanouchi } word  if  every  left subword of $w$ does not contain more occurrences of the letter $i+1$ than that of $i$    for every $i\geq 1$.    If every subword of $w$  contains more occurrences of the letter $i$ than that of $i+1$  for every $i\geq 1$, then the  word $w$ is said to be a {\em
shifted Yamanouchi} word. Similarly, the word $w$ is said to be a  {\em  skew Yamanouchi }  word if  every right subword of $w$   contains more occurrences of the letter $i+1$ than that of $i$  for every $i\geq 1$. For instance, it is easy to check that     the word $w=11231223$ is a   Yamanouchi word of type $(3,3,2)$, the word $u=1121213123$ is a shifted Yamanouchi word of type $(5,3,2)$, and the word $v=1231323233$ is a skew Yamanouchi word of type $(2,3,5)$.


A {\em partition} $\lambda$ of a positive integer $n$ is defined to
be a sequence $(\lambda_1, \lambda_2, \ldots, \lambda_m)$ of
nonnegative  integers such that $\lambda_1+\lambda_2+\ldots
\lambda_m=n$ and $\lambda_1\geq \lambda_2\ldots \geq \lambda_m$.
Given a partition $\lambda=(\lambda_1, \lambda_2, \ldots,
\lambda_m)$, the {\em (ordinary) Young diagram} of shape $\lambda$ is the
left-justified array of $\lambda_1+\lambda_2+\ldots+\lambda_m$ boxes
with $\lambda_1$ boxes in the first row, $\lambda_2$ boxes in the
second row, and so on.  If $\lambda$ is a partition with distinct
parts then the {\em shifted} Young diagram of shape $\lambda $ is an
array of cells with $m$ rows, each row indented by one cell to the
right with respect to the previous row, and $\lambda_i $ cells in
row $i$.

If $\lambda$ is a  Young diagram with $n$ boxes, a {\em   standard
Young tableau } of shape $\lambda$ is a filling of the boxes of
$\lambda$ with $[n]$ so that each element appears in exactly one box
and entries increase along rows and columns.   We identify boxes in
Young diagrams and tableaux using matrix coordinates. For example,
the box in the first row and second column is numbered $(1,2)$.


Let $n_1,n_2, \ldots, n_k$ be positive integers with $n_1\geq n_2  \ldots \geq n_k $. There exists a bijection $\chi$ between the set of standard Young
tableaux    of shape $(n_1, n_2, \ldots, n_k)$ and  the set of Yamanouchi  words of type $(n_1,n_2, \ldots, n_k)$ \cite{eu}.  Given a standard Young
tableau $T$, we associate $T$ with a word $\chi(T)$
by letting the $j$-th letter be the row index of
the box of $T$ containing the number $j$.    On the other hand, given
a Yamanouchi  word $w$, it is straightforward to recover the
corresponding tableaux $\chi^{-1}(w)$ by letting the $i$-th row
contain the indices of letters of $w$ that are equal to $i$. For
example, the associated standard Young tableau of the Yamanouchi
word $112311223$  is illustrated as follows:
\begin{center}
\parbox[t]{3cm}{ \young(1256,378,49) }
\end{center}

Clearly,   for any
shifted standard Young tableau $T$ of shape $(n_1, n_2, \ldots, n_k)$, where $n_1>n_2\ldots>n_k$, the
word $\chi(T)$ is a  shifted  Yamanouchi  word of type $(n_1,n_2, \ldots, n_k)$.  More precisely,  the map $\chi$ is a bijection between the set of  shifted standard Young tableaux  of shape $(n_1, n_2, \ldots, n_k)$ and the  set of  shifted Yamanouchi  words
of type $(n_1, n_2, \ldots, n_k)$. For example, let $T$ be a shifted standard Young tableau shown in Figure \ref{fi.2}.  By applying the map $\chi$, we obtain the shifted Yamanouchi  word $\chi(T)=1121213123$ of type $(5,3,2)$.
\begin{figure}[h,t]
\begin{center}
\begin{picture}(50,50)
\setlength{\unitlength}{1mm}

\put(0,10){\framebox(5,5) {1}} \put(5,10){\framebox(5,5) {2}}\put(10,10){\framebox(5,5) {4}}\put(15,10){\framebox(5,5){6}} \put(20,10){\framebox(5,5){8}}

\put(5,5){\framebox(5,5) {3}}\put(10,5){\framebox(5,5) {5}}\put(15,5){\framebox(5,5) {9}}

\put(10,0){\framebox(5,5) {7}}\put(15,0){\framebox(5,5) {10}}
\end{picture}
\end{center}
\caption{The shifted standard Young tableau $T$.}\label{fi.2}
\end{figure}
Note that  the map $\chi$ is not  a bijection between skew Yamanouchi words and skew  standard Young tableaux.


Let  $w=w_1w_2\ldots w_n$ be a    word on the alphabet $\{1,2,3\}$.
The left subword $w_1w_2\ldots w_j$ is called the {\em initial run} of $w$
if $w_{j+1}$ is the leftmost letter of $w$ that is equal to
$3$.  Similarly, the right subword $w_{n+1-j}w_{n+2-j}\ldots w_{n}$  is said to be the {\em final run} of $w$ if
$w_{n-j}$ is the rightmost letter    equal to $1$. As usual,  the {\em length} of any word $v$ is defined to be the number of entries of $v$.
For instance,  the word
$w=121211231323233$ has the initial run of length $7$ and the final run of length $6$.   Denote by $\alpha(w)$   the length of the initial run  of $w$.



In order to establish the bijections between $4123$-avoiding down-up
alternating permutations  and   standard Young tableaux, we consider the
following two sets.   Given a  permutation $\pi=\pi_1\pi_2\ldots
\pi_{n}\in \mathcal{S}_n$ and a   word $w=w_1w_2\ldots w_n$ on the alphabet $\{1,2,3\}$, let $$
\mathcal{A}(\pi)=\{0\}\cup \{k\mid \exists i<j  \,\,\mbox{ s.t.} \,\,
\pi_i=k, \pi_j={k+1}\, \mbox{and} \,\, k\leq \pi_1-2\},$$
and
$$
\mathcal{B}(w)=\{0\}\cup \{k \mid w_{k}w_{k+1}=12 \,\,\mbox{and}\,\, k\leq
\alpha(w)-2\},
$$
respectively.
For example, let   $\pi=658397(10)142$ and $w=121211231323233$. We have
$\mathcal{A}(\pi)=\{0,1,3\}$ and $\mathcal{B}(w)=\{0,1,3\}$.

Let $\pi=\pi_1\pi_2\ldots \pi_n$ be a permutation.
Suppose that $\mathcal{A}(\pi)=\{a_0, a_1,\ldots, a_p\}$, where $p\geq 0$ and  $0=a_0<a_1\ldots <a_p$. Define $a_{p+1}$ to be $\pi_1$. Similarly, given a word $w$, if $\mathcal{B}(w)=\{a_0, a_1,\ldots, a_p\}$, then we define $a_{p+1}$ to be $\alpha(w)$. Obviously, according to the definitions of  $\mathcal{A}(\pi)$ and $\mathcal{B}(w)$, we have $a_p<a_{p+1}$.

Given a permutation $\sigma\in \mathcal{S}_n$ and an element $a\in
[n+1]$, there is a unique permutation $\pi=\pi_1\pi_2\ldots
\pi_{n+1}\in \mathcal{S}_{n+1}$ such that $\pi_1=a$ and the word
$\pi_2\pi_3\ldots \pi_{n+1}$ is order-isomorphic to $\sigma$. We
denote this permutation by $a\rightarrow \sigma$.  Let $a,b\in [n+2]$
with $b<a$. Denote by $(a,b)\rightarrow \sigma$ the permutation
$\pi=\pi_1\pi_2\ldots \pi_{n+2}$ such that $\pi_1=a$, $\pi_2=b$ and
$\pi_3\pi_4\ldots \pi_{n+2}$ is order-isomorphic to $\sigma$. More
precisely, the permutation $\pi$ is defined by
$$
\pi_i=\left\{\begin{array}{ll} a, & \,\,  i=1,\\
b, & \,\,  i=2,\\
\sigma_{i-2}, &\,\, \sigma_{i-2}<b,\\
\sigma_{i-2}+1, &\,\, b\leq \sigma_{i-2}<a-1,\\
\sigma_{i-2}+2, &\,\, \sigma_{i-2}\geq a-1.
\end{array}\right.
$$
Note that the permutation $(a,b)\rightarrow \sigma$ is identical with the permutation $a\rightarrow (b\rightarrow \sigma )$.

We conclude this subsection  with two lemmas that will be essential in the construction
of the bijections between $4123$-avoiding down-up alternating
permutations and standard Young tableaux. First, we present the
following  simple  observation that will be of use in the subsequent
proofs of lemmas.

\begin{observation}\label{obser}
Let $\sigma=\sigma_1\sigma_2\ldots \sigma_n\in \mathcal{S}_n$ with
$\mathcal{A}(\sigma)=\{a_0, a_1,  \ldots, a_p\}$, where $p\geq 0$ and
$0=a_0<a_1<a_2\ldots<a_p<a_{p+1}=\sigma_1$.  For
any integers $r$ and $s$ with $a_j<r<s\leq a_{j+1}$, suppose
that $\sigma_\ell=r$ and $\sigma_m=s$. Then we have $\ell>m$.
\end{observation}


\begin{lemma} \label{lem4123}
Let $\sigma=\sigma_1\sigma_2\ldots \sigma_n\in \mathcal{DU}_n(4123)$ with
$\mathcal{A}(\sigma)=\{a_0, a_1,   \ldots, a_p\}$, where $p\geq 0$ and
$0=a_0<a_1<a_2\ldots<a_p<a_{p+1}=\sigma_1$.  If
$\pi =(a,b)\rightarrow \sigma $ is a permutation in
$\mathcal{DU}_{n+2}(4123)$, then $b\leq \sigma_1$ and there exists an
integer $j$ such that    $a_{j+1}+2\geq a>b\geq a_j+1$.
\end{lemma}
\begin{proof} Let $\pi =\pi _1\pi _2\ldots \pi _{n+2}$.  Recall  that
$\pi_1=a$ and $\pi_2=b$. Since $\pi$ is a down-up alternating
permutation and $\pi=(a,b)\rightarrow \sigma$, we have $b\leq  \sigma_1=a_{p+1}$. Choose the integer $j$ such that $a_{j+1}\geq b \geq
a_{j}+1$.  We claim that
$a\leq a_{j+1}+2$. Suppose  that $a> a_{j+1}+2$. Then we
have two cases.   If $j=p$, then the subsequence $ab(a_{p+1}+1)
(a_{p+1}+2)$ is order-isomorphic to  $4123$ in $\pi$.  If $j<p$,
 then according to the definition of $\mathcal{A}(\sigma)$, there exists
integers $l$ and $m$ with $l<m$ such that $\sigma_l=a_{j+1}$ and
$\sigma_{m}=a_{j+1}+1$. Note that $\pi_{l+2}=\sigma_l+1=a_{j+1}+1$ and
$\pi_{m+2}=\sigma_m+1=a_{j+1}+2$. Then the subsequence
$\pi_1\pi_2\pi_{l+2}\pi_{m+2}$ forms a $4123$ pattern in $\pi$. This yields a contradiction.
Hence, we conclude    that $a_{j}+1\leq b<a\leq a_{j+1}+2$. This
completes the proof.
\end{proof}


\begin{lemma}\label{lem2}
Let $\sigma=\sigma_1\sigma_2\ldots \sigma_n\in \mathcal{DU}_n(4123)$  with
$\mathcal{A}(\sigma)=\{a_0, a_1,  \ldots, a_p\}$, where $p\geq 0$ and $
0=a_0<a_1<a_2\ldots<a_p<a_{p+1}=\sigma_1$.    Let
$a,b$ be two integers such that $a_{j+1}+2\geq a>b\geq a_j+1$ and
$b\leq \sigma_1$. Then $\pi=(a,b)\rightarrow \sigma$
is a permutation in $\mathcal{DU}_{n+2}(4123)$ satisfying that
\begin{itemize}

 \item[{\upshape (\rmnum{1})}]  if $b=a_j+1$ and $j\geq 1$, then we have $\mathcal{A}(\pi)=\{a_0, a_1, \ldots, a_{j-1}, b\}$ when $a>b+1$ and $\mathcal{A}(\pi)= \{a_0, a_1, \ldots, a_{j-1}\}$ when $a=b+1$;
\item[{\upshape (\rmnum{2})}]  otherwise, we have $\mathcal{A}(\pi)=\{a_0, a_1, \ldots, a_j, b\}$ when $a>b+1$ and  $\mathcal{A}(\pi)=\{a_0, a_1, \ldots, a_j\}$ when $a=b+1$.
\end{itemize}
\end{lemma}
\begin{proof}  Since $b\leq \sigma_1$ and $a>b$, the permutation $\pi$ is a down-up alternating permutation.  Now we proceed to show that $\pi$ avoids the pattern $4123$.
Let $\pi=\pi_1\pi_2\ldots \pi_{n+2}$. Suppose that there is a
subsequence $\pi_k\pi_l\pi_{m}\pi_{q}$ with $k<l<m<q$ which is
order-isomorphic to $4123$. Note that the subsequence $\pi_3\ldots \pi_{n+2}$  is order-isomorphic to $\sigma$. This implies that the subsequence $\pi_3\ldots \pi_{n+2}$ avoids the pattern $4123$.    So we have either $k=1$ or $k=2$.
  Suppose that $k=2$. Since $\pi_2<\pi_3$,   the subsequence  $\pi_3\pi_l\pi_{m}\pi_{q}$ is  order-isomorphic to the pattern $4123$. This contradicts with the fact that  the subsequence $\pi_3\ldots \pi_{n+2}$ avoids the pattern $4123$.  Hence, we must have $k=1$.
    Suppose that $k=1$ and $l> 2$. Since $\pi_3\geq \sigma_1+1$ and $\pi_1=a\leq a_{j+1}+2\leq a_{p+1}+2= \sigma_1+2$, the subsequence $\pi_3\pi_l\pi_{m}\pi_{q}$ is an instance of  $4123$, which   contradicts  with the fact that the subsequence $\pi_3\ldots \pi_{n+2}$ is $4123$-avoiding.
     Thus, it follows that $k=1$ and $l=2$. Recall that $\pi_1=a$, $\pi_2=b$, which  implies that
$ b<\pi_{m}<\pi_{q}<a $.  From this, we deduce that $  a_j \leq
b-1<  \pi_m-1<\pi_q-1< a-1\leq a_{j+1}+1$.  Note that
$\pi_{m}=\sigma_{m-2}+1$  and $\pi_{q}=\sigma_{q-2}+1$.  So we have
$a_j+1\leq  \sigma_{m-2}<\sigma_{q-2}\leq a_{j+1}$ and $m<q$. This contradicts with
Observation \ref{obser}.   Thus, the permutation $\pi$ is in
$\mathcal{DU}_{n+2}(4123)$.

It remains to prove that the permutation $\pi$ verifies the points
(\rmnum{1}) and (\rmnum{2}). We claim that all the elements of the set $\mathcal{A}(\pi)$ are not larger than $b$. Suppose that  $k$ is a nonnegative integer such that
$k\in \mathcal{A}(\pi)$ and $k\geq b+1$. It follows that $k\leq \pi_1-2=a-2$ from the definition of $\mathcal{A}(\pi)$.  Moreover, there exists
integers $l$ and $m$ with $l<m$ such that $\pi_l=k$ and  $\pi_m=k+1$.     It is easy to check  that the subsequence  $\pi_1\pi_2\pi_l\pi_m$ forms a pattern $4123$. This contradicts with the fact that  $\pi\in {DU}_{n+2}(4123)$.  Hence, we have completed the proof of the claim.

If $a>b+1$, then we have $b\in \mathcal{A}(\pi)$ since $b+1$
appears right to $b$ in $\pi$ and $b\leq a-2=\pi_1-2$. If $a=b+1$,
then $b\notin \mathcal{A}(\pi)$ since $b+1$ appears left to $b$ in
$\pi$.  Moreover, when $b> 1$, since the entry $b$ appears left to the entry $b-1$ in $\pi$, we have $ b-1\notin \mathcal{A}(\pi)$. Finally, it's easy to check from the definitions  of $\mathcal{A}(\pi)$ and $\mathcal{A}(\sigma)$ that   for any integer $k$ with $k<b-1$, we have $k\in \mathcal{A}(\pi)$ if and only if $k\in \mathcal{A}(\sigma)$.   This completes the proof.
\end{proof}



\subsection{The bijections}

Denote by $\mathcal{P}_n$ and $\mathcal{Q}_n$ the set of Yamanouchi words on the
alphabet $ \{1,2,3\}$ of type $(n,n,n)$  and the set of skew Yamanouchi words on the
alphabet $ \{1,2,3\}$ of type $(n-1,n,n+1)$, respectively. Let $\mathcal{P}$ (resp. $\mathcal{Q}$) be the  union of $\mathcal{P }_n$ (resp. $\mathcal{Q}_n$) for all $n\geq 1$.  Similarly, denote by $\mathcal{DU}(4123)$ the union of $\mathcal{DU}_{n}(4123)$ for all $n\geq 1$.


Now we proceed to construct a    map $\phi$ from the set
$ \mathcal{DU}(4123)$ to  the set $\mathcal{P}\cup \mathcal{Q}$  in terms of a recursive procedure,  such that  for all $m\geq 1$,  $\phi$ is a map from $\mathcal{DU}_{m}(4123)$ to $\mathcal{Q}_n$ when $m=2n-1$  and from   $\mathcal{DU}_{m}(4123)$ to $\mathcal{P}_n$ when $m=2n$.
 Let   $\pi=\pi_1\pi_2\ldots \pi_{m}\in
\mathcal{DU}_{m}(4123)$.
 For $m=1$, we define
$\phi(1)=233$. For $m=2$, define  $\phi(21)=123$.
 For $m\geq 2$,  let $\sigma= \sigma_1\sigma_2\ldots
\sigma_{m-2}\in
\mathcal{DU}_{m-2}(4123)$  such that $\pi=(a,b)\rightarrow\sigma$ where $a=\pi_1$ and $b=\pi_2$.
Assume that  we have obtained  the  word $v=\phi(\sigma)=v_1v_2\ldots v_{3n-3}$. Then we  construct a
 word $w=\phi(\pi)=w_1w_2\ldots w_{3n}$ from $v$ by   inserting two consecutive letters $12$
 immediately left to $v_{b}$ and  one letter  $3$ immediately left to $v_{a-1}$.
 Namely,  $w$ is a word with $w_b=1$, $w_{b+1}=2$ and $w_{a+1}=3$ such that  we can recover  the word $v$ by  removing the entries $w_{b}$, $w_{b+1}$ and $w_{a+1}$ from $w$.


For example,
consider the $4123$-avoiding down-up alternating permutation
$\pi=63758142$. Let $\sigma=546132$, $\sigma'=4132$ and $\sigma''=21$. Clearly,  we have $\pi=(6,3)\rightarrow \sigma$, $\sigma=(5,4)\rightarrow \sigma' $ and $\sigma'=(4,1)\rightarrow \sigma''$. Applying the map $\phi$ recursively, we can obtain $\phi(\sigma'')=123$, $\phi(\sigma')=121233$, $\phi(\sigma)=121  12   3 233$, and $\phi(\pi)=12  12 11  3 23233$.





Conversely, we  define a  map $\psi$ from the set  $\mathcal{P} \cup \mathcal{Q} $ to the set $\mathcal{DU} (4123)$,  such that for all $n\geq 1$, $\psi$ is a map from $\mathcal{P}_n$ to $\mathcal{DU}_{2n}(4123)$   and from $\mathcal{Q}_n$ to $\mathcal{DU}_{2n-1}(4123)$.
Given a   word $w=w_1w_2\ldots
w_{3n}\in \mathcal{P} \cup \mathcal{Q} $,  we wish to recover a $4123$-avoiding down-up alternating
permutation $\psi(w)$ in terms of a recursive procedure. If $w=233$, we define $\psi(w)=1$.
  If $w=123$, then
define $\psi(w)=21$.   For $n\geq 2$, let $a=\alpha(w)$.
Now we proceed to construct an ordered pair $(v,b)$ from $w$  by
the following procedure.
\begin{itemize}
\item     If $w_{a+2}=3$, then let $b$ be the largest element of $\mathcal{B}(w)$  and     $v$  be a
word obtained from $w$ by removing $w_{b}$, $w_{b+1}$ and $w_{a+1}$
from $w$. For example, let $w=12    1    233$. It is easy to check that $a=\alpha(w)=4$, $w_{6}=3$ and $\mathcal{B}(w)=\{0,1\}$. Thus we have $b=1$ and $v=123$.

\item  If $w_{a+2}\neq 3$, then find the largest   integer $q$ such that   $q\leq a-1$ and  $w_{q}w_{q+1}=12$.
 Let $b= q$  and $v$  be a
word obtained from $w$ by removing $w_{b}$, $w_{b+1}$ and $w_{a+1}$
from $w$. For example, let $w=12  12 11  3 23233$.   It is easy to check that $a=\alpha(w)=6$ and $w_{8}=2\neq 3$. Thus  we have $b=3$ and $v=121123233$.
 \end{itemize}
Finally, we define $\psi(w)=(a,b)\rightarrow \psi(v) $.





For instance, let $w=12  12 11  3 23233$.
By applying the map $\psi$ recursively, we   construct a permutation  $\pi$
 as follows:
$$
\begin{array}{llllllll}
\\
w=&12{\bf 12}11{\bf 3}23233 &\Longrightarrow  & 121{\bf 12}{\bf 3}233 &
\Longrightarrow &
{\bf 12}12{\bf 3}3& \Longrightarrow &123,\\
\pi=& {\bf 63}758142 &\Longleftarrow  &{\bf 54}6132 & \Longleftarrow & {\bf
41}32&
\Longleftarrow& 21.
\end{array}
$$



Our next goal is to show that the map $\phi$ is a bijection between the set $\mathcal{DU}_{2n}(4123)$ and the set $\mathcal{P}_n$.
 Analogously,   the map $\phi$ induces  a bijection between the  set $\mathcal{DU}_{2n-1}(4123)$ and the set $\mathcal{Q}_n$.





\begin{proposition}\label{phi}
For any  permutation
$\pi=\pi_1\pi_2\ldots \pi_{2n}\in \mathcal{DU}_{2n}(4123)$, the word $\phi(\pi)$ is a Yamanouchi word on the alphabet $\{1,2,3\}$ of type $(n,n,n)$ satisfying   $\pi_1=\alpha(\phi(\pi))$ and
$\mathcal{A}(\pi)=\mathcal{B}(\phi(\pi))$.
\end{proposition}
\begin{proof}  We   proceed     by induction on $n$. For  $n=1$, we have  $\phi(21)=123$, which is   a Yamanouchi word of type $(1,1,1)$ with the property that $\alpha(\phi(21))=2$ and $\mathcal{A}(21)=\mathcal{B}(123)=\{0\}$.      For $n\geq 2$, choose  $\sigma= \sigma_1\sigma_2\ldots
\sigma_{2n-2}\in
\mathcal{DU}_{2n-2}(4123)$  such that $\pi=(a,b)\rightarrow\sigma$ where $a=\pi_1$ and $b=\pi_2$.  Suppose that
  $\mathcal{A}(\sigma)=\{a_0, a_1, \ldots, a_p\}$, where $p\geq 0$ and  $
0=a_0<a_1<a_2<\ldots<a_p<a_{p+1}=\sigma_1$.     Assume that $v=v_1v_2\ldots v_{3n-3}=\phi(\sigma)$ is a Yamanouchi word  on
the alphabet $ \{1,2,3\}$ of type $(n-1,n-1,n-1)$  such that
$\alpha(v)=\sigma_1$ and $\mathcal{B}(v)=\mathcal{A}(\sigma)$.
 We aim  to show that $w=\phi(\pi)$ is a Yamanouchi word  on
the alphabet $ \{1,2,3\}$ of type $(n,n,n)$ satisfying
$\alpha(w)=\pi_1$ and $\mathcal{B}(w)=\mathcal{A}(\pi)$.  By the construction of the word $w$,  it is easy to check that each left subword of $w$ does not contain more occurrences of the letter $i+1$ than that of $i$ for $i=1,2$. This implies that $w$ is a Yamanouchi word of length $3n$. Let $w=w_1w_2\ldots w_{3n}$.

By Lemma \ref{lem4123}, since $\pi=(a,b)\rightarrow \sigma$, we can choose the integer $j$ such that
  $a_{j+1}+2\geq a>b\geq a_{j}+1$.
 Since $a\leq a_{j+1}+2\leq a_{p+1}+2= \sigma_1+2=\alpha(v)+2$, there is no occurrence of the letter $3$ in the subword $v_{1}v_2\ldots v_{a-2}$ according to the definition of $\alpha(v)$ . This implies that there is no occurrence of the letter $3$ in the subword $w_{1}w_2\ldots w_{a}$ according to the construction of the word $w$.  Meanwhile, we have $w_{a+1}=3$.  So the obtained word $w$ has  the initial run of length $a$, that is, $\alpha(w)=a=\pi_1$.  It remains to show  that
$\mathcal{A}(\pi)=\mathcal{B}(w)$.  Recall that $\pi=(a,b)\rightarrow \sigma$ and $\mathcal{A}(\sigma)=\mathcal{B}(v)=\{a_0, a_1, \ldots, a_p\}$. By Lemma \ref{lem2}, in order to verify $\mathcal{B}(w)= \mathcal{A}(\pi)$, it suffices to show that
\begin{itemize}
   \item[{\upshape (\rmnum{1})}$^{'}$]  if $b=a_j+1$ and $j\geq 1$, then we have $\mathcal{B}(w)=\{a_0, a_1, \ldots, a_{j-1}, b\}$ when $a>b+1$ and $\mathcal{B}(w)= \{a_0, a_1, \ldots, a_{j-1}\}$ when $a=b+1$;
   \item[ {\upshape (\rmnum{2})}$^{'}$] otherwise, we have $\mathcal{B}(w)=\{a_0, a_1, \ldots, a_j, b\}$ when $a>b+1$ and  $\mathcal{B}(w)=\{a_0, a_1, \ldots, a_j\}$ when $a=b+1$.
\end{itemize}





   We claim that all the elements of the set $\mathcal{B}(w)$ are not larger than $b$. Suppose that  $k$ is a nonnegative integer  such that $k\in \mathcal{B}(w)$ and $k\geq b+1$.  According to the definition of the set $\mathcal{B}(w)$, we have  $w_kw_{k+1}=12$ and $k\leq \alpha(w)-2=a-2$.
   Since $w_{b+1}=2$,  we have $k\neq b+1$.   Now suppose that  $b+2\leq k\leq a-2$.   Clearly, we have   $v_{k-2}v_{k-1}=w_{k}w_{k+1}=12$ by the construction of $w$.   Since $k-2\leq a-4\leq a_{j+1}-2\leq \alpha(v)-2 $, we have $k-2\in \mathcal{B}(v)$. However,  we  have $a_j+1\leq b\leq  k-2\leq a_{j+1}-2$, which implies that  $k-2\notin \mathcal{B}(v)$.  Hence, the claim is proved.

If $a=b+1$, then  we have $b\notin \mathcal{B}(w)$ since $b=a-1=\alpha(w)-1$.  If  $a>b+1$, then we have $b\in \mathcal{B}(w)$ since $w_bw_{b+1}=12$ and $b<a-1\leq \alpha(w)-1$. Since $w_b=1$, we have $b-1\notin \mathcal{B}(w)$ when $b>1$.




In order to verify    (\rmnum{1})$^{'}$ and (\rmnum{2})$^{'}$, it remains to show that  for any nonnegative integer $k$ with $k<b-1$,   we have $k\in \mathcal{B}(w)$ if and only if $k\in \mathcal{B}(v)$.
According to the construction of the word $w$,  we have $w_{k}w_{k+1}=v_{k}v_{k+1}$.  By Lemma \ref{lem4123}, we have
 $b\leq \sigma_1$.  Note that   $k<b-1\leq \sigma_1-1= \alpha(v)-1$ and $k<b-1<a-1\leq \alpha(w)-1$.   Thus, we have $k\in \mathcal{B}(w)$ if and only if $k\in \mathcal{B}(v)$ by the definitions of   $\mathcal{B}(w)$ and $\mathcal{B}(v)$. This completes the proof.
 \end{proof}



 \begin{proposition}\label{bar-phi}
 For  any Yamanouchi word $w=w_1w_2\ldots w_{3n}$ on the
alphabet $ \{1,2,3\}$ of type $(n,n,n)$,  the permutation $\psi(w)$ is in $\mathcal{DU}_{2n}(4123)$ such that the first entry of the permutation  $\psi(w)$ is equal to
 $ \alpha(w)$ and
$\mathcal{A}(\psi(w))=\mathcal{B}(w)$.
\end{proposition}
\begin{proof} We proceed   by induction on $n$.  For the case $n=1$, we have
 $\psi(123)=21$.    For $n\geq 2$,  let  $a=\alpha(w)$. According to the definition of $\psi$, we can construct an ordered pair  $(v,b)$  from $w$.

 First, we shall show that the word $v$ is     a
Yamanouchi word on the alphabet $\{1,2,3\}$ of type $(n-1,n-1,n-1)$. Suppose that $\mathcal{B}(w)=\{a_0, a_1,  \ldots,
a_p\}$, where $p\geq 0$ and  $0=a_0<a_1<\ldots<a_p<a_{p+1}=\alpha(w)$.  For the case $w_{a+2}=3$, we have $b=a_p$ by the definition of $\psi$. Since $w$ is a Yamanouchi word with $\alpha(w)=a$, $w_{a+1}=3$ and $w_{a+2}=3$, there are at least two occurrences of $2$'s left to $w_{a+1}$ and the first  occurrence of $2$ is preceded immediately by   $1$.  This guarantees that  there exists at least one subword $w_kw_{k+1}=12$ with $k\leq a-2=\alpha(w)-2$. This yields that $\mathcal{B}(w)\neq \{0\}$ according to the definition of $\mathcal{B}(w)$. Hence we have $b=a_p>0$. Moreover, by definition  we have $b=a_p\leq \alpha(w)-2=a-2$.  For the case $w_{a+2}\neq 3$, the property of the Yamanouchi word guarantees that there exists at least one subword  $w_kw_{k+1}=12$ with $k\leq a-1$. Thus, in either case,  we have $a>b>0$. Note that $w_b=1, w_{b+1}=2$ and $w_{a+1}=3$. According to the definition of $\psi$, $v$ is obtained from $w$ by removing $w_b$, $w_{b+1}$ and $w_{a+1}$. It is easy to check that any left subword of $v$ does not contain more occurrences of  the letter $i+1$ than that of $i$ for $i=1,2$.  Thus  the obtained  word $v$ is   a Yamanouchi word of type $(n-1,n-1,n-1)$. Let $v=v_1v_2\ldots v_{3n-3}$.
Suppose that
 $\mathcal{B}(v)=\{c_0, c_1,  \ldots,
c_m\}$, where $m\geq 0$ and  $0=c_0<c_1<\ldots <c_{m}<c_{m+1}=\alpha(v)$.

We claim that $\alpha(v)\geq   a-2$. According to the definition of $\alpha(w)$, there is no occurrence of the letter $3$ in the subword $w_1w_2\ldots w_{a}$.  Thus,  by the construction of $v$,   there is no occurrence of the letter $3$ in the subword $v_1v_2\ldots v_{a-2}$. This implies that the word $v$ has the initial run of length at least $a-2$, that is,   $\alpha(v)\geq a-2$.


 Assume that  the permutation $\psi (v)$ is
in $\mathcal{DU}_{2n-2}(4123)$  such that the first element of $\psi(v)$ equals
$\alpha(v)$ and $\mathcal{A}(\psi(v))=\mathcal{B}(v)$.
Now we proceed
to show that   $\psi(w)$ is a down-up alternating permutation in $\mathcal{DU}_{2n}(4123)$ such that
    the first element of
 $\psi(w)$  is equal to $\alpha(w)$ and  $\mathcal{A}(\psi (w))=\mathcal{B}(w)$.
Recall that $\psi(w)=(a,b)\rightarrow \psi(v)$ and $a=\alpha(w)$.  This yields that the first element of $\psi(w)$ is equal to $\alpha(w)$.  Now we proceed to show that $\psi(w)\in \mathcal{DU}_{2n}(4123)$ such that $\mathcal{B}(w)=\mathcal{A}(\psi(w))$. We have two cases: $w_{a+2}=3$ or $w_{a+2}\neq 3$.

  If $w_{a+2}=3$,  then we have $\alpha(v)=a-2$ since  $v_{a-1}=3$. By  the definition of $\psi$, we have $b=a_p$. By the definition of  $\mathcal{B}(w)$,  this ensures that
         there is no subword $w_kw_{k+1}=12$ in the subword $w_{b+2}\ldots w_{a-1}$.  Thus   there is no subword    $v_kv_{k+1}=12$ in the subword $v_{b}\ldots v_{a-3}$ by the construction of $v$. Thus we have    $c_m\leq b-1$ according to the definition of $\mathcal{B}(v)$.   Since $c_{m+1}+2=\alpha(v)+2= a>b\geq c_m+1$ and $b=a_p\leq\alpha(w)-2= a-2=\alpha(v)$,  by Lemma \ref{lem2},    we can verify  that $\psi(w)=(a,b)\rightarrow \psi(v)$ is in $\mathcal{DU}_{2n}(4123)$.



  We next prove that $\mathcal{A}(\psi(w))=\mathcal{B}(w)$ for the case $w_{a+2}=3$.   Let $k$ be a nonnegative  integer  with $k< b-1$. From the construction of $v$, we have $v_kv_{k+1}=w_kw_{k+1}$. Since $a_p\leq \alpha(w)-2$ and $b=a_p$,  we have $k<b-1=a_p-1\leq \alpha(w)-3 $ and $k\leq \alpha(w)-4=\alpha(v)-2$.   By the definitions of  $\mathcal{B}(w)$ and $\mathcal{B}(v)$,   it follows that  $k\in \mathcal{B}(w)$ if and only if $k\in \mathcal{B}(v)$.  Observe  that $w_{b}=1$. This ensures   that $b-1\notin \mathcal{B}(w)$ when $b\geq 2 $ by the definition of  $\mathcal{B}(w)$.  Hence we deduce that    if  $c_m=b-1$ and $m\geq 1$ then we have  $ \{a_0, a_1, \ldots, a_{p-1} \}=\{c_0, c_1, \ldots, c_{m-1}\}$; otherwise, we have $ \{a_0, a_1, \ldots, a_{p-1}\}=\{c_0, c_1, \ldots, c_{m}\}$.  Note that $\psi(w)=(a,b)\rightarrow \psi(v)$, $\mathcal{A}(\psi(v))=\mathcal{B}(v)=\{c_0, c_1, \ldots, c_m\}$, and $a-2\geq b\geq c_m+1$.     By Lemma \ref{lem2}, we can verify that if  $c_m=b-1$ and $m\geq 1$, then $\mathcal{A}(\psi (w))=\{c_0, c_1, \dots, c_{m-1}, b\}   $; otherwise, $\mathcal{A}(\psi (w))=\{c_0, c_1, \dots, c_{m}, b\}   $. Since $b=a_p$, we deduce that $\mathcal{A}(\psi (w))=\mathcal{B}(w)$.



   If $w_{a+2}\neq 3$,     then we have $\alpha(v)\geq a-1$ since $v_{a-1}\neq 3$. By the definition of $\psi$, we have $b\leq a-1$. This yields that $b\leq \alpha(v)=c_{m+1}$. Choose the integer  $j$ such that $c_{j+1}\geq b\geq c_{j}+1$.
 According to the definition of $\mathcal{B}(w)$,   there is no subword   $w_kw_{k+1}=12$  in the subword
$w_{b+2}\ldots w_{a-1}$.   This implies that there is no subword $v_kv_{k+1}=12$
in the subword $v_b\ldots v_{a-3}$. Thus we have  $c_{j+1}\geq a-2$, that is, $a\leq c_{j+1}+2$. Since $c_{j+1}+2\geq a>b\geq c_j+1$ and $b\leq c_{j+1}\leq c_{m+1}=\alpha(v)$,  it follows that  $\psi(w)=(a,b)\rightarrow \psi (v)$ is in $\mathcal{DU}_{2n}(4123)$ from Lemma \ref{lem2}.


 Now we turn to the proof of $\mathcal{A}(\psi(w))=\mathcal{B}(w)$ for the case $w_{a+3}\neq 3$.  Let $k$ be a nonnegative  integer $k$ with $k< b-1$. From the construction of $v$, we have $v_kv_{k+1}=w_kw_{k+1}$. Since $k<b-1\leq a-2=\alpha(w)-2$ and $k<b-1\leq \alpha(v)-1$, we derive that $k\in \mathcal{B}(w)$ if and only if $k\in \mathcal{B}(v)$.  Observe  that $w_{b}=1$. This ensures   that $b-1\notin \mathcal{B}(w)$ when $b\geq 2 $ by the definition of the set $\mathcal{B}(w)$.
 Recall that $b\geq c_j+1$. According to the definitions of $\psi$ and $\mathcal{B}(w)$, we have $b\geq a_p$.    So, we derive that
\begin{itemize}
  \item if $b=a_p$, then   $  \{a_0, a_1,   \ldots,  a_{p-1} \}=\{c_0, c_1, \ldots, c_{j-1}\}$ when $b=c_j+1$ with $j\geq 1$; otherwise, $  \{a_0, a_1,  \ldots,  a_{p-1}\}=\{c_0, c_1, \ldots, c_j\}    $;

\item  if $b> a_ p$, then    $ \{a_0, a_1, \ldots,
a_{p}\}=\{c_0, c_1, \ldots, c_{j-1}\}$ when $b=c_j+1$ and $j\geq 1$; otherwise,
$ \{a_0, a_1, \ldots,
a_{p}\}=\{c_0, c_1, \ldots, c_{j}\}$.
  \end{itemize}
 According to the definition of $\mathcal{B}(w)$ and the construction of $(v,b)$, it is easy to check that if $b=a_p$, then we have $b\leq \alpha(w)-2=a-2$; otherwise,  we have $b=a-1$. Note that $\psi(w)=(a,b)\rightarrow \psi(v)$, $\mathcal{A}(\psi(v))=\mathcal{B}(v)$ and $c_{j+1}\geq b\geq c_j+1$.
  By Lemma \ref{lem2}, we can verify that
   \begin{itemize}
  \item if $b=a_p$, then  $  \mathcal{A}(\psi(w))= \{c_0, c_1, \ldots, c_{j-1}, b\}$ when $b=c_j+1$ with $j\geq 1$; otherwise, $    \mathcal{A}(\psi(w))  =\{c_0, c_1, \ldots, c_j, b\}    $;

\item  if $b> a_ p$, then    $ \mathcal{A}(\psi(w))= \{c_0, c_1, \ldots, c_{j-1}\}$ when $b=c_j+1$ and $j\geq 1$; otherwise,
$ \mathcal{A}(\psi(w))=\{c_0, c_1, \ldots, c_{j}\}$.
  \end{itemize}
  Thus, we derive that $\mathcal{A}(\psi(w))=\mathcal{B}(w)$.
    This completes the proof.
\end{proof}

Now we aim to prove that the map $\phi$ is
 a bijection by showing that the maps $\phi$ and $\psi$ are inverses of each other. 
 First, we need to introduce the following definition.
  Let $w=w_1w_2\ldots w_n$ be a word. The entry $w_i$ is said to be {\em positioned} at $i$.







\begin{theorem}\label{mainphi}
The map  $\phi$  is a bijection between  the set
$\mathcal{DU}_{2n}(4123)$ and the set of Yamanouchi words on the
alphabet $ \{1,2,3\}$ of type $(n,n,n)$ such that for any permutation $\pi=\pi_1\pi_2\ldots \pi_{2n}\in \mathcal{DU}_{2n}(4123)$, we have $\pi_1=\alpha(\phi(\pi))$ and
$\mathcal{A}(\pi)=\mathcal{B}(\phi(\pi))$
\end{theorem}
\begin{proof}
It is sufficient to show that the maps $\phi$   and  $\psi$ are  inverses of each other.  First we need to   show that $\psi(\phi (\pi))=\pi$ for any permutation $\pi\in \mathcal{DU}_{2n}(4123)$. We proceed  by induction on $n$.
Obviously,  for $n=1$, we have $\psi(\phi(21))=\psi(123)=21$.   For $n\geq 2$, choose  $\sigma=\sigma_1\sigma_2\ldots \sigma_{2n-2}$   such that $\pi=(a,b)\rightarrow\sigma$ where $a=\pi_1$ and $b=\pi_2$.
  Assume that  $\psi(\phi (\sigma))=\sigma$.


  For convenience, let $u=u_1u_2\ldots u_{3n-3}=\phi(\sigma)$ and $w=w_1w_2\ldots w_{3n}=\phi(\pi)$.
    By Proposition \ref{phi}, $u$ and $w$ are Yamanouchi words on the
alphabet $ \{1,2,3\}$  satisfying  $\alpha(u)=\sigma_1$, $\alpha(w)=\pi_1=a$,  $\mathcal{B}(u)=\mathcal{A}(\sigma)$ and $\mathcal{B}(w)=\mathcal{A}(\pi)$.  Suppose  that
  $\mathcal{A}(\sigma)=\{a_0, a_1, \ldots, a_p\}$, where $p\geq 0$ and  $
0=a_0<a_1<a_2<\ldots<a_p<a_{p+1}=\sigma_1$.
  By Lemma \ref{lem4123},
we have $a_{j+1}+2\geq a>b\geq a_{j}+1$ for some integer $j$ and
$b\leq \sigma_1$.

When we apply the map $\psi$ to  the word $w=\phi(\pi)$, we   construct an ordered pair from $w$.  Denote by $(v,t)$ the   obtained ordered pair.    By the definition of   $\psi$, we have $\psi(\phi(\pi))=\psi(w)=(a,t)\rightarrow \psi(v)$.  Since   $\pi=(a,b)\rightarrow \sigma$ and   $\psi(\phi (\sigma))=\sigma$, in order to prove $\psi(\phi(\pi))=\pi$,  it is sufficient to  show that
  $t=b$ and $v=\phi(\sigma)$.  According to the definition of $\phi$,  the word $u$ can be obtained from $w$ by removing $w_b$, $w_{b+1}$ and $w_{a+1}$.  Meanwhile, by the construction of the ordered pair $(v,t)$,  the word $v$ is obtained from $w$ by removing $w_t$, $w_{t+1}$ and $w_{a+1}$. Thus, it is sufficient to  show that
  $t=b$ to prove $\psi(\phi(\pi))=\pi$.       We shall consider two cases.






If $a=a_{p+1}+2$,  then we have $b\geq a_{p}+1$. Recall that $b\leq \sigma_1=a_{p+1}$. This yields that $a>b+1$.  By Lemma \ref{lem2},  we deduce that  if $b=a_p+1$ and $p\geq 1$,  then $ \mathcal{A}(\pi)=\{a_0,   \ldots, a_{p-1},   b\}$; otherwise, $ \mathcal{A}(\pi)=\{a_0,  \ldots, a_p,   b\}$. Since $a_{p+1}=\sigma_1=\alpha(u)$,   we have  $u_{a-1}=u_{\alpha(u)+1}=3$ according to the definition of $\alpha(u)$. According to the definition of $\phi$, the word $u$ can be obtained from $w$ by removing $w_b, w_{b+1} $ and $w_{a+1}$. This implies that $w_{a+2}=u_{a-1}=3$.
  By  the  construction of the ordered pair $( v, t )$,  it is easily seen that $t=b$.



If $a<a_{p+1}+2$,  then we have $a-1<a_{p+1}+1=\alpha(u)+1$.   According to the definition of $\alpha(u)$, we have $u_{a-1}\neq 3$. This implies that
   $w_{a+2}=u_{a-1}\neq 3$.
   Since $a_j+1\leq b<a\leq a_{j+1}+2$,  there is no subword $u_ku_{k+1}=12$ for $b\leq k\leq a-3$ according to the definition of $\mathcal{B}(u)$. By the construction of $w$, we see that there is no subword $w_kw_{k+1}=12$ for $b+2\leq k\leq a-1$. On the other hand, according to the definition of $\phi$, we have   $w_bw_{b+1}=12$ and $b\leq a-1$.    From the construction of the ordered pair $(v,t)$, it follows that $t=b$.
     Hence, we have $\psi(\phi(\pi))=\pi$.


     Next we turn to the proof of  the equality $\phi(\psi(w'))=w'$ for any Yamanouchi word $w'$ on the
alphabet $ \{1,2,3\}$ of type $(n,n,n)$. We proceed by induction on $n$.
Obviously,  for $n=1$, we have $\phi(\psi(123))=\phi(21)=123$. For $n\geq 2$,
let $a'=\alpha(w')$.
According to the definition of $\psi$, we  obtain an
ordered pair $(v',b')$ from $w'$. By the construction of the ordered pair $(v',b')$, the word $v'$ is obtained from $w'$ by removing the entries positioned at $b'$, $b'+1$ and $a'+1$.   From the proof of Proposition \ref{bar-phi}, it follows that $v'$ is a Yamanouchi word  of type $(n-1, n-1, n-1)$.
   By Proposition \ref{bar-phi},  the permutations $\psi(w')$ and $\psi(v')$ are in $\mathcal{DU}_{2n}(4123)$ and $\mathcal{DU}_{2n-2}(4123)$, respectively.
 Assume that $\phi(\psi(v'))=v'$.
According to the definition  of   $\psi$, we have $\psi(w')=(a',b')\rightarrow \psi(v')$. When we apply the map $\phi$ to the permutation $ \psi(w')$,   we get a a Yamanouchi word $\phi(\psi(w'))$  of type $(n, n, n)$. By the definition of $\phi$,  we can recover the word $\phi(\psi(v' ))$  form $\phi(\psi(w'))$
 by removing the entries positioned at $b'$, $b'+1$ and $a'+1$.
     Recall that $\phi(\psi(v'))=v'$ and $v'$ is obtained from $w'$ by removing the entries  positioned at $b'$, $b'+1$ and $a'+1$. Thus we have $\phi(\psi(w'))=w'$.   This completes the proof.
     \end{proof}



By the same reasoning as in the proofs of Propositions \ref{phi} and \ref{bar-phi} and Theorem \ref{mainphi}, we can obtain the following   analogous results for $4123$-avoiding down-up alternating permutations of odd length.
\begin{proposition}\label{phi'}
For any  permutation
$\pi=\pi_1\pi_2\ldots \pi_{2n-1}\in \mathcal{DU}_{2n-1}(4123)$, the word $\phi(\pi)$ is a skew Yamanouchi word on the alphabet $\{1,2,3\}$ of type $(n-1,n,n+1)$ satisfying   $\pi_1=\alpha(\phi(\pi))$ and
$\mathcal{A}(\pi)=\mathcal{B}(\phi(\pi))$.
\end{proposition}


\begin{proposition}\label{bar-phi'}
 For  any  skew Yamanouchi word $w=w_1w_2\ldots w_{3n}$ on the
alphabet $ \{1,2,3\}$ of type $(n-1,n,n+1)$,  the permutation $\psi(w)$ is in $\mathcal{DU}_{2n-1}(4123)$ such that the first entry of the 
permutation  $\psi(w)$ is equal to
 $ \alpha(w)$ and
$\mathcal{A}(\psi(w))=\mathcal{B}(w)$.
\end{proposition}


  \begin{theorem}\label{mainphi'}
The map  $\phi$  is a bijection between  the set
$\mathcal{DU}_{2n-1}(4123)$ and the set of skew Yamanouchi words on the
alphabet $ \{1,2,3\}$ of type $(n-1,n,n+1)$ such that for any permutation $\pi=\pi_1\pi_2\ldots \pi_{2n-1}\in \mathcal{DU}_{2n-1}(4123)$, we have $\pi_1=\alpha(\phi(\pi))$ and
$\mathcal{A}(\pi)=\mathcal{B}(\phi(\pi))$.
\end{theorem}


So far, we have established bijections between the set $\mathcal{DU}_{2n}(4123)$ and the set of Yamanouchi words on
the alphabet $\{1,2,3\}$ of type $(n,n,n)$,  and between the set of $\mathcal{DU}_{2n-1}(4123)$ and the set of skew Yamanouchi words on
the alphabet $\{1,2,3\}$ of type $(n-1,n,n+1)$.   Now we proceed to  present the desired  bijections between the set $\mathcal{DU}_{2n}(4123)$ and the set of standard Young tableaux of shape $(n,n,n)$,  and between the set $\mathcal{DU}_{2n-1}(4123)$ and the set of  shifted standard Young tableaux of shape $(n+1,n,n-1)$.






 Denote by $\mathcal{W}_n$ the set of words $w=w_1w_2\ldots w_n$  on the alphabet $\{1,2,3\}$. Now we define a map   $\beta$: $\mathcal{W}_n\rightarrow \mathcal{W}_n$ as follows. Let $w=w_1w_2\ldots w_{3n}$ be a  word on the alphabet $\{1,2,3\}$.  Define $\beta(w)=(4-w_{n})(4-w_{n-1})\ldots (4-w_{1})$. Obviously, the map $\beta$ is essentially an involution on the set $\mathcal{W}_n$, that is,  for any word $w\in \mathcal{W}_n$, we have $\beta(\beta(w))=w$.  Note that  the map $\beta$  can also be called  the {\em reverse-complement} operation.


According to the definitions of skew Yamanouchi  words and  shifted Yamanouchi  words,  it is easy to verify that    the  map $\beta$   induces  a
bijection between  the set of  skew Yamanouchi  words of type $(n-1, n, n+1)$
and  the set of   shifted Yamanouchi  words of type $(n+1, n, n-1)$.   Similarly, the map $\beta$ is an involution on the set of Yamanouchi
words of type $(n, n, n)$.  Moreover,
 the map $\beta$ transforms  the initial run of a word to the final run. Recall that the map $\chi$ is a bijection between the set of Yamanouchi  words of type $(n, n, n)$ and standard Young tableaux of shape $(n,n,n)$. Moreover, the map $\chi$ is a bijection between the set of shifted Yamanouchi  words of type $(n+1, n, n-1)$ and shifted standard Young tableaux of shape $(n+1,n,n-1)$.  Observe that given  any ordinary or shifted standard Young tableau $T$ of shape $(a,b,c)$ with the $(1,a)$-entry equal to $k$, its corresponding   word
 $\chi(T)$ has the final run of length $a+b+c-k$.
  Therefore, we derive the following results.
 \begin{proposition}\label{rc1}
  The map $\chi^{-1}\circ \beta$ is a bijection between the set of Yamanouchi  words of type $(n, n, n)$ with the initial run of length $k$ and the set of standard Young tableaux of shape $(n,n,n)$ with the $(1,n)$-entry equal to $3n-k$.
  \end{proposition}

  \begin{proposition} \label{rc2}
    The map $\chi^{-1}\circ \beta$ induces a bijection between the set of  skew Yamanouchi  words of type $(n-1, n, n+1)$ with the initial run of length $k$ and the set of  shifted standard Young tableaux of shape $(n+1,n,n-1)$ with the $(1,n+1)$-entry equal to $3n-k$.
 \end{proposition}


 For example, consider a  skew Yamanouchi  word $w=112123231323233$ of type $(4,5,6)$ with the initial  run of length $5$. By applying the map $\beta$,  we  obtain a shifted Yamanouchi  word $\beta(w)=112121312123233$ of type $(6,5,4)$ with the final run of length $5$. Applying the inverse map $\chi^{-1}$ to $\beta(w)$ gives a shifted standard Young tableaux $\chi^{-1}(\beta(w))$ with  the (1,6)-entry equal to $10$, as illustrated in Figure \ref{fi.1}.
  \begin{figure}[h,t]
\begin{center}
\begin{picture}(50,50)
\setlength{\unitlength}{1mm}

\put(0,10){\framebox(5,5) {1}} \put(5,10){\framebox(5,5) {2}}\put(10,10){\framebox(5,5) {4}}\put(15,10){\framebox(5,5){6}}\put(20,10){\framebox(5,5) {8}}\put(25,10){\framebox(5,5) {10}}

\put(5,5){\framebox(5,5) {3}}\put(10,5){\framebox(5,5) {5}}\put(15,5){\framebox(5,5) {9}}\put(20,5){\framebox(5,5) {11}}\put(25,5){\framebox(5,5) {13}}

\put(10,0){\framebox(5,5) {7}}\put(15,0){\framebox(5,5) {12}}\put(20,0){\framebox(5,5) {14}}\put(25,0){\framebox(5,5) {15}}
\end{picture}
\end{center}
\caption{The shifted standard Young tableau $\chi^{-1}(\beta(w))$.}\label{fi.1}
\end{figure}

















  Combining  Theorems \ref{mainphi} and  \ref{mainphi'} and Propositions   \ref{rc1} and \ref{rc2}, we deduce the following theorems.


\begin{theorem}\label{cphi}
The map $ \Phi =\chi^{-1}\circ \beta \circ\phi$ is a bijection between the set $\mathcal{DU}_{2n}(4123)$ and the set of standard Young tableaux of shape $(n,n,n)$ such that for any permutation $\pi=\pi_1\pi_2\ldots \pi_{2n}\in \mathcal{DU}_{2n}(4123)$, the $(1,n)$-entry of the corresponding tableau is equal to $3n-\pi_1$ .
\end{theorem}

\begin{theorem}\label{cpsi}
The map $ \Phi =\chi^{-1}\circ \beta \circ\phi$ is a bijection between the set $ \mathcal{DU}_{2n-1}(4123)$ and the set of shifted  standard Young tableaux of shape
  $(n+1,n,n-1)$  such that for any permutation $\pi=\pi_1\pi_2\ldots \pi_{2n}\in \mathcal{DU}_{2n-1}(4123)$,    the $(1,n+1)$-entry of the corresponding tableau is equal to $3n-\pi_1$.
\end{theorem}








Recall that there are bijections between the set
$\mathcal{UD}_{2n}(1234)$ and the standard Young tableaux of shape
$(n,n,n)$, and between  the set
     $\mathcal{UD}_{2n+1}(2143)$ and shifted standard Young tableaux of shape $(n+2, n+1,
    n)$. By the operation of complement,  the set
    $\mathcal{DU}_n(4123)$ is in bijection with the set
    $\mathcal{UD}_n(1432)$.  Thus, by Theorems \ref{cphi} and \ref{cpsi},  we derive that $|\mathcal{UD}_{2n}(1432)|=|\mathcal{UD}_{2n}(1234)|$ and
      $|\mathcal{UD}_{2n+1}(1432)|=|\mathcal{UD}_{2n+1}(2143)|$, as conjectured by Lewis \cite{Lewis2}.





\section{4123-avoiding up-down alternating permutations}
In this section, we
show that $4123$-avoiding up-down alternating permutations of length $2n+1$ are
in one-to-one correspondence with standard Young tableaux of shape
$(n+1, n, n-1)$. Moreover, for $n\geq 2$, there is a bijection
between the set of  $4123$-avoiding up-down permutations of length
$2n$ and the set of shifted   standard Young tableaux of shape
$(n+2, n, n-2)$. The following Lemma will be essential in
establishing the bijections.
\begin{lemma}\label{4123up}
Let $\sigma=\sigma_1\sigma_2\ldots \sigma_n$  be a permutation in
$\mathcal{DU}_n(4123)$ and let $a $ be a positive integer. If $a\leq \sigma_1$, then
$\pi=a\rightarrow \sigma  $ is in $\mathcal{UD}_{n+1}(4123)$.
\end{lemma}
\begin{proof}  Let $\pi=\pi_1\pi_2\ldots \pi_{n+1}$.  In order to prove $\pi\in \mathcal{UD}_{n+1}(4123)$,
it is sufficient to prove that there exists no subsequence $\pi_1\pi_i\pi_j\pi_k$ with $i<j<k$ in $\pi$. Assume  that $\pi_1\pi_i\pi_j\pi_k$ is a subsequence  order-isomorphic to $4123$. Since $\pi_1<\pi_2$,  we deduce that $\pi_2\pi_i\pi_j\pi_k$ is also a subsequence  order-isomorphic to $4123$, which implies that $\sigma_1\sigma_{i-1}\sigma_{j-1}\sigma_{k-1}$ is a subsequence order-isomorphic to $4123$. This contradicts with the fact that $\sigma$ is a $4123$-avoiding down-up alternating permutation. This completes the proof. \end{proof}

Now we proceed to construct a map $\gamma$ from the     set
$\mathcal{UD}_{2n+1}(4123)$ to the set of   standard Young tableaux  of shape $(n+1,n,n-1)$. Given a permutation $\pi=\pi_1\pi_2\ldots \pi_{2n+1}\in \mathcal{UD}_{2n+1}(4123)$, let $\sigma=\sigma_1\sigma_2\ldots \sigma_{2n}$ be the permutation such that $\pi=\pi_1\rightarrow \sigma$. Obviously,  the permutation $\sigma$ is in $\mathcal{DU}_{2n}(4123)$. By Theorem \ref{cphi}, the tableau  $ \Phi(\sigma)$ is a standard Young tableau of shape $(n, n, n)$ with  the $(1,n)$-entry equal to $3n-\sigma_1$.  Delete the $(3,n)$-entry of $\Phi(\sigma)$, insert
  a $(1,n+1)$-entry equal to $3n+1-\pi_1$, and increase each entry that is larger than $3n-\pi_1$ by one.
    Define $T=\gamma(\pi)$ to be the resulting   tableau.  Since $\pi_1\leq \sigma_1$, the obtained tableau $T$ is a standard Young tableau  of shape $(n+1, n, n-1)$. Therefore, the map $\gamma$ is well defined.

For example, consider a $4123$-avoiding up-down alternating permutation
$\pi=4657132$.   We get $\sigma=546132$ such that $\pi=4\rightarrow \sigma$.  By applying the bijection $\Phi$, we get a standard Young tableau $\Phi(\sigma)$:
   \begin{center}
\parbox[t]{4cm}{ \young(124,358,679) }
\end{center}
  Removing the $(3,3)$-entry of $\Phi(\sigma)$ and inserting a $(1,4)$-entry equal to $6$, we get the
  tableau $\gamma(\pi)$:
\begin{center}
\parbox[t]{4cm}{ \young(1246,359,78) }
\end{center}




\begin{theorem}\label{udodd}
For $n\geq 1$, the map  $\gamma$ is a bijection  between  the set
$\mathcal{UD}_{2n+1}(4123)$ and the set of   standard Young tableaux  of shape $(n+1,n,n-1)$.
\end{theorem}
\begin{proof}     We proceed to construct a map $\bar{\gamma}$ from the set of standard Young tableaux  of shape $(n+1,n,n-1)$ to the set $\mathcal{UD}_{2n+1}(4123)$.
 Given a  standard Young tableau  $T$ of shape  $(n+1, n, n-1)$, we wish to recover a permutation $\bar{\gamma}(T)\in \mathcal{UD}_{2n+1}(4123)$. Suppose that the $(1,n+1)$-entry and $(1,n)$-entry of $T$ are equal to  $3n+1-a$ and $3n-b$, respectively. Then we construct a permutation $\bar{\gamma} (T)$ as follows.
\begin{itemize}
 \item Remove the $(1,n+1)$-entry from the tableau $T$ and decrease each entry that is larger than $3n+1-a$ by one;
     \item   Insert a $(3,n)$-entry which is equal to $3n$. Denote by $T'$ the 
     obtained  standard Young tableaux;
\item Finally, set $\bar{\gamma}(T)=a\rightarrow \Phi^{-1}(T')$.
 \end{itemize}
Note that $T'$ is a standard Young tableau of shape $(n,n,n)$ such that the 
$(1,n)$-entry equals $3n-b$. 
Let $\sigma=\Phi^{-1}(T')=\sigma_1\sigma_2\ldots \sigma_{2n}$.   
By Theorem \ref{cphi}, we deduce that $\sigma$ is a down-up alternating
 permutation in $\mathcal{DU}_{2n}(4123)$ with $\sigma_1=b$.  
 Since $T$ is a standard Young tableau,  we have $a\leq b$.  
  By Lemma \ref{4123up}, the obtained 
  permutation $\bar{\gamma}(T)$ is in $\mathcal{UD}_{2n+1}(4123)$.  
   It is straightforward   to check that the construction of the
    map $\bar{\gamma}$ reverses  each step of the construction of the map $\delta$. 
    Thus the maps $\gamma$ and $\bar{\gamma}$ are   inverses of each other.  This completes the proof. \end{proof}

Recall that  there is a bijection between the set $\mathcal{UD}_{2n+1}(1234)$  
and the set of standard Young tableaux  of shape $(n+1, n, n-1)$ \cite{Lewis1}.
From Theorem \ref{udodd}, we deduce the following result.
\begin{theorem}\label{en1}
For $n\geq 0$, we have
$$|\mathcal{UD}_{2n+1}(4123)|=|\mathcal{UD}_{2n+1}(1234)|.$$
\end{theorem}



Our next goal is to establish an analogous bijection between  the set $\mathcal{UD}_{2n}(4123)$  and the set of  shifted standard Young tableaux of shape $(n+2,n,n-2)$. We define a map $\delta$ from the set of the set of $4123$-avoiding up-down alternating permutations of length $2n$  to  the set of  shifted standard Young tableaux of shape $(n+2,n,n-2)$.
For $n\geq 2$, given a permutation $\pi=\pi_1\pi_2\ldots \pi_{2n}\in \mathcal{UD}_{2n}(4123)$, let $\sigma=\sigma_1\sigma_2\ldots \sigma_{2n-1}$ be the permutation satisfying  $\pi=\pi_1 \rightarrow \sigma$.  Clearly,   the permutation $\sigma$ is in $\mathcal{DU}_{2n-1}(4123)$. By Theorem \ref{cpsi},   the tableau $\Phi(\sigma)$ is a shifted  standard Young tableau of shape $(n+1, n, n-1)$ with  the $(1,n+1)$-entry equal to $3n-\sigma_1$.  Finally we obtain a tableau  from $\Phi(\sigma)$ by deleting the $(3,n-1)$-entry,  inserting a $(1,n+2)$-entry equal to $(3n+1-\pi_1)$ and increasing each entry larger than $3n-\pi_1$ by one. Since $\pi_1\leq \sigma_1$, the obtained tableau  is a shifted standard Young  tableau  of shape $(n+2, n, n-2)$.
As in the case for the map $\gamma$, we can define the inverse map of $\delta$ by reversing each step of the map $\delta$. By Lemma  \ref{4123up} and Theorem \ref{cpsi},
we can verify that $\delta$ is a bijection.
\begin{theorem}\label{oddud}
For $n\geq 2$,    the map $\delta$ described above is a bijection between the set $\mathcal{UD}_{2n}(4123)$ and the set of   shifted standard Young tableaux of shape $(n+2,n,n-2)$.
\end{theorem}

As in the case for standard Young tableaux, there is a simple hook length formula for shifted standard Young tableaux \cite{ck}. By simple computation, we derive that  the number of shifted standard Young tableaux  of shape $(n+2,n,n-2)$ is equal to ${2(3n)!\over n!(n+1)!(n+2)!}.$  Recall that  the number of $1234$-avoiding up-down
    alternating permutations of length $2n$ is given by ${2(3n)!\over
    n!(n+1)!(n+2)!}$.  Hence, we obtain the following result.



\begin{theorem}\label{en2}
For $n\geq 0$, we have $$|\mathcal{UD}_{2n}(4123)|=|\mathcal{UD}_{2n}(1234)|={2(3n)!\over n!(n+1)!(n+2)!}.$$
\end{theorem}








 \noindent{\bf Acknowledgments.} The authors  would like to thank the referee for helpful suggestions.
   This work was supported by
the National Natural Science Foundation of China (No.10901141) and Zhejiang Innovation Project(Grant No. T200905).

%--------------------------
\begin{thebibliography}{100}
\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, arXiv: math.CO \,1205.1778v1.


\bibitem{eu}
S.P. Eu, Skew-standard tableaux with three rows, {\em Adv. Appl.
Math.} {\bf 45} (2010), 463--469.

\bibitem{ck}
C. Krattenthaler, Bijective proofs of the hook formulas for the number of standard Young tableaux, ordinary and shifted,
{\em Electronic J. Combin. } {\bf 2} (1995), R13.


\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}  {\bf 118} (2011), 1436--1450.

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

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




 \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/~rstan/ec/catadd.pdf,  2012.






\end{thebibliography}
\end{document}