% EJC papers *must* begin with the following two lines. 
\documentclass[12pt]{article}
\usepackage{e-jc}





% 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}

\usepackage{rotating}
\usepackage{tikz}

% 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


% declare theorem-like environments
%\usepackage{showkeys}
\newtheorem{example}{Example}
\newtheorem{Def}{Definition}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{claim}{Claim}
%\newtheorem{remark}{Remark}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{Conjecture}[theorem]{Conjecture}
\newtheorem{?}[theorem]{Problem}

\theoremstyle{definition}
\newtheorem{remark}{Remark}


\usepackage{amsthm,amsmath,amssymb,url,cite,color}

\def\blue{\textcolor{blue}}
\def\red{\textcolor{red}}
\def\green{\textcolor{green}}
%\theoremstyle{definition}
%\newtheorem{definition}[theorem]{Definition}
%\newtheorem{xca}[theorem]{Exercise}
%\theoremstyle{remark}
%\newtheorem{remark}[theorem]{Remark}
\newenvironment{demo}[1]{%
  \trivlist
  \item[\hskip\labelsep
        {\bf #1.}]
}{%
\hfill\qedsymbol
  \endtrivlist
}

\numberwithin{equation}{section}
\newcommand{\abs}[1]{\lvert#1\rvert}
\newcommand{\blankbox}[2]{
  \parbox{\columnwidth}{\centering

   \setlength{\fboxsep}{0pt}
    \fbox{\raisebox{0pt}[#2]{\hspace{#1}}}
  }
}

\newcommand{\N}{\mathbb{N}}

\newcommand{\Z}{\mathbb{Z}}

\newcommand{\C}{\mathbb{C}}

\def\lec{\mathrm{lec}}
\def\inv{\mathrm{inv}}
\def\aid{\mathrm{aid}}
\def\ai{\mathrm{ai}}

\def\rev{\mathrm{rev}}
\def\comp{\mathrm{comp}}
\def\G{\mathfrak{G}}

%\def\b{\mathrm{b}}
\def\ls{\mathrm{ls}}
\def\rs{\mathrm{rs}}
\def\lb{\mathrm{lb}}
\def\rb{\mathrm{rb}}
\def\ub{\mathrm{ub}}
\def\st{\mathrm{st}}
\def\id{\mathrm{id}}
\def\Fix{\mathrm{FIX}}
\def\fix{\mathrm{fix}}
\def\pix{\mathrm{pix}}
\def\rix{\mathrm{rix}}
\def\aix{\mathrm{aix}}
\def\max{\mathrm{max}}
\def\min{\mathrm{min}}
\def\cont{\mathrm{cont}}
\def\exc{\mathrm{exc}}
\def\dd{\mathrm{dd}}
\def\des{\mathrm{des}}
\def\Des{\mathrm{DES}}
\def\maj{\mathrm{maj}}
\def\imaj{\mathrm{imaj}}
\def\Cont{\mathrm{Cont}}
\def\fexc{\mathrm{fexc}}
\def\fmaj{\mathrm{fmaj}}
\def\S{\mathfrak{S}}
\def\B{\mathfrak{B}}
\def\D{\mathfrak{D}}
\def\T{\mathfrak{T}}
\def\C{\mathfrak{C}}
\def\E{\mathcal{E}}
\def\R{\mathcal{R}}
\def\DE{\mathcal{E}}
\def\W{\mathcal{W}}
\def\G{\mathfrak{G}}
\def\dec{\mathrm{dec}}
\def\tot{\mathrm{tot}}
\def\single{\mathrm{single}}
\def\wlec{\mathrm{wlec}}
\def\rinv{\mathrm{rinv}}
\def\wpix{\mathrm{wpix}}
\def\da{\mathrm{da}}
\def\tg{\mathrm{tg}}
\def\SCF{\mathrm{SCF}}
\def\LG{{L-hook}}
\def\FG{{F-hook}}
\def\cyc{\mathrm{cyc}}
\def\lyc{\mathrm{lyc}}
\def\valley{\mathrm{valley}}
\def\peak{\mathrm{peak}}
\def\fpeak{\mathrm{fpeak}}
\def\cda{\mathrm{cda}}
\def\cdd{\mathrm{cdd}}
\def\Rix{\mathrm{RIX}}
\def\Orb{\mathrm{Orb}}
\def\EXC{\mathrm{EXC}}
\def\NEXC{\mathrm{NEXC}}

\def\neg{\mathrm{neg}}
\def\fexc{\mathrm{fexc}}
\def\imaj{\mathrm{imaj}}
\def\ides{\mathrm{ides}}

\def\bk{\mathrm{bk}}
\def\den{\mathrm{den}}
\def\LS{\mathrm{LS}}
\def\RS{\mathrm{RS}}
\def\LB{\mathrm{LB}}
\def\RB{\mathrm{RB}}
\def\area{\mathrm{area}}
\def\SLR{\mathrm{SLR}}
\def\mak{\mathrm{mak}}
\def\lcs{\mathrm{lcs}}


\def\b{\blue{b}}
\def\a{\red{a}}
\def\M{\mathcal{M}}
\def\Ub{\mathrm{U\b}}
\def\val{\textbf{val}}
\def\pos{\textbf{pos}}
\def\n{\textbf{n}}
\def\e{\textbf{e}}


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

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

\title{On $1212$-avoiding restricted growth functions}

% 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{Zhicong Lin\\
\small School of Science, Jimei University\\[-0.8ex]
\small Xiamen 361021, P.R. China\\
\small  CAMP, National Institute for Mathematical Sciences\\[-0.8ex]
\small  Daejeon 34047, Republic of Korea\\
\small\tt lin@nims.re.kr
\and
Shishuo Fu\\
\small College of Mathematics and Statistics, Chongqing University\\[-0.8ex]
\small Chongqing 401331, P.R. China\\
\small\tt  fsshuo@cqu.edu.cn
}

% \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{January 10, 2017}{}\\
\small Mathematics Subject Classifications: 05A05, 05A19}

\begin{document}

\maketitle

% E-JC papers must include an abstract. The abstract should consist of a
% succinct statement of background followed by a listing of the
% principal new results that are to be found in the paper. The abstract
% should be informative, clear, and as complete as possible. Phrases
% like "we investigate..." or "we study..." should be kept to a minimum
% in favor of "we prove that..."  or "we show that...".  Do not
% include equation numbers, unexpanded citations (such as "[23]"), or
% any other references to things in the paper that are not defined in
% the abstract. The abstract will be distributed without the rest of the
% paper so it must be entirely self-contained.

\begin{abstract}
Restricted growth functions (RGFs) avoiding the pattern $1212$ are in natural bijection with noncrossing partitions. Motivated by  recent work of Campbell et al., we study five classical statistics $\bk,\ls,\lb,\rs$ and $\rb$ on $1212$-avoiding RGFs.  We show the equidistribution of $(\ls,\rb,\lb, \bk)$ and $(\rb,\ls,\lb, \bk)$ on $1212$-avoiding RGFs by constructing a simple involution.
To our surprise, this result was already proved by Simion 22 years ago via an involution on noncrossing partitions. Our involution, though turns out essentially the same as Simion's, is defined quite differently and has the advantage that makes the discussion more transparent. Consequently, a multiset-valued extension of Simion's result is discovered. Furthermore, similar approach enables us to prove the equidistribution of $(\mak,\rb,\rs, \bk)$ and $(\rb,\mak,\rs, \bk)$ on $1212$-avoiding RGFs, where ``$\mak$" is a set partition statistic introduced by Steingr\'imsson. 

Through two bijections to Motzkin paths, we also prove that the triple of classical permutation statistics $(\exc+1,\den,\inv-\exc)$ on $321$-avoiding permutations is equidistributed with the triple $(\bk,\rb,\rs)$ on $1212$-avoiding RGFs, which generalizes another result of Simion. In the course, an interesting $q$-analog of the $\gamma$-positivity of Narayana polynomials is found. 

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} restricted growth function; pattern avoidance; noncrossing partitions; partition statistics; Narayana polynomials
\end{abstract}

\section{Introduction}

A {\em restricted growth function} (RGF) of length $n$ is a word $w=w_1w_2\ldots w_n$ on positive integers such that 
$$
w_1=1\quad\text{and}\quad w_{i+1}\leq1+\max\{w_1,w_2,\ldots,w_i\}\,\,\text{for all $i\geq1$}.
$$
A {\em set partition} of $[n]:=\{1,2,\ldots,n\}$ is a family of nonempty subsets (or blocks)  $B_1,\ldots,B_k$ whose disjoint union is $[n]$. 
RGFs are of interest because they are in natural bijection with set partitions in the following way. We first write a set partition $\sigma$ of $[n]$ as $B_1/\ldots/B_k$ in the {\em standard form} where $\min\,B_1<\min\,B_2<\cdots< \min\,B_k$. Then the associated RGF $w(\sigma)=w_1\ldots w_n$ is defined as
$$
w_i=j\,\,\text{if and only if}\,\, i\in B_j.
$$
For example, we have $w(13/24)=1212$. Note that the number of {\em blocks} of a set partition becomes the greatest integer in its associated RGF. Therefore, we denote $\bk(w)$ the greatest integer in $w$.

Let $R_n$ be the set of all RGFs of length $n$. Wachs and White~\cite{WW} investigated four statistics $\ls$ ({\em left smaller}), $\lb$ ({\em left bigger}),  $\rs$ ({\em right smaller}) and $\rb$ ({\em right bigger}) on RGFs defined for each $w\in R_n$ by:
\begin{align*}
&\ls(w):=\sum_{i=1}^n\#\{w_j : j<i, w_j<w_i\},\quad \lb(w):=\sum_{i=1}^n\#\{w_j : j<i, w_j>w_i\},\\
&\rs(w):=\sum_{i=1}^n\#\{w_j : j>i, w_j<w_i\}\quad\text{and}\quad \rb(w):=\sum_{i=1}^n\#\{w_j : j>i, w_j>w_i\}.
\end{align*}
For example, if $w=12334155\in R_8$, then $\ls(w)=16,\lb(w)=3,\rs(w)=4,\rb(w)=13$.
Recently, a systematic study of RGF patterns with respect to $\ls,\lb,\rs$ and $\rb$ was carried out by Campbell, Dahlberg, Dorward, Gerhard, Grubb, Purcell and Sagan in~\cite{CDD+}, where interesting connections with integer partitions and Motzkin paths were exhibited. At the end of their paper, unaware of the work by Simion~\cite{Sim}, they conjectured that ``$\rb$'' and ``$\ls$'' are equidistributed on $R_n(1212)$, where $R_n(1212)$ is the set of $1212$-avoiding RGFs of length $n$. Here an RGF $w\in R_n$ {\em avoids the pattern $1212$} means that there does not exist some indices $i<j<k<l$ such that $w_i=w_k<w_j=w_l$.

Motivated by Campbell et al.'s conjecture above, we have been able to rediscover and reprove the following quadruple equidistribution that was first established by Simion~\cite{Sim} two decades ago.

\begin{theorem}[Simion~1994]\label{thm:1}
For any $n\geq 0$, the two four-variable statistics
$$ (\ls,\rb,\lb,\bk) \text{ and } (\rb,\ls,\lb,\bk)$$
are equidistributed on $R_n(1212)$.
\end{theorem}



Our proof of Theorem~\ref{thm:1} is by constructing an involution $\phi: R_n(1212)\rightarrow R_n(1212)$, which interchanges the statistics ``$\ls$'' and ``$\rb$'' but preserves the statistics ``$\lb$'' and ``$\bk$''.  It is not hard to show that a set partition is {\em noncrossing} (see~\cite{Sim} for the definition) if and only if its associated RGF is $1212$-avoiding. It turns out that, under the natural bijection between set partitions and RGFs, our involution becomes Simion's~\cite{Sim}, which was defined on noncrossing partitions (see Remark~\ref{invo:sim}). Our involution $\phi$ is defined directly on $1212$-avoiding RGFs, which is based on some kind of direct sum decomposition and has the advantage that makes the discussion more transparent.  In particular, our approach leads to the discovery of  a {\em multiset-valued extension} of  Theorem~\ref{thm:1} (see Theorem~\ref{thm:multi}). Furthermore, similar approach  can  be applied to prove the following quadruple equidistribution involving the set partition statistic ``$\mak$" introduced by Steingr\'imsson~\cite{es} (see the definition of ``$\mak$" on RGFs in Section~\ref{sec:mak}). 

\begin{theorem}\label{thm:mak}
For any $n\geq 0$, the two four-variable statistics
$$ (\mak,\rb,\rs,\bk) \text{ and } (\rb,\mak,\rs,\bk)$$
are equidistributed on $R_n(1212)$. 
 \end{theorem}


Our next result builds a relation  between statistics on $1212$-avoiding RGFs and classical Permutation Statistics, including excedances, inversions and Denert's statistic, on $321$-avoiding permutations. We first review the involved statistics  on permutations. Let $\S_n$ be the set of permutations of $[n]$. For each $\pi=\pi_1\pi_2\ldots\pi_n$ the {\em inversion} number of $\pi$ is
$$
\inv(\pi):=\#\{(i,j): i<j,\pi_i>\pi_j\},
$$
the {\em set of excedances} (resp.~{\em excedance number}) of $\pi$ is
$$
\EXC(\pi):=\{i\in[n-1]: \pi_i>i\} \,\,\,\,(\text{resp.~$\exc(\pi):=\#\EXC(\pi)$})
$$
and the {\em set of non-excedances} of $\pi$ is
$$
\NEXC(\pi):=[n]-\EXC(\pi).
$$
Following Foata and Zeilberger~\cite[Th.~2]{fz}, the {\em Denert's statistic} of $\pi$ may be defined by 
$$
\den(\pi):=\inv(\EXC^*(\pi))+\inv(\NEXC^*(\pi))+\sum_{i\in\EXC(\pi)}i,
$$
where for a subset $S=\{i_1<i_2<\ldots<i_k\}\subseteq[n]$, $S^*(\pi)$ is the subword $\pi_{i_1}\pi_{i_2}\ldots\pi_{i_k}$ of $\pi$. For example, if $\pi=2534716\in\S_7$, then $\inv(\pi)=8$, $\EXC(\pi)=\{1,2,5\}$, $\exc(\pi)=3$ and $\den(\pi)=\inv(257)+\inv(3416)+1+2+5=10$. Note that ``$\exc$'' is a {\em Eulerian} statistic, while both ``$\inv$'' and ``$\den$'' are {\em Mahonian}. Recall that a permutation $\pi\in\S_n$ is said to be {\em $321$-avoiding} if there does not exist indices $i<j<k$ such that $\pi_i>\pi_j>\pi_k$. Let $\S_n(321)$ be the set of all $321$-avoiding permutations in $\S_n$.

\begin{theorem}\label{thm:2}
There exists a bijection $\psi: \S_n(321)\rightarrow R_n(1212)$ such that for each  $\pi\in \S_n(321)$, we have 
$$
(\exc+1,\den,\inv-\exc)(\pi)=(\bk,\rb,\rs)(\psi(\pi)).
$$
Consequently, we have the equidistribution 
\begin{equation}\label{equi:simion}
\sum_{\pi\in\S_n(321)}t^{\exc(\pi)+1}p^{\den(\pi)}q^{\inv(\pi)-\exc(\pi)}=\sum_{w\in R_n(1212)}t^{\bk(w)}p^{\rb(w)}q^{\rs(w)}.
\end{equation}
\end{theorem}

The special $q=1$ case of equidistribution~\eqref{equi:simion} was proved by Simion~\cite[Theorem~5.7]{Sim} via a bijection from noncrossing partitions to $\S_n(321)$. Note that Simion's bijection can not be applied to show~\eqref{equi:simion}. Consider for instance, $w=12334155$ associated to the noncrossing partition $16/2/34/5/78$, at the end of her paper. The RGF $w$ is mapped to $\sigma=24153867\in\S_n(321)$ under her bijection which satisfies $\bk(w)=5=\exc(\sigma)+1$ and $\rb(w)=13=\den(\sigma)$, but meanwhile $\rs(w)=4\neq2=\inv(\sigma)-\exc(\sigma)$. Our bijection $\psi$ is a function composition of two bijections to the Motzkin paths, one from $R_n(1212)$ to two-colored Motzkin paths of length $n-1$ due to Campbell et al.~\cite{CDD+} and the other is from the latter object to $\S_n(321)$, which is new to the best of our knowledge.

Let 
\begin{equation}\label{nara:def}
N_n(t,p,q):=\sum_{\pi\in\S_n(321)}t^{\exc(\pi)}p^{\den(\pi)}q^{\inv(\pi)-\exc(\pi)}.
\end{equation} Since counting noncrossing partitions of $[n]$ by the number of blocks minus $1$ gives the {\em $n$-th Narayana polynomial} (cf.~\cite[Sec.~2.6]{Pet}) 
$$
N_n(t)=\sum_{k=0}^{n-1}\frac{1}{n}{n\choose k+1}{n\choose k}t^k,
$$
the polynomial $N_n(t,p,q)$ is a {\em $(p,q)$-analog of the Narayana polynomial}. It is well known that $N_n(t)$ is {\em $\gamma$-positive}, i.e., it can be expanded as $N_n(t)=\sum_{k=0}^{\lfloor (n-1)/2\rfloor}\gamma_{n,k}t^k(1+t)^{n-1-2k}$ with $\gamma_{n,k}\in\N$. Many combinatorial interpretations for  $\gamma_{n,k}$ are known in the literature, see the excellent exposition by Petersen~\cite{Pet}. For instance, Postnikov, Reiner and Williams~\cite{prw} showed that $\gamma_{n,k}$ enumerates the {\em$231$-avoiding} permutations of length $n$, with $k$ {\em descents} and without {\em initial} and {\em double descents}. As one application of our bijection $\psi$, the following neat $q$-$\gamma$-positivity expansion for the $q$-Narayana polynomial $N_n(t,1,q)$ is derived. 

\begin{theorem} \label{thm:3} Let 
$$\widetilde{\S_{n,k}}(321):=\{\pi\in\S_n(321): \exc(\pi)=k\text{ and whenever } i<\pi_i, (\pi^{-1})_{i+1}>i\}.$$ Then,
\begin{equation}\label{eq:gamma}
\sum_{\pi\in\S_n(321)}t^{\exc(\pi)}q^{\inv(\pi)-\exc(\pi)}=\sum_{k=0}^{\lfloor (n-1)/2\rfloor}\biggl(\sum_{\pi\in\widetilde{\S_{n,k}}(321)}q^{\inv(\pi)-\exc(\pi)}\biggr)t^k(1+t)^{n-1-2k}.
\end{equation}
\end{theorem}
For example, we have $\widetilde{\S_{4,0}}(321)=\{1234\}$ and $\widetilde{\S_{4,1}}(321)=\{1423,3124,4123\}$. It then follows from~\eqref{eq:gamma} that
$$
N_4(t,1,q)=1+(3+2q+q^2)t+(3+2q+q^2)t^2+t^3=(1+t)^3+(2q+q^2)t(1+t).
$$
Note that Theorem~\ref{thm:3} implies the sequence of coefficients of the polynomial (in $t$) $N_n(t,1,q)$   is {\em palindromic} and {\em unimodal} in the sense that if $N_n(t,1,q)=\sum_{i=0}^{n-1}a_{n,i}(q)t^i$, then
\begin{itemize}
\item $a_{n,i}(q)=a_{n,n-1-i}(q)$ for  $0\leq i\leq n-1$ and
\item $a_{n,j+1}(q)-a_{n,j}(q)\in\N[q]$ for $0\leq j<(n-1)/2$.
\end{itemize}
This result can be compared with the $q$-$\gamma$-positivity expansion of the $(\inv,\exc)$-$q$-Eulerian polynomials due to Shin and Zeng \cite[Theorem~1]{SZ}.


The rest of this paper is organized as follows. In Section~\ref{sec:1}, we define the direct sum decomposition of RGFs and introduce the involution $\phi$ to prove Theorem~\ref{thm:1}. Based again on the direct sum decomposition, we construct in Section~\ref{sec:mak} a new involution $\tau$ on $R_n(1212)$ in the same spirit as  $\phi$ (but more involved) to prove Theorem~\ref{thm:mak}.
Theorem~\ref{thm:2} is proved in Section~\ref{sec:3} by constructing the bijection $\psi$ as function composition of two bijections to Motzkin paths. Section~\ref{sec:4} is devoted to further applications of $\psi$. Indeed, we first establish Theorem~\ref{thm:3} via a group action on Motzkin paths, then we continue to analyze Motzkin paths so as to obtain a recursion for $N_n(t,p,q)$ and a continued fraction expansion for the generating function of $N_n(t,1,q)$. We conclude our paper with some further remarks.







%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Direct sum and the involution $\phi$}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\label{sec:1}
%We first recall one operation that is usually used to combine shorter permutations into longer ones. Given two permutations $\pi\in\S_k$ and $\sigma\in\S_l$, the \emph{direct sum} of them is a permutation in $\S_{k+l}$ denoted by $\pi\oplus\sigma$, point-wisely it satisfies
%$$
%(\pi\oplus\sigma)(i)=
%\begin{cases}
%\pi(i), &\text{for $i\in[1,k]$};\\
%\sigma(i-k)+k, &\text{for $i\in[k+1,k+l]$}.
%\end{cases}
%$$
We first recall one operation that is usually used to combine shorter words into longer ones.
 Suppose $w=w_1w_2\ldots w_{l_1}$ and $v=v_1v_2\ldots v_{l_2}$ are two words on positive integers with $w$'s (resp.~$v$'s) maximum being $m_1$ (resp.~$m_2$).  We define the {\em direct sum} of $w$ and $v$, denoted $w\oplus v$, to be a word with maximum being $m_1+m_2$ and length being $l_1+l_2$, and point-wisely it satisfies
$$
(w\oplus v)_i=
\begin{cases}
w_i, &\text{for $i\in[1,l_1]$};\\
v_{i-l_1}+m_1, &\text{for $i\in[l_1+1,l_1+l_2]$}.
\end{cases}
$$
For example, we have $121\oplus 12=12134$. If a word can be written as the direct sum of two non-empty words, we call it \emph{direct sum decomposable} or simply \emph{decomposable}. It is clear that the direct sum operation is {\em associative}, i.e., $u\oplus (v \oplus w)=(u\oplus v) \oplus w$. The following two fundamental lemmas are crucial for constructing our involution $\phi$, the first of which should be immediate. 

\begin{lemma}\label{lem:fund}
(i) A word $u$ is in $R_{n-1}(1212)$ if and only if $u1$ is in $R_n(1212)$. (ii) The direct sum $w\oplus v$ is a $1212$-avoiding RGF if and only if both $w$ and $v$ are $1212$-avoiding RGFs.
\end{lemma}

Now with the operation of direct sum in mind, we can give a new characterization of RGFs avoiding $1212$.
\begin{lemma}\label{lem:rgf}
For any RGF $w=w_1\ldots w_n\in R_n$, the following are equivalent:
\begin{enumerate}
\item The RGF $w$ avoids $1212$.
%\item There are no $xyxy$ subwords in $\omega$.
\item If $w_i=w_{i'}$ for some $i<i'$, then for all $j'>i'$, either $w_{j'}\leq w_{i'}$ or $w_{j'}>\max\{w_1,\ldots, w_{i'}\}$.
\item $w$ is one of the following two types.
\begin{itemize}
\item Type I (indecomposable): $w$ ends with $1$, say $w=\hat{w}1\ldots 1$, where $\hat{w}$ (possibly empty) does not end with $1$ and avoids $1212$. 
\item Type II (decomposable): $w$ does not end with $1$, and there exists some non-empty $1212$-avoiding RGFs $u$ and $v$, such that $w=u\oplus v$.
\end{itemize}
\end{enumerate}
\end{lemma}
\begin{proof}
The equivalence of (1) and (2) is Lemma~5.2 in~\cite{CDD+}. We show here their equivalence with (3). When $w$ satisfies (3), then $w$ avoids $1212$ by Lemma~\ref{lem:fund}. It remains to show that if the RGF $w$ avoids $1212$, then it must be one of the two types in (3).

%When $\omega$ is of type I or II, the proof is straightforward and left to the readers. We only show that when $\omega$ is neither layered nor ending with $1$, it avoids $1212$ if and only if it is decomposable into two $1212$-avoiding RGFs. Actually, when $\omega=\mu\oplus\nu$ with $\mu$ and $\nu$ avoiding $1212$, suppose on the contrary that there is some subword $xyxy$ in $\omega$, then this subword must intersect with both intervals in $\omega$ that corresponds to $\mu$ and $\nu$ respectively, since $\mu$ and $\nu$ are $1212$-avoiding. But this leads to contradiction too, due to the definition of direct sum. So we see $\omega$ must avoid $1212$ as well.
Find the rightmost $1$ in $w$, say at position $i$. If $i=n$, then clearly $w$ is type I. Otherwise, $1\leq i < n$. Let $u=w_1w_2\ldots w_i$. Since $w_i$ is the rightmost $1$ of $w$, according to condition (2), we have $w_{j}>\max\{w_1,\ldots,w_{i}\}$ for all $j>i$. Hence, $w=u\oplus v$, where $v_j=w_{i+j}-\bk(u)$ for all $1\leq j\leq n-i$. By Lemma~\ref{lem:fund}, both $u$ and $v$ are RGFs and avoiding $1212$. This shows $w$ is type II in this case and the proof is complete.
\end{proof}


%However, when we require that $\mu$ ends with $1$,  such a decomposition exists and is indeed unique. For the rest of the paper, when we say ``decompose'' $\omega$, we are referring to this unique decomposition.
%\end{remark}
We are ready to define our key map $\phi$ for Theorem~\ref{thm:1}. 
\begin{Def}
For any RGF $w$ that avoids $1212$, we define the map $\phi$ recursively and according to the type of $w$ (set $\phi(\emptyset)=\emptyset$):
\begin{itemize}
\item Type I. Suppose $w=\hat{w}1^k$, where $k\geq1$ and $\hat{w}$ (possibly empty) does not end with $1$. Define $$\phi(w)=\phi(\hat{w})1^k.$$
%\item Type II. Suppose $w=1^{n_1}2^{n_2}\ldots m^{n_m}$, then let $$\phi(\omega)=1^{n_m}2^{n_{m-1}}\ldots m^{n_1}.$$
\item Type II. Suppose $w=u\oplus v$, then let $$\phi(w)=\phi(v)\oplus\phi(u).$$
\end{itemize}
\end{Def}

Note that Lemma~\ref{lem:fund} ensures  $\phi(w)$  is  a $1212$-avoiding RGF.
 In general, the direct sum decomposition of a $1212$-avoiding RGF is not unique. For example, $12134=121\oplus 12=1213\oplus 1$. However, the following lemma shows that $\phi$ is independent of the decomposition of $w$, hence well-defined.

\begin{lemma}\label{lem:well}
Suppose $w\in R_n(1212)$ has two different decompositions $w=u\oplus v=u'\oplus v'$. Then, $\phi(v)\oplus \phi(u)=\phi(v')\oplus \phi(u')$.
\end{lemma}
\begin{proof} We prove this result by induction on the length of $w$. Without loss of generality, 
we suppose $u\in R_k(1212)$ and $u'\in R_l(1212)$ with $1\leq k<l<n$. Then, there exists a unique $c\in R_{l-k}(1212)$ such that $u'=u\oplus c$ and $v=c\oplus v'$.  Hence, by induction on the length of $w$ and by the associativity of the direct sum,
\begin{align*}
\phi(v)\oplus \phi(u)=\phi(c\oplus v')\oplus \phi(u)&=(\phi(v')\oplus \phi(c))\oplus \phi(u)\\
&=\phi(v')\oplus (\phi(c)\oplus \phi(u))=\phi(v')\oplus \phi(u'),
\end{align*}
as desired. 
\end{proof}

The following result provides a proof of Theorem~\ref{thm:1}.

\begin{theorem}\label{4stats}
The map $\phi$ is an involution on $R_n(1212)$ such that 
\begin{align}\label{eq-4stats}
(\ls,\rb,\lb,\bk)(w)=(\rb,\ls,\lb,\bk)(\phi(w))
\end{align}
for each $w\in R_n(1212)$.
\end{theorem}
\begin{proof}
This result can be checked easily by induction on $n$. Notice that $\phi$ preserves the type of $1212$-avoiding RGFs. We discuss in two cases according to the type of $w$.

Type I: suppose $w=\hat{w}1^k$, where $k\geq1$ and $\hat{w}$ (possibly empty) does not end with $1$. Thus, $\phi^2(w)=\phi(\phi(\hat{w})1^k)=\phi^2(\hat{w})1^k=\hat{w}1^k=w$. When $\hat{w}=\emptyset$, clearly $\phi(w)=w=1^k$, $\ls(w)=\rb(w)=0$ so \eqref{eq-4stats} holds trivially. For the following we assume $\hat{w}\neq \emptyset$ and we have
\begin{align*}
&\rb(\phi(w))=\rb(\phi(\hat{w})1^k)=\rb(\phi(\hat{w}))=\ls(\hat{w})=\ls(w),\\
%&\ls(\phi(w))=\rb(\phi^2(w))=\rb(w),\\
&\bk(\phi(w))=\bk(\phi(\hat{w})1^k)=\bk(\phi(\hat{w}))=\bk(\hat{w})=\bk(w)\,\,\,\,\text{and}\\
&\lb(\phi(w))=\lb(\phi(\hat{w})1^k)=\lb(\phi(\hat{w}))+k\times(\bk(\phi(\hat{w}))-1)\\
&\phantom{\lb(\phi(w))}=\lb(\hat{w})+k\times(\bk(\hat{w})-1)=\lb(w).
\end{align*}

Type II: suppose $w=u\oplus v$. Then, $\phi^2(w)=\phi(\phi(v)\oplus\phi(u))=\phi^2(u)\oplus \phi^2(v)=u\oplus v=w$. If $v$ has length $l$ with $1\leq l<n$, then
\begin{align*}
\rb(\phi(w))&=\rb(\phi(v)\oplus\phi(u))=\rb(\phi(v))+\rb(\phi(u))+l\times\bk(\phi(u))\\
&=\ls(v)+\ls(u)+l\times\bk(u)=\ls(u\oplus v)=\ls(w).
%\ls(\phi(w))&=\rb(\phi^2(w))=\rb(w).
\end{align*}
Moreover, we have
$$
\bk(\phi(w))=\bk(\phi(v))+\bk(\phi(u))=\bk(v)+\bk(u)=\bk(w)
$$
and
$$
\lb(\phi(w))=\lb(\phi(v))+\lb(\phi(u))=\lb(v)+\lb(u)=\lb(w).
$$

In either case the statement is true, which completes the proof of Theorem~\ref{4stats}.
\end{proof}

For example, if $w=1112322145541$, then $\phi(w)=\phi(111232214554) 1=(\phi(1221)\oplus\phi(11123221))1=(1121\oplus(\phi(111\oplus1211)1))1=
(1121\oplus(\phi(1211)\oplus\phi(111)1))1=(1121\oplus12113331) 1=1121343355531$. We have 
$$(\ls,\rb,\lb,\bk)(w)=(19,24,9,5)=(\rb,\ls,\lb,\bk)(\phi(w)).$$
%Furthermore, if we define $\ls(w_i)=\#\{w_j : j<i, w_j<w_i\}$ and introduce the set-valued extension of $\ls(w)$ as the multiset $\LS(w)=\{\ls(w_1),\ls(w_2),\ldots,\ls(w_n)\}$

\begin{remark}\label{invo:sim}
We recall Simion's involution $\phi'$ in \cite{Sim} that proves Theorem~\ref{thm:1}. Given a noncrossing partition $\Pi$ of $[n]$ written in standard form $B_1/B_2/\cdots/B_k$. Let $f_i=\min\{a: a\in B_i\}$ for $1\leq i\leq k$ and $f_{k+1}=n+1$. Relabel the elements of $[n]$ as follows: the elements of the last block $B_k$ are relabeled $1,2,\ldots,|B_k|$ in increasing order; next, the elements of the penultimate block $B_{k-1}$ are relabeled $|B_k|+1,|B_k|+2,\ldots, |B_k|+|B_{k-1}|$ in increasing order; and so on. Now, the $i$-th block of $\phi'(\Pi)$ consists of the set of new labels given to the elements in the original interval $\{f_{k-i+1},f_{k-i+1}+1,\ldots, f_{k-i+2}-1\}$.

For example, for $\Pi=1\,2\,3\,8\,13/4\,6\,7/5/9\,12/10\,11$,  $\phi'(\Pi)=1\,2\,4\,13/3/5\,7\,8\,12/6/9\,10\,11$. Note that $w(\Pi)=w=1112322145541$ and $\phi(w)=1121343355531$ as computed in  the previous example. Now we see that $\phi(w(\Pi))=w(\phi'(\Pi))$ for this particular $\Pi$. In fact, this coincidence is true in general. One possible way to see this is by induction on $n$ and by distinguishing two types of noncrossing partitions of $[n]$: (i)  $n$ is in the first block and (ii) $n$ is not in the first block, which corresponds to type I and II of RGFs under the natural bijection. The details are left to the interested reader.
\end{remark}

For any $w\in R_n$, let us define the multiset-valued extension of $\ls(w)$ as the multiset 
$$\LS(w):=\{\ls(w_1),\ls(w_2),\ldots,\ls(w_n)\},$$ where $\ls(w_i)=\#\{w_j : j<i, w_j<w_i\}$. Similarly, we define $\LB(w),\RS(w)$ and $\RB(w)$. Actually, the involution $\phi$ can be applied  to show the following multiset-valued extension of Theorem~\ref{thm:1} without any difficulty.

\begin{theorem}\label{thm:multi}
For any $n\geq 0$, the two mixed four-variable statistics (both integer-valued and multiset-valued)
$$ (\LS,\RB,\LB,\bk) \text{ and } (\RB,\LS,\LB,\bk)$$
are equidistributed on $R_n(1212)$.
\end{theorem}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Steingr\'imsson's set partition statistic ``$\mak$"}%
\label{sec:mak}%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

 In~\cite{es}, Steingr\'imsson introduced many statistics on (ordered or unordered) set partitions, of which the statistic ``$\mak$" is quite interesting. This statistic was inspired by the permutation statistic under the same name ``$\mak$''  introduced by Foata and Zeilberger~\cite{fz}. Here we will  define ``$\mak$'' on RGFs directly as follows. 
 
 Let $w\in R_n$ be a RGF.  For each $i\in[n]$, define 
 $$\lcs_i(w):=\#\{w_j: j<i, w_j<w_i\text{ and $w_k\neq w_j$ for all $k>j$}\}.$$
 Let us denote $\lcs(w)=\sum_{i}\lcs_i(w)$. For example, if $w=12334155\in R_8$, then $\lcs(w)=0+0+1+1+2+0+4+4=12$. Under the natural bijection, this statistic agrees with the ``{\bf l}eft {\bf c}loser {\bf s}maller'', also denoted ``$\lcs$'', defined on set partitions in~\cite{es}. Now the statistic ``$\mak$'' can be defined by 
 $$
 \mak(w):=\lb(w)+\lcs(w).
 $$ 
  Continuing with our running example, we have $\mak(w)=3+12=15$. It turns out that ``$\mak$'' is equidistributed with ``$\rb$'' on $R_n$ and even more  is true.
 
 \begin{theorem}[See~\cite{WW,kz,kaz}]
 For any $n\geq 0$, we have the quadruple equidistribution
\begin{equation}\label{thm:wz}
 \sum_{w\in R_n}p_1^{\mak(w)}p_2^{\rb(w)}q^{\rs(w)}t^{\bk(w)}= \sum_{w\in R_n}p_1^{\rb(w)}p_2^{\mak(w)}q^{\rs(w)}t^{\bk(w)}
\end{equation} 
 Moreover, there holds 
 \begin{equation}\label{eq:wwkz}
 \sum_{w\in R_n\atop{\bk(w)=k}}p^{\rb(w)}q^{\rs(w)}=S_{p,q}(n,k)= \sum_{w\in R_n\atop{\bk(w)=k}}p^{\mak(w)}q^{\rs(w)},
 \end{equation}
 where $S_{p,q}(n,k)$ is the $(p,q)$-Stirling number of the second kind defined by the recursion:
 $$
 S_{p,q}(n,k)=
 \begin{cases}
\,\, p^{k-1}S_{p,q}(n-1,k-1)+\biggl(\sum\limits_{i=0}^{k-1}p^iq^{k-1-i}\biggr)S_{p,q}(n-1,k)&\;\text{if $0<k\leq n$,}\\
\,\, \delta_{n,k}&\;\text{if $n=0$ or $k=0$.}
 \end{cases}
 $$
 \end{theorem}
 
 Note that the first identity of~\eqref{eq:wwkz} is due to Wachs and White~\cite{WW}, while the second was proved by Ksavrelof and Zeng~\cite{kz} in answering a conjecture of Steingr\'imsson~\cite{es}. The quadruple equidistribution~\eqref{thm:wz}, as well as two different generalizations to ordered set partitions, were proved by  Kasraoui and Zeng in~\cite{kaz}  via the intermediate structure of path diagrams. Our quadruple equidistribution stated in Theorem~\ref{thm:mak} is a restricted version of~\eqref{thm:wz}.
 
 
 
 
 Based on the direct sum decomposition structure showed in Lemma~\ref{lem:rgf}, 
 we will construct recursively a new involution $\tau:R_n(1212)\rightarrow R_n(1212)$, which interchanges the statistics ``$\mak$'' and ``$\rb$'' but preserves the statistics ``$\rs$'' and ``$\bk$''. 
 This leads to a proof of Theorem~\ref{thm:mak}.
 
\begin{Def}
For any $w=w_1\ldots w_n\in R_n(1212)$, we define $\tau(w)=\tau(w)_1\tau(w)_2\ldots \tau(w)_n$ recursively  according to the type of $w$ (see Example~\ref{ex:1}). Set $\tau(\emptyset)=\emptyset$ and suppose $\tau$ is already defined for all $R_m(1212), 0\leq m<n$.
\begin{itemize}
\item Type I. This means $w$ must end with $1$. Let $\tilde{w}$ be the word obtained from $w$ by subtracting each letter of $w$ by $1$ and then omitting all the $0$s, and for any $k$ with $w_k\neq1$, define $$\epsilon(k):=|\{j\geq k: w_j\neq 1\}|.$$ Then, 
$$ \tau(w)_i:=\begin{cases}
1 &\quad\text{if $w_{n+1-i}=1$,}\\
\tau(\tilde{w})_{\epsilon(n+1-i)}+1 &\quad\text{if $w_{n+1-i}\neq 1$.}
\end{cases} $$
For example, given $w=1112322145541$, we have $\tilde{w}=12113443$ and $\epsilon(4)=8, \epsilon(5)=7, \epsilon(9)=4$, etc.
\item Type II. Suppose $w=u\oplus v$, then let $$\tau(w)=\tau(v)\oplus\tau(u).$$
\end{itemize}
\end{Def}
When $w$ is of type II, with the aid of Lemma~\ref{lem:fund} and \ref{lem:well}, it is clear that $\tau(w)$ also avoids $1212$ and is independent of the decomposition of $w$. But for those $w$ of type I, we need the following lemma to see that $\tau$ is indeed well-defined.
\begin{lemma}
For any $w\in R_n(1212)$:
\begin{align}\label{cond}
\text{if }\;\tau(w)_i=\tau(w)_j, \quad \text{then }\; w_{n+1-i}=w_{n+1-j}.
\end{align}
Consequently, $\tau(w)\in R_n(1212)$ and $\tau$ is well-defined.
\end{lemma}
\begin{proof}
We prove \eqref{cond} by induction on $n$. It holds trivially for $n=1$ since $\tau(1)=1$. Now suppose $w\in R_n(1212)$ is of type I. If $\tau(w)_i=\tau(w)_j=1$, then by definition $w_{n+1-i}=w_{n+1-j}=1$. Otherwise $\tau(w)_i=\tau(w)_j=a>1$, hence $\tau(\tilde{w})_{\epsilon(n+1-i)}=\tau(\tilde{w})_{\epsilon(n+1-j)}=a-1$. Now since $\tilde{w}$ is of shorter length than $w$, say $\tilde{w}\in R_m(1212), m<n$, by inductive hypothesis we get $\tilde{w}_{m+1-\epsilon(n+1-i)}=\tilde{w}_{m+1-\epsilon(n+1-j)}$. A moment of reflection reveals that the $(m+1-\epsilon(n+1-i))$-th letter in $\tilde{w}$ is indeed the $(n+1-i)$-th letter in $w$. We get $w_{n+1-i}=w_{n+1-j}$ as desired. The case with $w$ being of type II is similar by induction, thus omitted. 

Next we use \eqref{cond} to show that $\tau(w)\in R_n(1212)$ for any $w$ of type I. Again we use induction on $n$. Suppose on the contrary that $\tau(w)\not\in R_n(1212)$, by induction we can assume such occurrence of pattern $1212$ involves letter $1$. More precisely, suppose there exists some indices $i<j<k$ such that $$\tau(w)_1=\tau(w)_j=1, \quad\tau(w)_i=\tau(w)_k=a>1.$$ Then by \eqref{cond} we have 
$$w_{n}=w_{n+1-j}=1, \quad w_{n+1-i}=w_{n+1-k}=a'>1.$$
Now the subword $w_1w_{n+1-k}w_{n+1-j}w_{n+1-i}$ forms a pattern $1212$ in $w$, a contradiction. This completes the proof.
\end{proof}
The following result parallels Theorem~\ref{4stats} and proves Theorem~\ref{thm:mak}.
\begin{theorem}\label{4stats2}
The map $\tau$ is an involution on $R_n(1212)$ such that 
\begin{align}\label{eq-4stats2}
(\mak,\rb,\rs,\bk)(w)=(\rb,\mak,\rs,\bk)(\tau(w))
\end{align}
for each $w\in R_n(1212)$.
\end{theorem}
\begin{proof}
That $\tau$ is an involution and $\bk(\tau(w))=\bk(w)$ can be easily checked by definition and induction. Notice that $\tau$ also preserves the type of $1212$-avoiding RGFs, so we deal with two types respectively. 

Type II is simpler so we consider it first. Given any $w=u\oplus v\in R_n(1212)$, suppose $u\in R_m(1212), 1\leq m < n$, then $v\in R_{n-m}(1212)$. We compute directly the remaining three statistics.
\begin{align*}
\rb(\tau(w))&=\rb(\tau(v)\oplus\tau(u))=(n-m)\times\bk(u)+\rb(\tau(v))+\rb(\tau(u))\\
&=(n-m)\times\bk(u)+\mak(v)+\mak(u)\\
&=(\lb(u)+\lb(v))+((n-m)\times\bk(u)+\lcs(u)+\lcs(v))\\
&=\lb(w)+\lcs(w)=\mak(w),\\
\mak(\tau(w))&=\mak(\tau(v)\oplus\tau(u))=\lb(\tau(v)\oplus\tau(u))+\lcs(\tau(v)\oplus\tau(u))\\
&=\lb(\tau(v))+\lb(\tau(u))+\lcs(\tau(v))+\lcs(\tau(u))+m\times\bk(v)\\
&=\mak(\tau(v))+\mak(\tau(u))+m\times\bk(v)\\
&=\rb(v)+\rb(u)+m\times\bk(v)=\rb(w),\\
\rs(\tau(w))&=\rs(\tau(v)\oplus\tau(u))=\rs(\tau(v))+\rs(\tau(u))=\rs(v)+\rs(u)=\rs(w).
\end{align*}

Type I is more involved. First note that since $\tau$ is an involution, we can strengthen \eqref{cond} to the following form:
\begin{align}\label{cond'}
\tau(w)_i=\tau(w)_j \quad \text{if and only if}\quad w_{n+1-i}=w_{n+1-j}.
\end{align}
This is the key to the ensuing argument. Given any $w$ of type I, for each $a$, $1<a\leq \bk(w)$, we consider the maximal subword of $w$ formed purely by $1$ and $a$, it must be of the following form since $w$ avoids $1212$
$$
w^{(a)}=w_{i_1}\ldots w_{i_r}w_{j_1}\ldots w_{j_s}w_{k_1}\ldots w_{k_t}=1^r a^s 1^t,
$$
where the sub-indices are the original ones in $w$. As a result of property \eqref{cond'}, we see that
\begin{align*}
\tau(w)^{(b)}&=\tau(w)_{n+1-k_t}\ldots \tau(w)_{n+1-k_1}\tau(w)_{n+1-j_s}\ldots \tau(w)_{n+1-j_1}\tau(w)_{n+1-i_r}\ldots \tau(w)_{n+1-i_1}\\
&=1^t b^s 1^r
\end{align*}
must be the maximal subword of $\tau(w)$ composed of $1$ and $b$ only, for certain $1<b\leq \bk(w)$. And when $a$ runs over $2,3,\ldots,\bk(w)$, so does $b$. Now we analyse their contributions to each of the three statistics.
\begin{itemize}
\item $\mak=\lb+\lcs$: $w^{(a)}$ adds $t$ to $\lb$, $0$ to $\lcs$, while $\tau(w)^{(b)}$ adds $r$ to $\lb$, $0$ to $\lcs$;
\item $\rb$: $w^{(a)}$ adds $r$ to $\rb$, while $\tau(w)^{(b)}$ adds $t$ to $\rb$;
\item $\rs$: both $w^{(a)}$ and $\tau(w)^{(b)}$ add $s$ to $\rs$.
\end{itemize}
We sum up all the contributions when $a$ and $b$ traverse $2,3,\ldots,\bk(w)$ respectively, and use induction on $\tilde{w}$, this amounts to establish \eqref{eq-4stats2}, and the proof ends here.
\end{proof}

\begin{example}\label{ex:1}
For instance, if $w=111\blue{2322}1\blue{4554}1$, then we need to first compute 
$$
\tau(\tilde{w})=\tau(1211\oplus 1221)=\tau(1221)\oplus\tau(1211)=1221\oplus1121=\blue{12213343},
$$
which in turn gives us 
$\tau(w)=1\blue{2332}1\blue{4454}111$.
And we check that
$$
(\mak,\rb,\rs,\bk)(w)=(17,24,11,5)=(\rb,\mak,\rs,\bk)(\tau(w)).
$$
\end{example}
%For example, if $w=11223342221111516761118=1122334222111151676111\oplus1$, then we need to first compute 
%\begin{align*}
%\tau(112231114565)&=\tau(11223111\oplus 1232)=\tau(1232)\oplus\tau(11223111)\\
%&=1213\oplus11123311=121344456644,
%\end{align*} 
%which in turn gives us 
%\begin{align*}
%&\tau(1122334222111151676111)=1112321411115556775511,\\
%&\tau(w)=12223432522226667886622.
%\end{align*}
%And we check that
%$$
%(\mak,\rb,\rs,\bk)(w)=(81,64,16,8)=(\rb,\mak,\rs,\bk)(\tau(w)).
%$$





%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The bijection $\psi$ and a proof of Theorem~\ref{thm:2}}%
\label{sec:3}%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


The Motzkin paths are at the heart of our proof of Theorem~\ref{thm:2}. Recall that a {\em Motzkin path} of length $n$ is a lattice path in $\N^2$ starting at $(0,0)$, ending at $(n,0)$, with three possible steps: 
$$
\text{$(1,1)=U$ (up step), $(1,-1)=D$ (down step)\,\,\,and\,\,\,$(1,0)=H$ (horizontal step).}
$$
 For our purpose, we color each horizontal step of a Motzkin path by color $\a$ or $\b$. We call such a Motzkin path a {\em two-colored Motzkin path}. See Fig.~\ref{fig:motzkin} for a display of the two-colored Motzkin path $U\b U\a UD\b DDU\a D$. Denote by  $\M_n^{(2)}$ the set of all two-colored Motzkin paths of length $n$. Note that  $\M_{n-1}^{(2)}$ is enumerated by the 
famous {\em$n$-th Catalan number} 
$$C_n=\frac{1}{n+1}{2n\choose n},$$ as well as $R_n(1212)$ and $\S_n(321)$. There  is a bijection from 
$\M_{n-1}^{(2)}$ to $R_n(1212)$ due to Campbell et al.~\cite{CDD+} which forms one step of our bijection $\psi$ that we now describe.


 \begin{figure}%[ht]
\begin{center}
\begin{tikzpicture}[scale=.8]
\draw[step=1,color=gray] (0,0) grid (12,3); \draw [very thick]
(0,0)--(1,1) --(2,1)--(3,2)--(4,2)--(5,3)--(6,2)--(7,2)--(8,1)--(9,0)--(10,1)--(11,1)--(12,0);
\draw (1.5,1.3) node{$\b$}; \draw (3.5,2.3) node{$\a$}; 
\draw(6.5,2.3) node{$\b$}; \draw (10.5,1.3) node{$\a$};
%%labeling
\draw (0.5,-0.4) node{$1$};\draw (1.5,-0.4) node{$2$};
\draw (2.5,-0.4) node{$3$};\draw (3.5,-0.4) node{$4$};
\draw (4.5,-0.4) node{$5$};\draw (5.5,-0.4) node{$6$};
\draw (6.5,-0.4) node{$7$};\draw (7.5,-0.4) node{$8$};
\draw (8.5,-0.4) node{$9$};\draw (9.5,-0.4) node{$10$};
\draw (10.5,-0.4) node{$11$};\draw (11.5,-0.4) node{$12$};
\draw[dashed] (2.6,1.5)--(7.4,1.5);

\end{tikzpicture}
\end{center}
\caption{A two-colored Motzkin path in $\M_{12}^{(2)}$}
\label{fig:motzkin}
\end{figure}

% \begin{figure}%[ht]
%\begin{center}
%\begin{tikzpicture}[scale=.8]
%\draw[step=1,color=gray] (0,0) grid (12,3); \draw [very thick]
%(0,0)--(1,1) --(2,1)--(3,2)--(4,2)--(5,3)--(6,2)--(7,2)--(8,1)--(9,0)--(10,1)--(11,1)--(12,0);
%%lables
%\draw (1.5,0.7) node{$\b$};
%\draw (3.5,1.7) node{$\a$};
%\draw (6.5,1.7) node{$\b$}; 
%\draw (10.5,0.7) node{$\a$};
%\draw (0.25,0.75) node{$s_1$};
%\draw (1.5,1.3) node{$s_2$};
%\draw (2.3,1.75) node{$s_3$};
%\draw (3.5,2.3) node{$s_4=\a$};
%\draw (4.3,2.75) node{$s_5$};
%\draw (5.7,2.75) node{$s_6$};
%\draw (6.5,2.3) node{$s_7$};
%\draw (7.7,1.75) node{$s_8$};
%\draw (8.7,0.75) node{$s_9$};
%\draw (9.3,0.75) node{$s_{10}$};
%\draw (10.5,1.3) node{$s_{11}$};
%\draw (11.75,0.75) node{$s_{12}$};
%%pairs
%\draw[dashed] (2.6,1.5)--(7.4,1.5);
%\end{tikzpicture}
%\end{center}
%\caption{A two-colored Motzkin path}
%\label{fig:motzkin}
%\end{figure}
 
Let $M=s_1s_2\ldots s_{n-1}$ be a two-colored Motzkin path in $\M_{n-1}^{(2)}$. Given a step $s_i$ in $M$, we realize $s_i$ geometrically as the line segment in the plane that connects two lattice points in the obvious way.  If $s_i=U$ then we pair it with the first $D$-step $s_j$ to its right, i.e. $j>i$, whose midpoint has  the same height as the midpoint of $s_i$. Continuing with our running example path, $s_3$ is paired with $s_8$ (see the dashed line in Fig.~\ref{fig:motzkin}).
The associated RGF $\psi_1(M)=w=w_1\ldots w_n$ of $M$ is then defined as follows. Let $w_1=1$ and
 $$
w_{i+1}=
\begin{cases}
\,\,1+\max\{w_1,\ldots,w_{i}\}\quad&\text{if $s_i=U$ or $s_i=\b$},\\
\,\,w_i\quad&\text{if $s_i=\a$},\\
\,\,w_j\quad&\text{if $s_i=D$ is paired with the $U$-step $s_j$}.
\end{cases}
$$
 For instance, for the two-colored Motzkin path $M$ in Fig.~\ref{fig:motzkin}, we have 
 $\psi_1(M)=w=1234454631771$ and $\rb(w)=28,\rs(w)=16,\bk(w)=7$. Campbell et al.~\cite[Th.~5.7]{CDD+} showed that $\psi_1: \M_{n-1}^{(2)}\rightarrow R_n(1212)$ is a bijection that satisfies the property 
 \begin{equation*}\label{lem:area}
 \area(M)=\rs(w), 
 \end{equation*}
 where $w=\psi_1(M)$ and $\area(M)$ is the area between $M$ and the $x$-axis. More precisely, they proved that $\rs(w_i)$ equals $h(s_i)$ (resp.~$h(s_i)+1$) if $s_i=\a,\b$ or $U$ (resp.~$s_i=D$).   But what  are the two statistics ``$\rb$'' and ``$\bk$'' on RGFs corresponding to?
 
 To answer this question, we need to introduce a  set-valued extension of ``$\rb$'', which is different from the multiset-valued statistic ``$\RB$'' introduced earlier. 
For each RGF $w\in R_n(1212)$,  a {\em shifted left-to-right maximum (position)} of $w$ is an index $i\in[n-1]$ such that $w_{i+1}>w_j$ for all $j<i+1$. Let $\SLR(w)$ be the set of all shifted left-to-right maximum of $w$. For example, $\SLR(1234454631771)=\{1,2,3,5,7,10\}$. 
 \begin{lemma}\label{lem:slr}
 For $w\in R_n(1212)$, we have 
 $$
 \bk(w)=\#\SLR(w)+1\quad\text{and}\quad\rb(w)=\sum_{i\in\SLR(w)}i.
 $$
 \end{lemma}
 \begin{proof}
 For any integer $t\in\{2,3,\ldots,\bk(w)\}$, from left to right, $w_i$ is the first occurrence of letter $t$ in $w$
if and only if $i-1$ is a shifted left-to-right maximum of $w$. Thus, the first equality follows. 

Note that if $w_k=w_{k'}$ for some $k<k'$, then all the letters in between positions $k$ and $k'$ should be no less than $w_k$. Otherwise, say $w_l<w_k$ with $k< l< k'$, then there must exist a letter $w_{l'}=w_l$ that occurs before $w_k$, but this means $w_{l'}w_kw_lw_{k'}$ is a $1212$ pattern, a contradiction. Therefore, for any fixed letter $t\in\{2,3,\ldots,\bk(w)\}$, only the first occurrence of $t$ in $w$ could contribute one to $\rb(w_i)$ for each letter $w_i$ ($w_i<t$) to the left of it.
The second  equality then follows.
 \end{proof}
 
 
Let us introduce the statistic $\Ub(M)$ for a two-colored Motzkin path $M\in\M_{n-1}^{(2)}$ as
$$
\Ub(M):=\{i\in[n-1]: s_i=U\,\,\,\text{or}\,\,\,\,s_i=\b\},
$$
with its cardinality denoted $\ub(M):=\#\Ub(M)$. It is clear from the definition of $\psi_1$ that $\Ub(M)=\SLR(\psi_1(M))$. Hence,

\begin{lemma}\label{bij:psi1}
For each $M\in\M_{n-1}^{(2)}$, we have
$$
\Ub(M)=\SLR(\psi_1(M))\quad\text{and}\quad\area(M)=\rs(\psi_1(M)).
$$
\end{lemma}


Next, we will introduce a bijection $\psi_2: \S_n(321)\rightarrow\M_{n-1}^{(2)}$ which transforms the pair $(\EXC,\inv-\exc)$ to $(\Ub,\area)$. Our bijection $\psi_2$ is inspired by a bijection of Foata and Zeilberger~\cite{fz} from permutations to {\em Laguerre histories} and a bijection of Cheng et al.~\cite{ceks} from $321$-avoiding permutations to two-colored Motzkin paths. 

 We need two important vectors to keep track of the values and positions of excedances.
 For $\pi=\pi_1\ldots\pi_n\in\S_n(321)$, let 
$$
\val(\pi)=(v_1,\ldots,v_n)\quad\text{and}\quad\pos(\pi)=(p_1,\ldots,p_n),
$$
where $v_i=\chi(i>\pi^{-1}_i)$ and $p_i=\chi(\pi_i>i)$. For instance, for  $\pi=3\,7\,8\,1\,9\,2\,10\,4\,5\,13\,6\,11\,12$ in $\S_{13}(321)$, we have
$$\val(\pi)=(0,0,1,0,0,0,1,1,1,1,0,0,1),\quad\pos(\pi)=(1,1,1,0,1,0,1,0,0,1,0,0,0).$$
Now, the associated two-colored Motzkin path $\psi_2(\pi)=M=s_1s_2\ldots s_{n-1}$ is defined by
\begin{align}\label{UbDa}
s_{i}=
\begin{cases}
\,\,U\quad&\text{if $v_{i+1}=0$ and $p_i=1$},\\
\,\,\b\quad&\text{if $v_{i+1}=p_i=1$},\\
\,\,D\quad&\text{if $v_{i+1}=1$ and $p_i=0$},\\
\,\,\a\quad&\text{if $v_{i+1}=p_i=0$}.
\end{cases}
\end{align}
Continuing with our  example, $\psi_2(3\,7\,8\,1\,9\,2\,10\,4\,5\,13\,6\,11\,12)=U\b U\a UD\b DDU\a D$, which is the path in Fig.~\ref{fig:motzkin}. 

We first need to show that $\psi_2$ is well defined, that is the path $M$ as produced above ends on $x$-axis and stays weakly above it during the process. In other words, we require the number of $U$'s in any prefix of $M$ is at least as great as the number of $D$'s and with equality for $M$ in its entirety. This follows from the simple fact that for any fixed $i\in[n-1]$,
$$
|\{j\in\EXC(\pi): j\leq i\}|\geq|\{j\in\EXC(\pi): \pi_j\leq i+1\}|,
$$
and with equality when $i=n-1$. 

For each  $i\in\EXC(\pi)$ (resp.~$i\in\NEXC(\pi)$), we call $\pi_i$ the {\em excedance (resp.~non-excedance)  value}  of $\pi$. We will also need the following characterization of $321$-avoiding permutations, which is  folkloric in pattern avoidance. 

\begin{lemma}\label{lem:den}
A permutation is $321$-avoiding if and only if both the subsequence formed  by its excedance values and the one formed by the remaining non-excedance values are increasing. Equivalently, $\pi$ is $321$-avoiding if and only if $\inv(\EXC^*(\pi))=\inv(\NEXC^*(\pi))=0$.
\end{lemma}

We are ready for the key lemma of this section. 
\begin{lemma}\label{bij:psi2}
The mapping $\psi_2: \S_n(321)\rightarrow\M_{n-1}^{(2)}$ is a bijection such that for each $\pi\in\S_n(321)$, we have
\begin{equation}\label{eq:exc}
\EXC(\pi)=\Ub(\psi_2(\pi))\quad\text{and}\quad(\inv-\exc)(\pi)=\area(\psi_2(\pi)).
\end{equation}
\end{lemma}

\begin{proof}
Given a two-colored Motzkin path $M$ that is an image under $\psi_2$, we have the information for the positions and values of all the excedances of $\pi$ such that $\psi_2(\pi)=M$. Hence, by Lemma~\ref{lem:den} such a $\pi$ must be unique. This shows that $\psi_2$ is injective and thus bijective, since the cardinalities  of $\M_{n-1}^{(2)}$ and $\S_n(321)$ are both the Catalan number $C_n$.

The first equality in~\eqref{eq:exc} is clear from the definition of $\psi_2$ and we will prove the second one by calculating $(\inv-\exc)(\pi)$ via the two associated vectors $\val(\pi)$ and $\pos(\pi)$. Indeed, using the characterization given in Lemma~\ref{lem:den}, we see that for any $\pi=\pi_1\ldots\pi_n\in\S_n(321)$, an excedance of $\pi$ must also be a left-to-right maximum of $\pi$. Consequently, an excedance, say $\pi_i$, contributes $\pi_i-i$ to the value of $\inv(\pi)$, while each non-excedance contributes nothing. This observation leads to the following computation of $\inv(\pi)$ and $\exc(\pi)$:
\begin{align*}
\inv(\pi)&=\langle\val(\pi), \n\rangle-\langle\pos(\pi), \n\rangle,\quad \n=(1,2,\ldots,n),\\
\exc(\pi)&=\langle\val(\pi), \e\rangle=\langle\pos(\pi), \e\rangle,\quad \e=(1,1,\ldots,1),
\end{align*}
where  $\langle\cdot{,}\cdot\rangle$ is the usual {\em inner product} for vectors in $\mathbb{R}^n$. Note that by definition, $\val(\pi)$ (resp.~$\pos(\pi)$) always begins (resp.~ends) with $0$. Now suppose $\psi_2(\pi)=M=s_1s_2\ldots s_{n-1}$, then using \eqref{UbDa} and a little bit of linear algebra, we get
$$
(\inv-\exc)(\pi)=\sum_{s_i=D}i-\sum_{s_j=U}j=\area(M),
$$
where the last equality is due to the fact that all $U$-steps and $D$-steps are paired up, and the distance from $U$ to $D$ in any given pair is exactly the amount they contributes to the value of $\area(M)$. The proof of the lemma is complete.
%induction on $n$. We distinguish three cases according to the usual decomposition of the two-colored Motzkin path $M=\psi_2(\pi)\in\M_{n-1}^{(2)}$ ($n\geq2$):
%\begin{itemize}
%\item[(i)] $M=\a M'$, where $M'\in \M_{n-2}^{(2)}$. If $\psi_2^{-1}(M')=\sigma=\sigma_1\ldots\sigma_{n-1}$, then $\pi=1(\sigma_1+1)\ldots (\sigma_{n-1}+1)$. So the second equality is true in this case.
%\item[(ii)] $M=\b M'$, where $M'\in \M_{n-2}^{(2)}$. If $\psi_2^{-1}(M')=\sigma=\sigma_1\ldots 1\ldots\sigma_{n-1}$, then $\pi=2(\sigma_1+1)\ldots 1\ldots (\sigma_{n-1}+1)$. The second equality is true too.
%\item[(iii)] $M=U M_1DM_2$, where  $M_1\in \M_{k-1}^{(2)},M_2\in \M_{n-k-2}^{(2)}$ (possibly empty) for some $k\in[n-2]$. If $\psi_2^{-1}(UM_1D)=\sigma=\sigma_1\ldots\sigma_{k+2}$ and $\psi_2^{-1}(M_2)=\mu=\mu_1\ldots1\ldots\mu_{n-k-1}$, then we have $\pi=\sigma_1\ldots\sigma_{k+1}(\mu_1+k+1)\ldots\sigma_{k+2}\ldots(\mu_{n-k-1}+k+1)$. Clearly,
%\begin{align*}
%(\inv-\exc)(\pi)&=(\inv-\exc)(\sigma)+(\inv-\exc)(\mu)\\
%&=\area(UM_1D)+\area(M_2)=\area(M),
%\end{align*}
%as desired. 
%\end{itemize}
\end{proof}

Combining Lemma~\ref{bij:psi1} and Lemma~\ref{bij:psi2}, we arrive at  the following result.
\begin{theorem}\label{th:main}
The composition $\psi=\psi_1\circ\psi_2: \S_n(321)\rightarrow R_n(1212)$ is a bijection such that for each $\pi\in\S_n(321)$, we have 
$$
\EXC(\pi)=\SLR(\psi(\pi))\quad\text{and}\quad\inv(\pi)-\exc(\pi)=\rs(\psi(\pi)).
$$
\end{theorem}
 In view of Lemmas~\ref{lem:slr} and~\ref{lem:den}, Theorem~\ref{th:main} implies Theorem~\ref{thm:2}.


\section{Further applications of $\psi$}\label{sec:4}
\subsection{Proof of Theorem~\ref{thm:3}}
 
 
 We will apply a simple group action on two-colored Motzkin paths which results in a proof of Theorem~\ref{thm:3}. Let $x\in[n-1]$ and $M=s_1\ldots s_{n-1}\in\M_{n-1}^{(2)}$. Define the action $\Theta_x$ on $M$ by 
 $$
\Theta_x(M)=
\begin{cases}
\,\,M\quad&\text{if $s_x=U$ or $s_x=D$},\\
\,\,s_1\ldots s_{x-1}\b s_{x+1}\ldots s_{n-1}\quad&\text{if $s_x=\a$},\\
\,\,s_1\ldots s_{x-1}\a s_{x+1}\ldots s_{n-1}\quad&\text{if $s_x=\b$}.
\end{cases}
$$
In other words, $\Theta_x$ changes the color of the $x$-th step of $M$. Note that all actions commute with each other, i.e., $\Theta_y\circ\Theta_x(M)=\Theta_x\circ\Theta_y(M)$ for any $x,y\in[n-1]$. Moreover, each $\Theta_x$ is an involution on $\M_{n-1}^{(2)}$.  For any subset $S\subseteq[n-1]$, we then define the function $\Theta_S: \M_{n-1}^{(2)}\rightarrow\M_{n-1}^{(2)}$ by 
$\Theta_S=\prod_{x\in S}\Theta_x$, the function compositions of all $\Theta_x$ with $x\in S$. Hence, the group $\Z_2^{n-1}$ acts on $M\in\M_{n-1}^{(2)}$ via the function $\Theta_S$  ($S\subseteq[n-1]$). For example, $\Theta_{\{1,2,4,7\}}(U\b U\a UD\b DDU\a D)=U\a U\b UD\a DDU\a D$.

This $\Z_2^{n-1}$-action divides the set $\M_{n-1}^{(2)}$ into disjoint orbits and each orbit has exactly one two-colored Motzkin path whose $H$-steps, if any, all have color $\a$. For example, under the $\Z_2^{2}$-action, the disjoint orbits of $\M_2^{(2)}$ are $\{UD\}$ and $\{\a\a,\a\b,\b\a,\b\b\}$ with the representatives being $UD$ and $\a\a$, respectively. Note that this $\Z_2^{n-1}$-action preserves the area of any two-colored Motzkin path. Therefore, if we choose the set of representatives of all the disjoint orbits under the $\Z_2^{n-1}$-action on $\M_{n-1}^{(2)}$ as
$$
\mathcal{O}_{n-1}:=\{M\in\M_{n-1}^{(2)}: \,\,\text{$M$ has no $\b$-step}\},
$$
then we have
\begin{lemma}
For $n\geq1$, we have
\begin{equation}\label{action}
\sum_{M\in\M_{n-1}^{(2)}}t^{\ub(M)}q^{\area(M)}=\sum_{M\in\mathcal{O}_{n-1}}q^{\area(M)}t^{\ub(M)}(1+t)^{n-1-2\ub(M)}.
\end{equation}
\end{lemma}

Since $M\in\M_{n-1}^{(2)}$ has no $\b$-step if and only if $\psi_2^{-1}(M)=\pi_1\ldots\pi_n$ has no excedance, say at $i$, such that $\pi_{i+1}^{-1}\leq i$, applying $\psi_2^{-1}$ to both sides of~\eqref{action} then gives the $q$-$\gamma$-positivity expansion in Theorem~\ref{thm:3}.

Parallel to Theorem~\ref{thm:3}, there is also a similar expansion regarding $1212$-avoiding RGFs.
Let 
$$
\widetilde{R_{n}}(1212):=\{w\in R_n(1212): \,\,\text{whenever $w_i<w_{i+1}$,  there exists $j>i+1$ s.t. $w_j=w_i$}\}.
$$
Applying $\psi_1$ to both sides of~\eqref{action} we get
\begin{theorem} \label{gam:rgf}Let $\widetilde{R_{n,k}}(1212):=\{w\in\widetilde{R_{n}}(1212): \bk(w)=k-1\}$. Then, 
$$
\sum_{w\in R_n(1212)}t^{\bk(w)}q^{\rs(w)}=t\sum_{k=0}^{\lfloor (n-1)/2\rfloor}\biggl(\sum_{\pi\in\widetilde{R_{n,k}}(1212)}q^{\rs(w)}\biggr)t^k(1+t)^{n-1-2k}.
$$
\end{theorem}

\subsection{A recurrence for $N_n(t,p,q)$}
%Recall the definition of the $(p,q)$-Narayana polynomials  $N_n(t,p,q)$ in~\eqref{nara:def}. 
It is known that the Catalan numbers $C_n$ satisfy the recurrence relation
$$
C_0=1\quad\text{and}\quad C_{n+1}=\sum_{k=0}^nC_kC_{n-k}.
$$
Regarding our $(p,q)$-Narayana polynomials  $N_n(t,p,q)$, we have 
the following {\em Catalan-like recursion},  which can be derived easily from Lemma~\ref{bij:psi2} by using the usual decomposition of two-colored Motzkin paths.

\begin{theorem}\label{thm:recu}
The $(p,q)$-Narayana polynomials satisfy the recurrence formula:
\begin{equation}\label{eq:recu}
N_{n+1}(t,p,q)=(1+tp)N_{n}(tp,p,q)+tp\sum_{k=1}^{n-1}q^{k}N_{k}(tp,p,q)N_{n-k}(tp^{k+1},p,q)
\end{equation}
for $n\geq0$ and $N_0(t,p,q)=1$.
\end{theorem}
\begin{proof}
It follows from Lemma~\ref{bij:psi2} that (for $n\geq0$)
\begin{equation}\label{int:mot}
N_{n+1}(t,p,q)=\sum_{M\in\M_{n}^{(2)}}t^{\ub(M)}p^{\sum_{i\in\Ub(M)}i}q^{\area(M)}.
\end{equation}
Now for each $M\in\M_{n}^{(2)}$, we distinguish three cases according to the first step of $M$: 
\begin{itemize}
\item It is an $U$-step, then $M$ can be decomposed uniquely as $M=UM_1DM_2$ with $M_1\in\M_{k-1}^{(2)}$ and $M_2\in\M_{n-k-1}^{(2)}$ for some $1\leq k\leq n-1$. In this case, we have $\ub(M)=1+\ub(M_1)+\ub(M_2)$, $\sum_{i\in\Ub(M)}i=1+\sum_{i\in\Ub(M_1)}(i+1)+\sum_{i\in\Ub(M_2)}(k+1+i)$ and $\area(M)=k+\area(M_1)+\area(M_2)$.
\item It is a $\b$-step, then $M=\b M'$ with $M'\in\M_{n-1}^{(2)}$. In this case, we have $\ub(M)=1+\ub(M')$, $\sum_{i\in\Ub(M)}i=1+\sum_{i\in\Ub(M')}(i+1)$ and $\area(M)=\area(M')$.
\item It is an $\a$-step, then $M=\a M''$ with $M''\in\M_{n-1}^{(2)}$. In this case, we have $\ub(M)=\ub(M'')$, $\sum_{i\in\Ub(M)}i=\sum_{i\in\Ub(M'')}(i+1)$ and $\area(M)=\area(M'')$.
\end{itemize}

Summarizing all the above three cases then gives~\eqref{eq:recu}.
\end{proof}
  
  This recursion is a new generalization of~\cite[Theorem~1.1]{ceks}. For the reader's convenience, 
we list the first few values of $N_n(t,p,q)$ in the following:
 \begin{align*}
 N_1(t,p,q)&=1; N_2(t,p,q)=1+pt; N_3(t,p,q)=1+(p+p^2+pq)t+p^3t^2;\\
 N_4(t,p,q)&=1+(p+p^2+pq+p^3+p^2q+pq^2)t(1+tp^2)+p^6t^3;\\
 N_5(t,p,q)&=1+(p+p^2+pq+p^3+p^2q+pq^2+p^4+p^3q+p^2q^2+pq^3)t(1+t^2p^5)\\
 &\quad+(p^3+p^4+p^3q+2p^5+2p^4q+2p^3q^2+p^6+2p^5q+p^4q^2+p^3q^3\\
 &\qquad+p^7+p^6q+2p^5q^2+p^4q^3+p^3q^4)t^2+p^{10}t^4.
 \end{align*}
 
 Let $\Gamma^d_+$ be the set of all polynomials in $\N[t,q]$ that have coefficients in $\N[q]$ when expanded in $\{t^k(1+t)^{d-2k}\}_{k=0}^{\lfloor d/2\rfloor}$.  Expansion~\eqref{eq:gamma} shows that $N_n(t,1,q)\in\Gamma^{n-1}_+$, a fact which was already known in ~\cite[Corollary~2.1]{Lin}. We note that this fact also  follows immediately from Theorem~\ref{thm:recu}.  Actually, setting $p=1$ in~\eqref{eq:recu} we get
 $$
 N_{n+1}(t,1,q)=(1+t)N_{n}(t,1,q)+t\sum_{k=1}^{n-1}q^{k}N_{k}(t,1,q)N_{n-k}(t,1,q).
 $$
 Since $\Gamma^{n}_+\cdot\Gamma^{m}_+:=\{fg: f\in\Gamma^{n}_+\text{ and } g\in\Gamma^{m}_+\}\subseteq\Gamma^{n+m}_+$, we see $N_n(t,1,q)\in\Gamma^{n-1}_+$ from the above recursion  by induction on $n$.
 
 \subsection{Continued fraction expression for $N_n(t,1,q)$}
 Let $\M_n$ be the set of all Motzkin paths of length $n$. For a Motzkin path $M=s_1s_2\ldots s_{n}\in\M_n$, we define the height $h(s_i)$ of the step $s_i$ to be the $y$-coordinate of the starting point of $s_i$. According to the combinatorial theory of continued fractions developed by Flajolet~\cite{fla}, if we weight each up (resp.~down, horizontal) step of a Motzkin path $M$ with height $h$  by $u_h$ (resp.~$d_h$ and $l_h$) and define the weight of $M$ as the product of its step weights, denoted by $w(M)$, then 
 \begin{equation}\label{con:frac}
 1+\sum_{n\geq1}\sum_{M\in\M_n}w(M)x^n=\frac{1}{1-l_0x-\displaystyle\frac{u_0d_1x^2}{1-l_1x-\displaystyle\frac{u_1d_2x^2}{\cdots}}}.
 \end{equation}
 The following continued fraction expansion for  $N_n(t,1,q)$ is a direct consequence of Flajolet's  result and our bijection $\psi_2$.
\begin{theorem}
The ordinary generating function $N(t,q;x):=\sum_{n\geq1}N_n(t,1,q)x^{n}$ has the continued fraction expansion
$$
N(t,q;x)=\frac{x}{1-(1+t)x-\displaystyle\frac{tqx^2}{1-(1+t)qx-\displaystyle\frac{tq^3x^2}{1-(1+t)q^2x-\displaystyle\frac{tq^5x^2}{\cdots}}}}.
$$
\end{theorem}
 \begin{proof}
 By setting the weights $l_h=(1+t)q^h$, $u_h=tq^h$ and $d_h=q^h$ in \eqref{con:frac} and using the interpretation of $N_n(t,1,q)$ in~\eqref{int:mot}, we get the desired continued fraction expansion. 
 \end{proof}
 
 
 
 
 \section{Final remarks}
 \label{sec:5}
 

Wachs and White~\cite{WW} proved that ``$\rb$'' and ``$\ls$'' are equidistributed on the whole set $R_n$. In view of Theorem~\ref{thm:1}, one may wonder if the stronger property that the two paris $(\rb,\ls)$ and $(\ls,\rb)$ are equidistributed on $R_n$ would hold. This is not true, the first counterexample occurs when $n=6$.

Let $(q;q)_n:=\prod_{i=1}^n(1-q^i)$ and $[n]_q:=1+q+\cdots+q^{n-1}$. Recall that the {\em$q$-binomial coefficients} ${n\brack k}_q$ are defined by 
${n\brack k}_q:=\frac{(q;q)_n }{(q;q)_{n-k}(q;q)_k}$ for $0\leq k\leq n$.  The {\em F\"urlinger-Hofbauer $q$-Narayana polynomials}~\cite{fh} that we denote as $C_n(t,q)$ are defined by  
$$
C_n(t,q):=\sum_{k=0}^{n-1}q^{k(k+1)}\frac{1}{[n]_q}{n\brack k}_q{n\brack k+1}_qt^k.
$$
 This  $q$-analog of Narayana polynomials is different from $N_n(t,1,q)$ and has already been widely studied in the literature (cf.~\cite{fh,ceks,stump,zhao}). A natural question that one may ask is if there are interpretations of 
$C_n(t,q)$ in terms of pattern avoiding permutations or RGFs that are similar to Theorem~\ref{thm:2}. This question is answered by works of F\"urlinger-Hofbauer~\cite{fh}, Stump~\cite[Section~3]{stump} and Zhao-Zhong~\cite[Theorem~4.2]{zhao} that we organize as a result in the following. 

\begin{theorem}[See~\cite{fh,stump,zhao}]\label{eq:other}The following equidistribution holds:
$$
C_n(t,q)=\sum_{\pi\in\S_n(231)}t^{\des(\pi)}q^{\maj(\pi)+\maj(\pi^{-1})}=\sum_{w\in R_n(1212)}t^{\bk(w)-1}q^{\ls(w)-\rb(w)+n(\bk(w)-1)},
$$
where $\S_n(231)$ is the set of $231$-avoiding permutations in $\S_n$, $\des(\pi):=\sum_{\pi_i>\pi_{i+1}}1$ and $\maj(\pi):=\sum_{\pi_i>\pi_{i+1}}i$ for each permutation $\pi$.

\end{theorem}

Recently, Dilks, Krattenthaler and Wachs~\cite{wa} proved via $q$-hypergeometric techniques the following $q$-$\gamma$-positivity expansion of $C_n(t,q)$: 
 $$
 C_n(t,q)=\sum_{k=0}^{\lfloor (n-1)/2\rfloor}\gamma_{n,k}(q)t^kq^{k(k+1)}\prod_{i=k+1}^{n-k-1}(1+tq^{2i}),
 $$
 where $\gamma_{n,k}(q)=q^k{n-1\brack 2k}_qC_k(q^2)$ with $C_k(q):=\frac{1}{[k+1]_q}{2k\brack k}_q=C_k(1,q)$. In view of Theorems~\ref{gam:rgf} and \ref{eq:other}, we would like to pose the following open problem for further investigation. 
 \begin{?}Is there a combinatorial interpretation for the $\gamma$-coefficients $\gamma_{n,k}(q)$ in terms of $231$-avoiding permutations or $1212$-avoiding RGFs? Or more precisely, can one find certain statistic, say ``$\st$'', on 
 $\widetilde{R_{n}}(1212)$ so that $\gamma_{n,k}(q)=\sum_{w\in\widetilde{R_{n}}(1212)}q^{\st(w)}$?
 \end{?}
 
 


 
 
 
%%%%%%%%%%%%%%%%%%%%%%%%%% 
\section*{Acknowledgement} 
%%%%%%%%%%%%%%%%%%%%%%%%%%
The authors wish to thank the anonymous referee for bringing their attention to the preprint~\cite{es}, which gives birth to Theorem~\ref{thm:mak}.
The first author's research was supported by the National Science Foundation of China grant 11501244. The second author's research was supported by the National Science Foundation of China grant 11501061 and the Fundamental Research Funds for the Central Universities No.~CQDXWL-2014-Z004. 


\begin{thebibliography}{99}

\bibitem{CDD+}L.R.~Campbell, S.~Dahlberg, R.~Dorward, J.~Gerhard, T.~Grubb, C.~Purcell and B.E.~Sagan, Restricted growth function patterns and statistics, \href{https://arxiv.org/abs/1605.04807v2}{arXiv:1605.04807v2}. 

\bibitem{ceks} S.-E. Cheng, S. Elizalde, A. Kasraoui and B.E. Sagan, Inversion polynomials for $321$-avoiding permutations, Discrete Math., {\bf313} (2013), 2552--2565.

\bibitem{fla}P. Flajolet, Combinatorial aspects of continued fractions, Discrete Math., {\bf32} (2) (1980), 125--161.

\bibitem{fz} D. Foata and D. Zeilberger, Denert's permutation statistic is indeed Euler--Mahonian, Stud. Appl. Math., {\bf83} (1990), 31--59.

\bibitem{fh} F. F\"urlinger and J. Hofbauer, $q$-Catalan numbers, J. Combin. Theory Ser. A, {\bf40} (1985), 248--264.

\bibitem{kaz}A. Kasraoui and J. Zeng, 
Euler-Mahonian statistics on ordered set partitions (II), 
J. Combin. Theory Ser. A, {\bf116} (2009),  539--563.

\bibitem{kz} G. Ksavrelof and J. Zeng, Nouvelles statistiques de partitions pour les $q$-nombres de Stirling de seconde esp\`ece (in French), Discrete Math., {\bf256} (2002), 743--758.


%\bibitem{fs} D. Foata and M.-P. Sch\"utzenberger, {\em Th\'eorie g\'eom\'etrique des polyn\^omes eul\'eriens},  Lecture Notes in Mathematics, Vol. 138, Springer-Verlag, Berlin, 1970.

\bibitem{Lin} Z. Lin, On $\gamma$-positive polynomials arising in pattern avoidance,  Adv. in Appl. Math., {\bf82} (2017), 1--22.

\bibitem{SZ} H. Shin and J. Zeng, Symmetric unimodal expansions of excedances in colored permutations, European J. Combin., {\bf 52} (2016), 174--196.

\bibitem{Sim} R. Simion, Combinatorial statistics on noncrossing partitions, J. Combin. Theory Ser. A, {\bf66} (1994), 270--301.

\bibitem{Pet}T.K. Petersen,  {\em Eulerian numbers}. With a foreword by Richard Stanley. Birkh\"auser Advanced Texts: Basler Lehrb\"ucher. Birkh\"auser/Springer, New York, 2015.

\bibitem{prw}A. Postnikov, V. Reiner, and L. Williams, Faces of generalized permutohedra,
Doc. Math., {\bf13} (2008), 207--273.

\bibitem{es} E. Steingr\'imsson, Statistics on ordered partitions of sets, \href{https://arxiv.org/abs/math/0605670v5}{arXiv:0605670v5}.

\bibitem{stump}C. Stump, On bijections between 231-avoiding permutations and Dyck paths, S\'em. Lothar. Combin.,  {\bf60} (2009), Article B60a. 

 \bibitem{wa}  M. Wachs, On $q$-$\gamma$-positivity, \href{https://www.ima.umn.edu/materials/2014-2015/W11.10-14.14/22141/q-gam.pdf}{talk} at IMA Annual Program Year Workshop: Geometric and Enumerative Combinatorics, November 12, 2014. 

\bibitem{WW}M.~ Wachs and D.~White, $p, q$-Stirling numbers and set partition statistics,  J. Combin. Theory Ser. A, {\bf 56} (1991), 27--46.


\bibitem{zhao} H. Zhao and Z. Zhong, Two statistics linking Dyck paths and non-crossing partitons, 
Electron. J. Combin., {\bf18} (2011),  \#P83. 




\end{thebibliography}
\end{document}
