% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.27}{24(4)}{2017} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb,extarrows,tikz} % we recommend the graphicx package for importing figures \usepackage{graphicx} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins \newcommand*\circled[1]{\tikz[baseline=(char.base)]{ \node[shape=circle,draw,inner sep=0pt] (char) {#1};}} % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{cor}[theorem]{Corollary} \newtheorem{prop}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{ex}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \newcommand{\casc}{{\rm casc\,}} \newcommand{\mcq}{\mathcal{CQ}} \newcommand{\ddq}{{\rm dq\,}} \newcommand{\desi}{{\rm desi\,}} \newcommand{\NBar}{{\rm NBar\,}} \newcommand{\hhat}{{\rm hat\,}} \newcommand{\HHat}{{\rm Hat\,}} \newcommand{\bbar}{{\rm bar\,}} \newcommand{\BBar}{{\rm Bar\,}} \newcommand{\redd}{{\rm red\,}} \newcommand{\caplat}{{\rm cap\,}} \newcommand{\cplat}{{\rm cplat\,}} \newcommand{\plat}{{\rm plat\,}} \newcommand{\ap}{{\rm ap\,}} \newcommand{\asc}{{\rm asc\,}} \newcommand{\fix}{{\rm fix\,}} \newcommand{\cyc}{{\rm cyc\,}} \newcommand{\DI}{{\rm DI\,}} \newcommand{\lrmin}{{\rm lrmin\,}} \newcommand{\rlmin}{{\rm rlmin\,}} \newcommand{\RLMIN}{{\rm RLMIN\,}} \newcommand{\exc}{{\rm exc\,}} \newcommand{\des}{{\rm des\,}} \newcommand{\zero}{{\rm zero\,}} \newcommand{\fn}{\mathcal{F}_{2n}} \newcommand{\nega}{{\rm neg\,}} \newcommand{\POS}{{\rm POS\,}} \newcommand{\NPOS}{{\rm NPOS\,}} \newcommand{\pos}{{\rm pos\,}} \newcommand{\npos}{{\rm npos\,}} \newcommand{\mk}{\rm{mark}} \newcommand{\umk}{\rm{umark}} \newcommand{\st}{{\rm star\,}} \newcommand{\ns}{{\rm ns\,}} \newcommand{\el}{{\rm el\,}} \newcommand{\ol}{{\rm ol\,}} \newcommand{\ec}{{\rm ec\,}} \newcommand{\oee}{{\rm oe\,}} \newcommand{\ee}{{\rm ee\,}} \newcommand{\eo}{{\rm eo\,}} \newcommand{\mdq}{\mathcal{DQ}} \newcommand{\mq}{\mathcal{Q}} \newcommand{\mbn}{{\mathcal B}_n} \newcommand{\mdqn}{\mathcal{DQ}_n} \newcommand{\mqq}{\mathcal{Q}} \newcommand{\mdn}{\mathcal{D}} \newcommand{\mqn}{\mathcal{Q}_n} \newcommand{\mqnn}{\mathcal{Q}_{n+1}} \newcommand{\msk}{\mathfrak{S}_{n-k}} \newcommand{\mcn}{\mathcal{C}_{[n]}} \newcommand{\mcnn}{\mathfrak{C}_{2n+1}} \newcommand{\msn}{\mathfrak{S}_n} \newcommand{\msss}{\mathfrak{S}} \newcommand{\mssecond}{\mathfrak{S}_2} \newcommand{\msthird}{\mathfrak{S}_3} \newcommand{\ms}{\mathfrak{S}} \newcommand{\msb}{\mathfrak{S}_{2n}} \newcommand{\msnn}{\mathfrak{S}_{n+1}} \newcommand{\z}{ \mathbb{Z}} \newcommand{\as}{{\rm as\,}} \newcommand{\mss}{{\mathcal S}} \newcommand{\msp}{{\mathcal P}} \newcommand{\mbp}{{\mathcal B}} \newcommand{\I}{{\rm I}} \newcommand{\spmaa}{{\rm SPM}} \newcommand{\ffour}{\mathcal{F}_{4}} \newcommand{\mfour}{\mathcal{M}_{4}} \newcommand{\mmn}{\mathcal{M}_{2n}} \newcommand{\mmnn}{\mathcal{M}_{2n+2}} \newcommand{\mmfour}{\mathcal{M}_{4}} \newcommand{\mmsix}{\mathcal{M}_{6}} \newcommand{\m}{{\rm M}} \newcommand{\mm}{\mathcal{M}} \newcommand{\mmark}{\mathcal{Mark}} \newcommand{\umark}{\mathcal{UMark}} \newcommand{\mmyn}{\mathcal{MY}_{n}} \newcommand{\PM}{\mathcal{PM}} \newcommand{\BM}{\mathcal{BM}} \newcommand{\spmann}{\mathcal{SPM}_{n-1}} \newcommand{\myn}{\mathcal{Y}_{n}} \newcommand{\mynn}{\mathcal{Y}_{n-1}} \newcommand{\mpn}{\mathcal{P}_{2n}} \newcommand{\OO}{{\rm OO}} \newcommand{\OEE}{{\rm OE}} \newcommand{\EE}{{\rm EE}} \newcommand{\EO}{{\rm EO}} \newcommand{\BBA}{{\rm BB algorithm}} \newcommand{\LSPA}{{\rm LSP algorithm}} \newcommand{\LPA}{{\rm LP algorithm}} \newcommand{\lrf}[1]{\lfloor #1\rfloor} \newcommand{\lrc}[1]{\lceil #1\rceil} \DeclareMathOperator{\N}{\mathbb{N}} \newcommand{\Eulerian}[2]{\genfrac{<}{>}{0pt}{}{#1}{#2}} \newcommand{\Stirling}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf {Eulerian polynomials, Stirling permutations \\of the second kind and perfect matchings}} \author{Shi-Mei Ma\thanks{Supported by NSFC (11401083), Natural Science Foundation of Hebei Province (A2017501007) and the Fundamental Research Funds for the Central Universities (N152304006).}\\ \small School of Mathematics and Statistics\\[-0.8ex] \small Northeastern University at Qinhuangdao\\[-0.8ex] \small Hebei 066004, P.R. China\\ \small\tt shimeimapapers@163.com\\ \and Yeong-Nan Yeh\thanks{Supported by NSC 101-2115-M-001-013-MY3.}\\ \small Institute of Mathematics\\[-0.8ex] \small Academia Sinica\\[-0.8ex] \small Taipei, Taiwan\\ \small\tt mayeh@math.sinica.edu.tw} % \date{\dateline{submission date}{acceptance date}\\ \date{\dateline{Sep 5, 2017}{Oct 9, 2017}{Oct 20, 2017}\\ \small Mathematics Subject Classifications: 05A05, 05A19} \begin{document} \maketitle \begin{abstract} In this paper, we introduce Stirling permutations of the second kind. In particular, we count Stirling permutations of the second kind by their cycle ascent plateaus, fixed points and cycles. Moreover, we get an expansion of the ordinary derangement polynomials in terms of the Stirling derangement polynomials. Finally, we present constructive proofs of a kind of combinatorial expansions of the Eulerian polynomials of types $A$ and $B$. % keywords are optional \bigskip\noindent \textbf{Keywords:} Eulerian polynomials; Stirling permutations of the second kind; Stirling derangements \end{abstract} \section{Introduction} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Let $[n]$ denote the set $\{1,2,\ldots,n\}$. Let $\msn$ be the set of all permutations of $[n]$ and let $\pi=\pi(1)\pi(2)\cdots\pi(n)\in\msn$. Let $\mbn$ be the hyperoctahedral group of rank $n$. Elements $\pi$ of $\mbn$ are signed permutations of the set $\pm[n]$ such that $\pi(-i)=-\pi(i)$ for all $i$, where $\pm[n]=\{\pm1,\pm2,\ldots,\pm n\}$. Let $\#S$ denote the cardinality of a set $S$. We define \begin{equation*} \begin{split} \des_A(\pi)&:=\#\{i\in\{1,2,\ldots,n-1\}|\pi(i)>\pi({i+1})\},\\ \des_B(\pi)&:=\#\{i\in\{0,1,2,\ldots,n-1\}|\pi(i)>\pi({i+1})\}, \end{split} \end{equation*} where $\pi(0)=0$. The Eulerian polynomials of types $A$ and $B$ are respectively defined by $$A_n(x)=\sum_{\pi\in\msn}x^{\des_A(\pi)},~B_n(x)=\sum_{\pi\in\mbn}x^{\des_B(\pi)}.$$ There is a larger literature devoted to $A_n(x)$ and $B_n(x)$ (see, e.g.,~\cite{Bre00,Dilks09,Foata09,Lin15,Savage1201} and references therein). Let $s=(s_1,s_2,\ldots)$ be a sequence of positive integers. Let $$I_n^{(s)}=\left\{ (e_1,e_2,\ldots,e_n)\in \z^n|~0\leq e_i< s_i\right\},$$ which is known as the set of $s$-inversion sequences. The reader is referred to Savage~\cite{Savage16} for recent progress on this subject. The number of {\it ascents} of an $s$-inversion sequence $e=(e_1,e_2,\ldots,e_n)\in I_n^{(s)}$ is defined by $$\asc(e)=\#\left\{i\in [n-1]:\frac{e_i}{s_i}<\frac{e_{i+1}}{s_{i+1}}\right\}\cup\{0: \textrm{if $e_1> 0$}\}.$$ %The $s$-Eulerian polynomial $E_n^{s}(x)$ is defined by Let $E_n^s(x)=\sum_{e\in I_n^{(s)}}x^{\asc(e)}$. Following~\cite{Pensyl13} and~\cite{Savage1201}, we have \begin{align*} A_n(x)&=E_n^{(1,2,\ldots,n)}(x), B_n(x)=E_n^{(2,4,\ldots,2n)}(x). \end{align*} Let $M_n(x)$ be a sequence of polynomials defined by \begin{equation}\label{N2xt02} M(x,z)=\sum_{n\geq 0}M_n(x)\frac{z^n}{n!}=\sqrt{\frac{x-1}{x-e^{2z(x-1)}}}. \end{equation} Combining~\eqref{N2xt02} and an explicit formula of the Ehrhart polynomial of the $s$-lecture hall polytope, Savage and Viswanathan~\cite{Savage1202} proved that $M_n(x)=E_n^{(1,3,\ldots,2n-1)}(x)$. A {\it perfect matching} of $[2n]$ is a partition of $[2n]$ into $n$ blocks of size $2$. Let $\mmn$ be the set of perfect matchings of $[2n]$. Let $\el(\m)$ be the number of blocks of $\m\in\mmn$ with even larger entries. We define $$N({n,k})=\#\{\m\in\mmn: \el(\m)=k\}.$$ The numbers $N(n,k)$ satisfy the recurrence relation \begin{equation*} N(n+1,k)=2kN(n,k)+(2n-2k+3)N(n,k-1) \end{equation*} for $n,k\geq 1$, where $N(1,1)=1$ and $N(1,k)=0$ for $k\geq 2$ or $k\leq 0$ (see~\cite[Proposition~1]{MaYeh}). Let $N_n(x)=\sum_{k=1}^nN({n,k})x^k$. The first few of the polynomials $N_n(x)$ are $$N_0(x)=1,N_1(x)=x, N_2(x)=2x+x^2, N_3(x)=4x+10x^2+x^3.$$ The exponential generating function for $N_n(x)$ is given as follows (see~\cite[Eq.~(25)]{Ma13}): \begin{equation}\label{N2xt} N(x,z)=\sum_{n\geq 0}N_n(x)\frac{z^n}{n!}=\sqrt{\frac{1-x}{1-xe^{2z(1-x)}}}. \end{equation} Combining~\eqref{N2xt02} and~\eqref{N2xt}, we get $M_n(x)=x^{n}N_n(\frac{1}{x})$ for $n\geq 0$. Let $\ol(\m)$ be the number of blocks of $\m\in\mmn$ with odd larger entries. Then $$M_n(x)=\sum_{\m\in\mmn}x^{\ol(\m)}.$$ Context-free grammar was introduced by Chen~\cite{Chen93} and it is a powerful tool for studying exponential structures in combinatorics. We refer the reader to~\cite{Chen14,Dumont96,Ma-EuJC} for further information. Using~\cite[Theorem~10]{Ma-EuJC}, one can present a grammatical proof of the following result. \begin{prop}\label{prop01} For $n\geq 0$, we have \begin{equation}\label{NnxAnx} 2^nxA_n(x)=\sum_{k=0}^n\binom{n}{k}N_k(x)N_{n-k}(x), \end{equation} \begin{equation}\label{NnxBnx} B_n(x)=\sum_{k=0}^n\binom{n}{k}N_k(x)M_{n-k}(x). \end{equation} \end{prop} Recall that the exponential generating function for $xA_n(x)$ is \begin{equation*}\label{Axz} A(x,z)=1+\sum_{n\geq 1}xA_n(x)\frac{t^n}{n!}=\frac{1-x}{1-xe^{z(1-x)}}. \end{equation*} An equivalent formula of~\eqref{NnxAnx} is given as follows: \begin{equation*}\label{N2xzAx2z} N^2(x,z)=A(x,2z). \end{equation*} Motivated by Proposition~\ref{prop01}, the main purpose of this paper is to introduce some cycle structure related to $N(x,z)$ or $M(x,z)$. This paper is organized as follows. In Section~\ref{Section02}, we introduce the Stirling permutations of the second kind, which is a disjoint union of Stirling permutations. In Section~\ref{Section03}, we count Stirling permutations of the second kind by their cycle ascent plateaus, fixed points and cycles. In Section~\ref{Section04}, we present a constructive proof of Proposition~\ref{prop01}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Stirling permutations of the second kind}\label{Section02} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Stirling permutations were introduced by Gessel and Stanley~\cite{Gessel78}. A \emph{Stirling permutation} of order $n$ is a permutation of the multiset $[n]_2$ such that every element between the two occurrences of $i$ is greater than $i$ for each $i\in [n]$, where $[n]_2=\{1,1,2,2\ldots,n,n\}$. Let $\mq_n$ be the set of Stirling permutations of $[n]_2$. For example, $\mq_2=\{1122,1221,2211\}$. Let $\sigma_1\sigma_2\cdots\sigma_{2n}\in\mqn$. An index $i$ is a {\it descent} of $\sigma$ if $\sigma_i>\sigma_{i+1}$ or $i=2n$. Let $C(n,k)$ be the number of Stirling permutations of $[n]_2$ with $k$ descents. Following~\cite[Eq.~(6)]{Gessel78}, the numbers $C(n,k)$ satisfy the recurrence relation \begin{equation}\label{Cnk-recu} C(n,k)=kC(n-1,k)+(2n-k)C(n-1,k-1) \end{equation} for $n\geq2$, with the initial conditions $C(1,1)=1$ and $C(1,0)=0$. The {\it second-order Eulerian polynomial} is defined by $$C_n(x)=\sum_{i=1}^nC(n,k)x^k.$$ In recent years, there has been much work on Stirling permutations (see~\cite{Bona08,Dzhuma14,Haglund12,Janson11,Ma15}). In particular, B\'ona~\cite{Bona08} introduced the plateau statistic on Stirling permutations, and proved that descents and plateaus have the same distribution over $\mqn$. Given $\sigma\in\mqn$, the index $i$ is called a {\it plateau} if $\sigma_i=\sigma_{i+1}$. We say that an index $i\in [2n-1]$ is an \emph{ascent plateau} if $\sigma_{i-1}<\sigma_i=\sigma_{i+1}$, where $\sigma_0=0$. Let $\ap(\sigma)$ be the number of the ascent plateaus of $\sigma$. For example, $\ap(\textbf{2}211\textbf{3}3)=2$. Very recently, we present a combinatorial proof of the following identity (see~\cite[Theorem 3]{MaYeh}): \begin{equation}\label{Nnx-AP} \sum_{\m\in\mmn}x^{\el(\m)}=\sum_{\sigma\in\mqn}x^{\ap(\sigma)}. \end{equation} Motivated by Proposition~\ref{prop01} and~\eqref{Nnx-AP}, we shall introduce Stirling permutations of the second kind. Let $[k]^n$ denote the set of words of length $n$ in the alphabet $[k]$. For $\omega=\omega_1\omega_2\cdots\omega_n\in [k]^n$, the reduction of $\omega$, denoted by $\redd(\omega)$, is the unique word of length $n$ obtained by replacing the $i$th smallest entry by $i$. For example, $\redd(33224547)=22113435$. \begin{definition}\label{def07} A permutation $\sigma$ of the multiset $[n]_2$ is a {\it Stirling permutation of the second kind} of order $n$ whenever $\sigma$ can be written as a nonempty disjoint union of its distinct cycles and $\sigma$ has a standard cycle form satisfying the following conditions: \begin{itemize} \item [\rm ($i$)] For each $i\in [n]$, the two copies of $i$ appear in exactly one cycle; \item [\rm ($ii$)] Each cycle is written with one of its smallest entry first and the cycles are written in increasing order of their smallest entry; \item [\rm ($iii$)] The reduction of the word formed by all entries of each cycle is a Stirling permutation. In other words, if $(c_1,c_2,\ldots,c_{2k})$ is a cycle of $\sigma$, then $\redd(c_1c_2\cdots c_{2k})\in \mq_k$. \end{itemize} \end{definition} Let $\mqn^2$ denote the set of Stirling permutations of the second kind of order $n$. In the following discussion, we always write $\sigma\in\mqn^2$ in standard cycle form. \begin{ex} \begin{align*} \mq_1^2&=\{(11)\}, ~\mq_2^2=\{(11)(22),(1122),(1221)\},\\ \mq_3^2&=\{(11)(22)(33),(11)(2233),(11)(2332),(1133)(22),(1331)(22),(1122)(33),(112233),\\ &(112332),(113322),(133122),(1221)(33),(122133),(122331),(123321),(133221)\}. \end{align*} \end{ex} Let $(c_1,c_2,\ldots,c_{2k})$ be a cycle of $\sigma$. An entry $c_i$ is called a {\it cycle plateau} (resp. {\it cycle ascent}) if $c_i=c_{i+1}$ (resp. $c_ii$ (resp. $\pi(i)\pi(i+1)$ (resp. $\pi(i)<\pi(i+1)$). By using the reverse map, it is evident that ascent and descent are equidistributed. Let $\asc(\pi)$ be the number of ascents of $\pi$. Hence \begin{equation}\label{Anx-asc} A_n(x)=\sum_{\pi\in\msn}x^{\asc(\pi)}. \end{equation} Throughout this subsection, we shall always use~\eqref{Anx-asc} as the definition of the Eulerian polynomial $A_n(x)$. We now constructively define a set of decorated permutations on $[n]$ with some entries of permutations decorated with hats and circles, denoted by $\msp_n$. Let $w=w_1w_2\cdots w_n\in \msp_n$. We say that $w_i$ with a hat (resp. circle) if $w_i=\tiny{\widehat{{k}}}$ or $w_i={\circled{$\widehat{{k}}$}}$ (resp. $w_i={\circled{$k$}}$ or $w_i={\circled{$\widehat{{k}}$}}$) for some $k\in [n]$. Start with $\msp_1=\{1,\widehat{{1}}\}$. Suppose we have get $\msp_{n-1}$, where $n\geq 2$. Given $v=v_1v_2\cdots v_{n-1}\in\msp_{n-1}$. We now construct entries of $\msp_{n}$ by inserting $n,{\circled{n}},\widehat{{n}}$ or $\circled{$\widehat{n}$}$ into $v$ according the following rules: \begin{enumerate} \item [($r_1$)] We can only put $n$ or $\widehat{n}$ at the end of $v$; \item [($r_2$)] For $1\leq i\leq n-1$, if $v_i$ with no hat, then we can only put $n$ or ${\circled{n}}$ immediately before $v_i$; if $v_i$ with a hat, then we can only put $\widehat{n}$ or $\circled{$\widehat{n}$}$ immediately before $v_i$. %In other words, if $v_i$ with a hat (resp. with no hat), then we can only insert $n$ with a hat (resp. with no hat) immediately before $v_i$. \end{enumerate} It is clear that there are $2n$ elements in $\msp_{n}$ that can be generated from any $v\in\msp_{n-1}$. By induction, we obtain $|\msp_n|=2n|\msp_{n-1}|=2^nn!$. %For $\pi\in\msn$, assume that $ab$ is a consecutive subword of $\pi$. Let $\varphi(w)=\varphi(w_1)\varphi(w_2)\cdots\varphi(w_n)$ be a permutation of $\msn$ obtained from $w\in\msp_n$ by deleting the hats and circles of all $w_i$. For example, $\varphi(\widehat{3}~\widehat{1}\circled{4}~2)=3142$. Let $\msp_{n}(\pi)=\{w\in\msp_n: \varphi(w)=\pi\}$. Let $k\ell$ be a consecutive subword of $\pi\in\msn$. We see that if $k<\ell$, then $k\ell$ can be decorated as $k\ell,k\widehat{\ell},\widehat{k}\ell,\widehat{k}~\widehat{\ell}$. If $k>\ell$, then $k\ell$ can be decorated as $k\ell,\circled{k}\ell,\widehat{k}~\widehat{\ell}$ or $\circled{$\widehat{k}$}\widehat{\ell}$. Therefore, $|\msp_n(\pi)|=2^n$ for any $\pi\in\msn$. It should be noted that $k\widehat{\ell}$ or $\widehat{k}\ell$ is a consecutive subword of $w\in\msp_n$ if and only if $k<\ell$. Let the entry $w_i$ be called an {\it ascent} (resp. a {\it descent}) of $w$ if $\varphi(w_i)<\varphi(w_{i+1})$ ($\varphi(w_i)>\varphi(w_{i+1})$). Also a conventional ascent is counted at the beginning of $w$. That is, we identify a decorated permutation $w=w_1\cdots w_n$ with the word $w_0w_1\cdots w_n$, where $w_0=0$. Let $\asc(w)$ be the number of ascents of $w$. Therefore, we obtain $$2^nxA_n(x)=\sum_{w\in\msp_n}x^{\asc(w)}.$$ \begin{ex} The following decorated permutations are generated from $\widehat{3}~\widehat{1}4~2$: \begin{align*} &\widehat{3}~\widehat{1}425,~\widehat{3}~\widehat{1}4~2~\widehat{5}, ~\widehat{3}~\widehat{1}4~5~2, ~\widehat{3}~\widehat{1}4~\circled{5}~2,\widehat{3}~\widehat{1}542,\\ &~\widehat{3}~\widehat{1}~\circled{5}42,~\widehat{3}~\widehat{5}~\widehat{1}42,~\widehat{3}~\circled{$\widehat{5}$}~\widehat{1}~4~2, \widehat{5}~\widehat{3}~\widehat{1}42,~\circled{$\widehat{5}$}~\widehat{3}~\widehat{1}42. \end{align*} \end{ex} \begin{ex} We have $\msp_2=\{12,1~\widehat{2},\widehat{1}~2,\widehat{1}~\widehat{2},21,\circled{2}~1,\widehat{2}~\widehat{1},\circled{$\widehat{2}$}~\widehat{1}\}$. \end{ex} Let $\emph{\I}_{n,k}$ be a set of subsets of $[n]$ with cardinality $k$. Let $\HHat(w)$ be a set of entries of $w$ with hats and let $\hhat(w)=\#\HHat(w)$. Let $\varphi(\HHat(w))$ be a subset of $[n]$ obtained from $\HHat(w)$ by deleting all hats and circles of all entries of $\HHat(w)$. For example, if $w=\circled{$\widehat{5}$}~\widehat{3}~\widehat{1}42$, then $\HHat(w)=\{\widehat{1},\widehat{3},\circled{$\widehat{5}$}\}$ and $\varphi(\HHat(w))=\{1,3,5\}$. We define \begin{align*} \msp_{n,k}&=\{w\in\msp_n: \hhat(w)=k\},\\ \PM_{n,k}&=\{(S_1,S_2,I_{n,k}): S_1\in \mm_{2k},~S_2\in\mm_{2n-2k},~I_{n,k}\in \emph{\I}_{n,k}\}. \end{align*} In this subsection, we always assume that the weight of $w\in\msp_{n,k}$ is $x^{\asc(w)}$ and that of the pair of matchings $(S_1,S_2)$ is $x^{\el(S_1)+\el(S_2)}$. Now we start to construct a bijection, denoted by $\Phi$, between $\msp_{n,k}$ and $\PM_{n,k}$. When $n=1$, set $\Phi(1)=(\varnothing,(1,2),\varnothing)$ and $\Phi(\widehat{1})=((1,2),\varnothing,\{1\})$. This gives a bijection between $\msp_{1,k}$ and $\PM_{1,k}$. When $n=2$, the bijection $\Phi$ between $\msp_{2,k}$ and $\PM_{2,k}$ is given as follows: \begin{align*} \Phi(12)&=(\varnothing,(1,2)(3,4),\varnothing), ~\Phi(21)=(\varnothing,(1,3)(2,4),\varnothing)\\ \Phi(\circled{2}1)&=(\varnothing,(1,4)(2,3),\varnothing),~\Phi(\widehat{1}{2})=((1,2),(1,2),\{1\}),\\ \Phi(1\widehat{2})&=((1,2),(1,2),\{2\}),~\Phi(\widehat{1}~\widehat{2})=((1,2)(3,4),\varnothing,\{1,2\}),\\ \Phi(\widehat{2}~\widehat{1})&=((1,3)(2,4),\varnothing,\{1,2\}),~\Phi(\circled{$\widehat{2}$}~\widehat{1})=((1,4)(2,3),\varnothing,\{1,2\}). \end{align*} Suppose $\Phi$ is a bijection between $\msp_{m-1,k}$ and $\PM_{m-1,k}$ for all $k$, where $m\geq 3$. Assume that $w=w_1w_2\cdots w_{m-1}\in\msp_{m-1,k}$, $\asc(w)=i+j$ and $\HHat(w)=\{w_{i_1},w_{i_2},\ldots,w_{i_k}\}$. Let $\Phi(w)=(S_1,S_2,I_{m-1,k})$, where $S_1\in\mm_{2k},~S_2\in\mm_{2m-2k-2},~I_{m-1,k}=\varphi(\HHat(w)),~\el(S_1)=i$ and $\el(S_2)=j$. Consider the case $n=m$. Let $w'$ be a decorated permutation generated from $w$. We first distinguish two cases: If $w'=wm$, then let $\Phi(w')=(S_1,S_2(2m-2k-1,2m-2k),I_{m,k})$, where $I_{m,k}=\varphi(\HHat(w))$; If $w'=w\widehat{m}$, then let $\Phi(w')=(S_1(2k+1,2k+2),S_2,I_{m,k+1})$, where $I_{m,k+1}=\varphi(\HHat(w))\cup\{m\}$. Now let $\ell_1\ell_2$ be a consecutive subword of $w$. Firstly, suppose that $\ell_2$ with no hat. We say that $\ell_2$ is a {\it unhat-ascent-top} (resp. {\it unhat-descent-bottom}) if $\varphi(\ell_1)<\varphi(\ell_2)$ (resp. $\varphi(\ell_1)>\varphi(\ell_2)$). Consider the following two cases: \begin{enumerate} \item [\rm ($c_1$)] If $w'=\cdots\ell_1 m\ell_2$ (resp. $w'=\cdots\ell_1\circled{m} \ell_2\cdots$) and $\ell_2$ is the $p$th unhat-ascent-top of $w$, then let $\Phi(w')=(S_1,S'_2,I_{m,k})$, where $I_{m,k}=\varphi(\HHat(w))$ and $S'_2$ is obtained from $S_2$ by replacing $p$th marked block $(a,b)$ by two blocks $(a,2m-2k-1),(b,2m-2k)$ (resp. $(a,2m-2k),(b,2m-2k-1)$). \item [\rm ($c_2$)] If $w'=\cdots\ell_1m \ell_2\cdots$ (resp. $w'=\cdots\ell_1\circled{m} \ell_2\cdots$) and $\ell_2$ is the $p$th unhat-descent-bottom of $w$, then let $\Phi(w')=(S_1,S'_2,I_{m,k})$, where $I_{m,k}=\varphi(\HHat(w))$ and $S'_2$ is obtained from $S_2$ by replacing $p$th unmarked block $(a,b)$ by two blocks $(a,2m-2k-1),(b,2m-2k)$ (resp. $(a,2m-2k),(b,2m-2k-1)$). \end{enumerate} Secondly, suppose that $\ell_2$ with a hat. We say that $\ell_2$ is a {\it hat-ascent-top} (resp. {\it hat-descent-bottom}) if $\varphi(\ell_1)<\varphi(\ell_2)$ (resp. $\varphi(\ell_1)>\varphi(\ell_2)$). Consider the following two cases: \begin{enumerate} \item [\rm ($c_1$)] If $w'=\cdots\ell_1\widehat{m}~{\ell_2}\cdots$ (resp. $w'=\cdots\ell_1\circled{$\widehat{m}$}~{\ell_2}\cdots$) and $\ell_2$ is the $p$th hat-ascent-top of $w$, then let $\Phi_1(w')=(S'_1,S_2,I_{m,{k+1}})$, where $I_{m,{k+1}}=\varphi(\HHat(w))\cup\{m\}$ and $S'_1$ is obtained from $S_1$ by replacing the $p$th marked block $(a,b)$ by two blocks $(a,2k+1),(b,2k+2)$ (resp. $(a,2k+2),(b,2k+1)$). \item [\rm ($c_2$)] If $w'=\cdots\ell_1\widehat{m}~{\ell_2}\cdots$ (resp. $w'=\cdots\ell_1\circled{$\widehat{m}$}~{\ell_2}\cdots$) and $\ell_2$ is the $p$th hat-descent-bottom of $w$, then let $\Phi(w')=(S'_1,S_2,I_{m,{k+1}})$, where $I_{m,{k+1}}=\varphi(\HHat(w))\cup\{m\}$ and $S_1'$ is obtained from $S_1$ by replacing the $p$th unmarked block $(a,b)$ by two blocks $(a,2k+1),(b,2k+2)$ (resp. $(a,2k+2),(b,2k+1)$). \end{enumerate} After the above step, we write the obtained perfect matchings in standard form. Suppose that $w\in\msp_{n,k}$ and $\Phi(w)=(S_1,S_2,I_{n,k})$. Then $\asc(w)=i+j$ if and only if $\el(S_1)+\el(S_2)=i+j$. By induction, we see that $\Phi$ is the desired bijection between $\msp_{n,k}$ and $\PM_{n,k}$ for all $k$, which also gives a constructive proof of~\eqref{NnxAnx}. %We now present an example to illustrate the bijection between $\myn$ and $\mqnn$. \begin{ex} Let $w=\widehat{3}~\widehat{1}42\circled{$\widehat{6}$}\widehat{5}\in \msp_{6,4}$. The correspondence between $w$ and $\Phi(w)$ is built up as follows: \begin{align*} \widehat{1}&\Leftrightarrow ((1,2),\varnothing,\{1\});\\ \widehat{1}2&\Leftrightarrow ((1,2),(1,2),\{1\});\\ \widehat{3}~\widehat{1}2&\Leftrightarrow ((1,3)(2,4),(1,2),\{1,3\});\\ \widehat{3}~\widehat{1}42&\Leftrightarrow ((1,3)(2,4),(1,3)(2,4),\{1,3\});\\ \widehat{3}~\widehat{1}42\widehat{5}&\Leftrightarrow ((1,3)(2,4)(5,6),(1,3)(2,4),\{1,3,5\});\\ \widehat{3}~\widehat{1}42\circled{$\widehat{6}$}\widehat{5}&\Leftrightarrow ((1,3)(2,4)(5,8)(6,7),(1,3)(2,4),\{1,3,5,6\}). \end{align*} \end{ex} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \subsection{Signed permutations and pairs of perfect matchings} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \hspace*{\parindent} In this subsection, we write signed permutations of $\mbn$ as $\pi=\pi(0)\pi(1)\pi(2)\cdots\pi(n)$, where some elements are associated with the minus sign and $\pi(0)=0$. As usual, we denote by $\overline{i}$ the negative element $-i$. For $\pi\in\mbn$, let $$\RLMIN(\pi)=\{\pi(i): |\pi(i)|<|\pi(j)| ~\textrm{for all $j>i$}\}.$$ For example, $\RLMIN(\overline{3}~\overline{1}42\overline{6}7\overline{5})=\{\overline{1},2,\overline{5}\}$. For $\pi\in\mbn$, we let $\rlmin(\pi)=\#\RLMIN(\pi)$. For $\pi\in\msn$, we let $\rlmin(\pi)=\#\{\pi(i):\pi(i)<\pi(j)~\textrm{for all $j>i$}\}$. For $n\geq 1$, we have $$\sum_{\pi\in\mbn}x^{\rlmin(\pi)}=2^n\sum_{\pi\in\msn}x^{\rlmin(\pi)} =2^nx(x+1)(x+2)\cdots(x+n-1).$$ \begin{definition} A block of $\pi$ is a maximal subsequence of consecutive elements of $\pi$ ending with $\pi(i)\in\RLMIN(\pi)$ and not contain any other element of $\RLMIN(\pi)$. \end{definition} It is clear that any $\pi$ has a unique decomposition as a sequence of its blocks. If $\rlmin(\pi)=k$, then we write $\pi\mapsto B_1B_2\cdots B_k$, where $B_i$ is $i$th block of $\pi$. A {\it bar-block} (resp.~{\it unbar-block}) is a block ending with a negative (resp. positive) element. Let $\BBar(\pi)$ be the union of elements of bar-blocks of $\pi$ and let $\bbar(\pi)=\#\BBar(\pi)$. We define a map $\theta$ by $$\theta(\BBar(\pi))=\{|\pi(i)|: \pi(i)\in \BBar(\pi)\}.$$ Set $\NBar(\pi)=[n]/\BBar(\pi)$. For example, if $\pi=\overline{3}~\overline{1}42\overline{6}7\overline{5}$, then $\pi\mapsto[\overline{3}~\overline{1}][42][\overline{6}7\overline{5}]$, $[\overline{3}~\overline{1}]$ and $[\overline{6}7\overline{5}]$ are bar-blocks of $\pi$, $\BBar(\pi)=\{\overline{6},\overline{5},\overline{3},\overline{1},7\},\bbar(\pi)=5$, $\theta(\BBar(\pi))=\{1,3,5,6,7\}$. and $\NBar(\pi)=\{2,4\}$. We define ${\mbp}_{n,k}=\{\pi\in\mbn: \bbar(\pi)=k\}$ and $${\BM}_{n,k}=\{(T_1,T_2,I_{n,k}): T_1\in \mm_{2k},~T_2\in\mm_{2n-2k},~I_{n,k}\in \emph{\I}_{n,k}\},$$ where $\emph{\I}_{n,k}$ is the set of subsets of $[n]$ with the cardinality $k$. In this subsection, we always assume that the weight of $\pi\in\mbp_{n,k}$ is $x^{\des_B(\pi)}$ and that of the pair of matchings $(T_1,T_2)$ is $x^{\el(T_1)+\ol(T_2)}$. Along the same lines as the proof of~\eqref{NnxAnx}, we start to construct a bijection, denoted by $\Psi$, between ${\mbp}_{n,k}$ and ${\BM}_{n,k}$. When $n=1$, set $\Psi(1)=(\varnothing,(1,2),\varnothing)$ and $\Psi(\overline{1})=((1,2),\varnothing,\{1\})$. This gives a bijection between $\mbp_{1,k}$ and $\BM_{1,k}$. When $n=2$, the bijection $\Psi$ between ${\mbp}_{2,k}$ and ${\BM}_{2,k}$ is given as follows: \begin{align*} \Psi(12)&=(\varnothing,(1,2)(3,4),\varnothing),~\Psi(21)=(\varnothing,(1,3)(2,4),\varnothing)\\ \Psi(\overline{2}1)&=(\varnothing,(1,4)(2,3),\varnothing),~\Psi(\overline{1}{2})=((1,2),(1,2),\{1\}),\\ \Psi(1\overline{2})&=((1,2),(1,2),\{2\}),~\Psi(\overline{1}~\overline{2})=((1,2)(3,4),\varnothing,\{1,2\}),\\ \Psi(2\overline{1})&=((1,3)(2,4),\varnothing,\{1,2\}),~\Psi(\overline{2}~\overline{1})=((1,4)(2,3),\varnothing,\{1,2\}). \end{align*} Suppose $\Psi$ is a bijection between $\mbp_{m-1,k}$ and $\BM_{m-1,k}$ for all $k$, where $m\geq 3$. Assume that $\pi=\pi(1)\pi(2)\cdots \pi(m-1)\in{\mbp}_{m-1,k}$, $\des_B(\pi)=i+j$ and $\BBar(\pi)=\{\pi(i_1),\pi(i_2)\ldots,\pi(i_k)\}$. Let $\Psi(\pi)=(T_1,T_2,I_{m-1,k})$, where $$T_1\in\mm_{2k},~T_2\in\mm_{2m-2k-2},~I_{m-1,k}=\theta(\BBar(\pi)),~\el(T_1)=i,\ol(T_2)=j.$$ Consider the case $n=m$. Let $\pi'$ be obtained from $\pi$ by inserting the entry $m$ (resp. $\overline{m}$) into $\pi$. We first distinguish two cases: If $\pi'=\pi m$, then let $$\Psi(\pi')=(T_1,T_2(2m-2k-1,2m-2k),I_{m,k}),$$ where $I_{m,k}=\theta(\BBar(\pi))$; If ${\pi}'=\pi \overline{m}$, then let $\Psi({\pi}')=(T_1(2k+1,2k+2),T_2,I_{m,k+1})$, where $I_{m,k+1}=\theta(\BBar(\pi))\cup\{m\}$. For $0\leq i\leq m-2$, consider the consecutive subword $\pi(i)\pi(i+1)$ of $\pi$. Firstly, suppose that $\pi(i+1)\in \NBar(\pi)$. We say $\pi(i+1)$ is a {\it unbar-ascent-top} (resp. {\it unbar-descent-bottom}) if $\pi(i)<\pi(i+1)$ (resp. $\pi(i)>\pi(i+1)$). Consider the following two cases: \begin{enumerate} \item [\rm ($c_1$)] If $\pi'=\cdots\pi(i)m\pi(i+1)\cdots$ (resp. $\pi'=\cdots\pi(i)\overline{m}\pi(i+1)\cdots$) and $\pi(i+1)$ is the $p$th unbar-ascent-top of $\pi$, then let $\Psi(\pi')=(T_1,T_2',I_{m,k})$, where $T_2'$ is obtained from $T_2$ by replacing the $p$th marked block $(a,b)$ by two blocks $(a,2m-2k-1),(b,2m-2k)$ (resp. $(a,2m-2k),(b,2m-2k-1)$) and $I_{m,k}=\theta(\BBar(\pi))$. \item [\rm ($c_2$)] If $\pi'=\cdots\pi(i)m\pi(i+1)\cdots$ (resp. $\pi'=\cdots\pi(i)\overline{m}\pi(i+1)\cdots$) and $\pi(i+1)$ is the $p$th unbar-descent-bottom of $\pi$, then let $\Psi(\pi')=(T_1,T_2',I_{m,k})$, where $T_2'$ is obtained from $T_2$ by replacing the $p$th unmarked block $(a,b)$ by two blocks $(a,2m-2k-1),(b,2m-2k)$ (resp. $(a,2m-2k),(b,2m-2k-1)$) and $I_{m,k}=\theta(\BBar(\pi))$. \end{enumerate} Secondly, suppose that $\pi(i+1)\in \BBar(\pi)$. We say $\pi(i+1)$ is a {\it bar-ascent-top} (resp. {\it bar-descent-bottom}) if $\pi(i)<\pi(i+1)$ (resp. $\pi(i)>\pi(i+1)$). Consider the following two cases: \begin{enumerate} \item [\rm ($c_1$)] If $\pi'=\cdots\pi(i)m\pi(i+1)\cdots$ (resp. $\pi'=\cdots\pi(i)\overline{m}\pi(i+1)\cdots$) and $\pi(i+1)$ is the $p$th bar-ascent-top of $\pi$, then let $\Psi(\pi')=(T_1',T_2,I_{m,{k+1}})$, where $T_1'$ is obtained from $T_1$ by replacing the $p$th unmarked block $(a,b)$ by two blocks $(a,2k+1),(b,2k+2)$ (resp. $(a,2k+2),(b,2k+1)$) and $I_{m,{k+1}}=\theta(\BBar(\pi))\cup\{m\}$. \item [\rm ($c_2$)] If $\pi'=\cdots\pi(i)m\pi(i+1)\cdots$ (resp. $\pi'=\cdots\pi(i)\overline{m}\pi(i+1)\cdots$) and $\pi(i+1)$ is the $p$th bar-descent-bottom of $\pi$, then let $\Psi(\pi')=(T_1',T_2,I_{m,{k+1}})$, where $T_1'$ is obtained from $T_1$ by replacing the $p$th marked block $(a,b)$ by two blocks $(a,2k+1),(b,2k+2)$ (resp. $(a,2k+2),(b,2k+1)$) and $I_{m,{k+1}}=\theta(\BBar(\pi))\cup\{m\}$. \end{enumerate} After the above step, we write the obtained perfect matching in standard form. Suppose that $\pi\in\mbp_{n,k}$ and $\Psi(\pi)=(T_1,T_2,I_{n,k})$. Then $\des_B(\pi)=i+j$ if and only if $\el(T_1)+\ol(T_2)=i+j$. By induction, we see that $\Psi$ is the desired bijection between $\mbp_{n,k}$ and $\BM_{n,k}$ for all $k$, which also gives a constructive proof of~\eqref{NnxBnx}. \begin{ex} The correspondence between $\pi=\overline{3}~\overline{1}42\overline{6}7\overline{5}$ and $\Psi(\pi)$ is built up as follows: \begin{align*} \overline{1}&\Leftrightarrow ((1,2),\varnothing,\{1\});\\ \overline{1}2&\Leftrightarrow ((1,2),(1,2),\{1\});\\ \overline{3}~\overline{1}2&\Leftrightarrow ((1,4)(2,3),(1,2),\{1,3\});\\ \overline{3}~\overline{1}42&\Leftrightarrow ((1,4)(2,3),(1,3)(2,4),\{1,3\});\\ \overline{3}~\overline{1}42\overline{5}&\Leftrightarrow ((1,4)(2,3)(5,6),(1,3)(2,4),\{1,3,5\});\\ \overline{3}~\overline{1}42\overline{6}~\overline{5}&\Leftrightarrow ((1,3)(2,4)(5,8)(6,7),(1,3)(2,4),\{1,3,5,6\});\\ \overline{3}~\overline{1}42\overline{6}7\overline{5}&\Leftrightarrow ((1,3)(2,4)(5,8)(6,9)(7,10),(1,3)(2,4),\{1,3,5,6,7\}). \end{align*} \end{ex} \section{Concluding remarks}\label{Section-5} %\hspace*{\parindent} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Given $\sigma=\sigma_1\sigma_2\cdots\sigma_{2n}\in\mqn$. We say that $\sigma_i$ is a {\it left-to-right minimum} of $\sigma$ if $\sigma_i<\sigma_j$ for all $1\leq j