% 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 : jw_i\},\\ &\rs(w):=\sum_{i=1}^n\#\{w_j : j>i, w_ji, 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\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\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 $ii'$, 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 kj$}\}.$$ 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 $01$, 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), m1.$$ 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$, $1i$, 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\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_ii+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}