% EJC papers *must* begin with the following two lines.
\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P4.42}{22(4)}{2015}

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

% 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{\ap}{{\rm ap\,}}
\newcommand{\asc}{{\rm asc\,}}
\newcommand{\fix}{{\rm fix\,}}
\newcommand{\cyc}{{\rm cyc\,}}
\newcommand{\open}{{\rm open\,}}
\newcommand{\aexc}{{\rm aexc\,}}
\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{\oo}{{\rm oo\,}}
\newcommand{\so}{{\rm so\,}}
\newcommand{\ec}{{\rm ec\,}}
\newcommand{\oee}{{\rm oe\,}}
\newcommand{\ee}{{\rm ee\,}}
\newcommand{\eo}{{\rm eo\,}}
\newcommand{\mq}{\mathcal{Q}}
\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{\my}{{\rm MY}}
\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{\spma}{\mathcal{SPM}}
\newcommand{\spman}{\mathcal{SPM}_{n}}
\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}}
\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
\newtheorem{theorem}{Theorem}%[section]
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{ex}[theorem]{Example}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}

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

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

\title{\bf Stirling permutations, cycle structure of permutations and perfect matchings}

% 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{Shi-Mei Ma\thanks{Supported by NSFC (11401083), the NSF of Hebei Province (A2013501070) and
the Fundamental Research Funds for the Central Universities (N130423010).}\\
\small School of Mathematics and Statistics\\[-0.8ex]
\small Northeastern University at Qinhuangdao\\[-0.8ex]
\small Hebei 066000, 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}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Jun 9, 2015}{Dec 10, 2015}{Dec 23, 2015}\\
\small Mathematics Subject Classifications: 05A15, 05A19}

\begin{document}

\maketitle



\begin{abstract}
  In this paper we provide constructive proofs that
the following three statistics are equidistributed: the number of ascent plateaus
of Stirling permutations of order $n$, a weighted variant of the number of excedances
in permutations of length $n$ and the number of blocks with even maximal elements in
perfect matchings of the set $\{1,2,3,\ldots,2n\}$.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Stirling permutations; Excedances; Perfect matchings; Eulerian polynomials
\end{abstract}

\section{Introduction}
In this paper we will study the relationship between Stirling permutations, the cycle structure of permutations and
perfect matchings, and will give constructive proofs
for the equidistribution of some combinatorial statistics on these combinatorial structures.

Stirling permutations were introduced by Gessel and Stanley~\cite{Gessel78}.
A \emph{Stirling permutation} of order $n$ is a permutation of the multiset $\{1,1,2,2,\ldots,n,n\}$ such that
every element between the two occurrences of $i$ is greater than $i$ for each $i\in [n]$,
where $[n]=\{1,2,\ldots,n\}$.
%Recently, there are a lot of results on Stirling permutations.
We refer the reader to
~\cite{Bona08,Haglund12,Janson11,Ma14} for some recent results on Stirling permutations.

%Recall that an occurrence of a {\it pattern} $\tau$ in a permutation $\pi$ is defined as a subsequence
%in $\pi$ whose letters are in the same relative order as those in $\tau$.
Let $\mqn$ be the set of Stirling permutations of order $n$.
For any $\sigma=\sigma_1\sigma_2\cdots\sigma_{2n}\in\mqn$, an occurrence of
an \emph{ascent} (resp.~\emph{a plateau}) is an index $i$
such that $\sigma_i<\sigma_{i+1}$ (resp. $\sigma_i=\sigma_{i+1}$).
%is an occurrence of the pattern $12$ (resp. 11).
%In this paper, we always assume that Stirling permutations are prepended by 0.
%That is, we identify an $n$-Striling permutation
%$\sigma_1\sigma_2\cdots\sigma_{2n}$ with the word $\sigma_0\sigma_1\sigma_2\cdots\sigma_{2n}$,
%Let $\sigma=\sigma_1\sigma_2\cdots\sigma_{2n}\in \mqn $.
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$ (see~\cite{Ma14}).
Let $\ap(\sigma)$ be the number of the ascent plateaus of $\sigma$. Then as an example, $\ap(\textbf{2}211\textbf{3}3)=2$.
Let
\begin{equation*}\label{Nnx-Stirling}
P_n(x)=\sum_{\sigma \in \mqn}x^{\ap(\sigma)}=\sum_{k=1}^nP(n,k)x^k.
\end{equation*}
Then $P_n(1)=\#\mqn=(2n-1)!!$, where $(2n-1)!!$ is the double factorial of $2n-1$.
By~\cite[Theorem~3]{Ma14}, the numbers $P(n,k)$ satisfy the recurrence relation
\begin{equation}\label{recurrence-Pnk}
P({n+1,k})=2kP({n,k})+(2n-2k+3)P(n,k-1),
\end{equation}
with the initial values $P(1,1)=1$ and $P(1,k)=0$ for $k\leq 0$ or $k\geq 2$.

%As usual, we say that $i_1,i_2,\ldots,i_n$ are the {\it openers} of $\m$ and
%$j_1,j_2,\ldots,j_n$ are the {\it closers}.
Let $\msn$ denote the symmetric group of all permutations of $[n]$
and $\pi=\pi_1\pi_2\cdots \pi_n\in\msn$. An \emph{excedance} in $\pi$ is an
index $i$ such that $\pi_i>i$. Let $\exc(\pi)$ denote the number of
excedances in $\pi$. The classical
\emph{Eulerian polynomials} $A_n(x)$ are defined by
$$A_0(x)=1,~A_n(x)=\sum_{\pi\in\msn}x^{\exc(\pi)}~\textrm{for $n\ge 1$},$$
and have been extensively investigated (see~\cite{Dilks09,FS70} for instance).
In~\cite{FS70},
Foata and Sch\"utzenberger introduced a $q$-analog of the
Eulerian polynomials defined by
\begin{equation*}\label{anxq-def}
A_n(x;q)=\sum_{\pi\in\msn}x^{\exc(\pi)}q^{\cyc(\pi)},
\end{equation*}
where $\cyc(\pi)$ is the number of cycles in $\pi$.
Brenti~\cite{Bre94,Bre00} further studied $q$-Eulerian polynomials
and established the link with $q$-symmetric functions arising from
plethysm. In particular, Brenti~\cite[Proposition~7.3]{Bre00} obtained the exponential generating function for $A_n(x;q)$:
\begin{equation*}\label{anxq-rr}
1+\sum_{n\geq 1}A_n(x;q)\frac{z^n}{n!}=\left(\frac{1-x}{e^{z(x-1)}-x}\right)^q.
\end{equation*}

For any $k\geq 1$, the \emph{$1/k$-Eulerian polynomials} $A_n^{(k)}(x)$ are defined by
\begin{equation}\label{Ankx-def01}
\sum_{n\geq 0}A_n^{(k)}(x)\frac{z^n}{n!}=\left(\frac{1-x}{e^{kz(x-1)}-x} \right)^{\frac{1}{k}}.
\end{equation}
Let $\textbf{e}=(e_1,e_2,\ldots,e_n)\in\z^n$. Let
$I_{n,k}=\left\{ \textbf{e}~|~0\leq e_i\leq (i-1)k\right\}$, which is known as the set of $n$-dimensional \emph{$k$-inversion sequences}.
The number of \emph{ascents} of $\textbf{e}$ is defined by
$$\asc(\textbf{e})=\#\left\{i:1\leq i\leq n-1~\big{|}~\frac{e_i}{(i-1)k+1}<\frac{e_{i+1}}{ik+1}\right\}.$$
Recently, Savage and Viswanathan~\cite{Savage1202} discovered that
\begin{equation}\label{Ankx-Savage}
A_n^{(k)}(x)=\sum_{\textbf{e}\in I_{n,k}}x^{\asc(\textbf{e})}=k^nA_n(x;1/k).
\end{equation}

A \emph{perfect matching} of $[2n]$ is a set partition of $[2n]$ with blocks (disjoint nonempty subsets) of size exactly 2.
Let $\mmn$ be the set of matchings of $[2n]$, and let $\m\in\mmn$.
The \emph{standard form} of $\m$ is a list of blocks $\{(i_1,j_1),(i_2,j_2),\ldots,(i_n,j_n)\}$ such that
$i_r<j_r$ for all $1\leq r\leq n$ and $1=i_1<i_2<\cdots <i_n$.
Throughout this paper we always write $\m$ in standard form.
It is well known that $\m$ can
be regarded as a fixed-point-free involution on $[2n]$.
We call $(a,b)$ a \emph{marked block} (resp.~an \emph{unmarked block}) if $b$ is even (resp. odd) and
large than $a$.
Let $\mk(\m)$ be the number of marked blocks of $\m$.
%(see~\cite{Ma13,Ma1302})

Let
\begin{equation*}\label{Nnx-Matching}
N_n(x)=\sum_{\m\in\mmn}x^{\mk(\m)}=\sum_{k=1}^nN(n,k)x^k.
\end{equation*}
Then $N_n(1)=\#\mmn=(2n-1)!!$. The first few terms of $N_n(x)$ are
$$N_1(x)=x,~N_2(x)=2x+x^2,~N_3(x)=4x+10x^2+x^3,~
N_4(x)=8x+60x^2+36x^3+x^4.$$

%Let $\widehat{N}_n(x)=x^{n}N_n\left(\frac{1}{x}\right)$.
%It follows from~\eqref{Ankx-def01} and~\eqref{An2x-Nnx} that
%\begin{equation*}\label{Anx-Nnx01}
%2^nA_n(x)=\sum_{k=0}^n\binom{n}{k}\widehat{N}_k(x)\widehat{N}_{n-k}(x).
%\end{equation*}
% a constructive proof that
%the following three statistics are equidistribute
The main purpose of the paper is to prove constructively that
the following three statistics are equidistributed:
\begin{enumerate}
  \item [\rm ($m_1$)] $\ap(\sigma)$, the number of ascent plateaus of $\sigma\in\mqn$;
  \item [\rm ($m_2$)] a weighted variant of $\exc(\pi)$, where the
variant is $n-\exc(\pi)$ and the weight is $2^{n-\cyc(\pi)}$;
  \item [\rm ($m_3$)] $\mk(\m)$, the number of marked blocks of $\m\in\mmn$.
\end{enumerate}

The paper is organized as follows.
In Section~\ref{Section-02}, we first derive the recurrence relation of the numbers $N(n,k)$ and then we give
the connection between the three combinatorial objects studied in this paper on the
level of generating functions.
In Section~\ref{Section03}, we give constructive proofs of the main results by using the $\spma$-sequences.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Recurrence formula for $N(n,k)$}\label{Section-02}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\section{Main results}\label{Section-2}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%The blocks of $\m\in\mmn$ can be partitioned into
%four subsets:
%\begin{align*}
%  \OO(\m)&=\{(a,b)\in\m\mid \textrm{a and b are both odd}\}, \\
%  \OEE(\m)&=\{(a,b)\in\m\mid \textrm{a is odd and b is even}\}, \\
%  \EO(\m)&=\{(a,b)\in\m\mid \textrm{a is even and b is odd}\}, \\
%  \EE(\m)&=\{(a,b)\in\m\mid \textrm{a and b are both even}\}.
%\end{align*}
%Define $$\oo(\m)=\#\OO(\m),~ \oee(\m)=\#\OEE(\m), ~\eo(\m)=\#\EO(\m),~ \ee(\m)=\#\EE(\m).$$
%By definition, $\so(\m)=\oo(\m)+\oee(\m)$.
%We found that it is difficult to derive the recurrence relation for $N(n,k)$ by using the fact that
%$$N(n,k)=\#\{\m\in\mmn\mid \oo(\m)+\oee(\m)=k\}.$$
%In the following, we give an alternative approach.

%Observe that  $2\oo(\m)+\oee(\m)+\eo(\m)$ and $2\ee(M)+\oee(\m)+\eo(\m)$ are the number of odd elements and the number of even elements in %$\{1,2,\ldots,2n\}$, respectively.
%Therefore,
%$$2\oo(\m)+\oee(\m)+\eo(\m)=n=2\ee(\m)+\oee(\m)+\eo(\m).$$
%This implies that  $\oo(\m)=\ee(\m)$. Therefore,
%the number of blocks of $\m$ with odd minimal elements equals the number of blocks of $\m$ with even maximal elements.
%\begin{equation}\label{Nnk-Mark}
%\sum_{\m\in\mmn}x^{\so(\m)}=\sum_{\m\in\mmn}x^{\mk(\m)}.
%\end{equation}
%Given $\m\in\mmn$, if $(a,b) \in \EE(\m) \cup \OEE(\m)$, then we call $(a,b)$ a \emph{marked block}.
%Otherwise, $(a,b)$ is an \emph{unmarked block}. Denote by $\mk(\m)$ the number of marked blocks in $\m$. Thus we have $\so(\m)=\mk(\m)$.

\begin{prop}\label{prop01}
The numbers $N(n,k)$ satisfy the recurrence relation
\begin{equation}\label{recurrence-01}
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\leq 0$ or $k\geq 2$.
\end{prop}
\begin{proof}
For each $\m\in\mmn$ and for each block $(a,b)$ of $\m$, let
$\varphi_1(\m,(a,b))\in\mmnn$ be obtained from $\m$ by replacing the block $(a,b)$ with two blocks $(a, 2n+1),(b,2n+2)$, and let
$\varphi_2(\m,(a,b)) \in \mmnn$  be obtained from $\m$ by replacing the block $(a,b)$ with two blocks
$(a, 2n+2),(b,2n+1)$. Moreover, let $\varphi(\m) \in \mmnn$  be obtained from $\m$ by adding the block $(2n+1,2n+2)$.
It is obvious that for any $\m' \in \mmnn$, there is an $\m\in\mmn$ such that either $\m'=\varphi(\m)$ or there is a block $(a,b)$ of $\m$
 such that $\m' = \varphi_1(\m,(a,b))$ or $\m' = \varphi_2(\m,(a,b))$.
Moreover, it follows from the definition that $\mk(\varphi(\m))=\mk(\m)+1$ and
\begin{enumerate}
  \item [\rm ($i$)] if $(a,b)$ is a marked block, then $\mk(\varphi_\emph{i}(\m,(a,b)))=\mk(\m)$ for $i \in \{1,2\}$;
  %Combining~\eqref{Nnk-Mnk}, this accounts for $2kN(n,k)$ possibilities.
  \item [\rm ($ii$)] if $(a,b)$ is an unmarked block, then $\mk(\varphi_\emph{i}(\m, (a,b)))=\mk(\m)+1$ for $i\in \{1,2\}$.
  %This gives $(2n-2(k-1)+1)N(n,k-1)=(2n-2k+3)N(n,k-1)$ possibilities.
\end{enumerate}
Assume $\m'=\varphi(\m)$ or $\varphi_i(\m,(a,b))$ ($i=1,2$). If $\mk(\m')=\emph{k}$, then $\mk(\m)=\emph{k}$ or $\mk(\m)=\emph{k}-1$.
Each matching $\m\in\mmn$ with $\mk(\m)=\emph{k}$ corresponds to $2k$ matchings $\m'\in\mmnn$ with $\mk(\m')=\emph{k}$, and each matching
$\m\in\mmn$ with $\mk(\m)=\emph{k}-1$ corresponds to $2(n-(k-1))+1$ matchings $\m'\in\mmnn$ with $\mk(\m')=\emph{k}$.
So
$$N(n+1,k)=2kN(n,k)+(2(n-(k-1))+1)N(n,k-1).$$
This completes the proof of~\eqref{recurrence-01}.
\end{proof}

Comparing~\eqref{recurrence-Pnk} with~\eqref{recurrence-01}, we see that the numbers $P(n,k)$
satisfy the same recurrence relation and
initial conditions as $N(n,k)$. Hence they agree.
The bijection $(a,b)\rightarrow (b',a')$ on $\mmn$ defined by $a'=2n+1-a, b'=2n+1-b$ shows that
$N(n,k)$ is also the number of perfect matchings of $[2n]$
in which exactly $k$ blocks with odd minimal elements.
Now it is well known that
the exponential generating function for $N_n(x)$ is given by (see~\cite{Ma13,Ma14}):
\begin{equation}\label{EGF-Nnx}
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}
%It follows from~\cite[Theorem~9]{Ma13} that
%\begin{equation*}\label{Anx-Nnx02}
%2^nxA_n(x)=\sum_{k=0}^n\binom{n}{k}N_k(x)N_{n-k}(x).
%\end{equation*}
By~\eqref{Ankx-def01} and~\eqref{EGF-Nnx},
\begin{equation}\label{An2x-Nnx}
A_n^{(2)}(x)=x^{n}N_n\left(\frac{1}{x}\right).
\end{equation}
Therefore, it follows from~\eqref{Ankx-Savage} and~\eqref{An2x-Nnx} that
\begin{equation*}\label{Nnx-exc-cyc}
N_n(x)=\sum_{\pi\in\msn}2^{n-\cyc(\pi)}x^{n-\exc(\pi)}.
\end{equation*}
%The motivation of this paper is to provide a bijective proof of the following identity:
%$$\sum_{\m\in\mmn}x^{\so(\m)}=\sum_{\pi\in\msn}2^{n-\cyc(\pi)}x^{n-\exc(\pi)}.$$

\section{The $\spma$-sequences}\label{Section03}
\hspace*{\parindent}

Let $Y_n=(y_1,y_2,\ldots,y_n)$ be a sequence of integers of length $n$.
For $1\leq k\leq n$, let $\POS(Y_k)$ (resp. $\NPOS(Y_k)$) denote the set of positive (resp. non-positive) entries of $Y_k=(y_1,y_2,\ldots,y_k)$.
We define
$$\pos(Y_k)=\#\POS(Y_k),~\npos(Y_k)=\#\NPOS(Y_k).$$
Let $P_k$ be the set $\{1,2,3,\ldots, 2k\}$ and let $N_k$ be the set $\{0,-1,-2,\ldots, -2k\}$.
In particular, $P_0=\emptyset,~P_1=\{1,2\},~N_0=\{0\}$ and $N_1=\{0,-1,-2\}$.

%Let $k\geq 1$ and $\ell\geq 0$.
%Given a sequence $Y_n=(y_1,y_2,\ldots,y_n)$, where $y_i\in[-2\ell,2k]\subseteq\z$ for $1\leq i\leq n$.
%We denote by $\pos(Y_n)$ (resp. $\nega(Y_n)$) the number of positive (resp. negative) entries in $Y_n$.
%Let $\st(Y_n)$ be the number of $0$'s in $Y_n$. Thus $\nega(Y_{n})+\st(Y_{n})+\pos(Y_n)=n$.
%We define
%$$P_k=\{1,2,3,\ldots, 2k\}~\textrm{and}~ N_{\ell}=\{-2\ell, -2\ell+1,\ldots,-3,-2,-1,0\}.$$
\begin{definition}\label{def01}
Let $Y_n=(y_1,y_2,\ldots,y_n)$ be a sequence of integers of length $n$. We call the sequence $Y_n$ an $\spma$-sequence of length $n$
if $y_1=0$, and $y_{k+1}\in P_{\npos(Y_k)}\cup N_{\pos(Y_k)}$ for $k =1,2,3,\ldots, n-1$.
%We say that a sequence $Y_n=(y_1,y_2,\ldots,y_n)$ the {\it $\spma$-sequence} of length $n$ if $y_1=0$ and
%$y_k\in P_{s_k}\bigcup N_{t_k}$ for $2\leq k\leq n$, where $s_k$ and $t_k$ are respectively
%the number of nonpositive entries and positive entries of the first $k-1$ entries of $Y_n$.
%, i.e., $s_k=\nega(Y_{k-1})+\st(Y_{k-1})$ $t_k=\pos(Y_{k-1})$, where $Y_{k-1}=(y_1,y_2,\ldots,y_{k-1})$.
\end{definition}
%In particular, $P_1\bigcup N_0=\{0,1,2\}, P_1\bigcup N_1=\{-2,-1,0,1,2,\}$ and $P_2\bigcup N_0=\{0,1,2,3,4\}$.

%Denote by $\st(Y_n)$ the number of $0$'s in $Y_n$.
%Let $\pos(Y_n)$ (resp. $\nega(Y_n)$) be the number of positive (resp. negative) entries in $Y_n$.
%Careful consideration of Proposition~\ref{prop01} yields the following definition.
%\begin{definition}\label{def01}
%We call a sequence $Y_n$ the {\it $\spma$-sequence} of length $n$ if $y_1=0$ and
%$y_k\in P_{1+s_k}\bigcup N_{t_k}$ for $2\leq k\leq n$, where $s_k=\nega(Y_{k-1})+\st(Y_{k-1})-1$ and
%$t_k=\pos(Y_{k-1})$ for $k\geq 2$.
%\end{definition}
For example, $(0,1,-1,2,0)$ is a $\spma$-sequence, while $(0,1,-1,-4,2)$ is not
since $y_4=-4\not\in P_2\cup N_1$. Let $\spman$ denote the set of $\spma$-sequences of length $n$.
Note that $\npos(Y_{n-1})+\pos(Y_{n-1})=n-1$. This implies that the set
$P_{\npos(Y_{n-1})} \cup N_{\pos(Y_{n-1})}$ contains $2n-1$ elements. So there are $2n-1$ choices for $y_n$ and hence
 $$\#\spman=(2n-1)\#\spmann=(2n-1)!!.$$
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\hspace*{\parindent}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

We now present the first main result of this paper.
\begin{theorem}\label{thm01}
For any $n\geq 1$,
\begin{equation}\label{bijection01}
\sum_{\m\in\mmn}x^{\mk(\m)}=\sum_{Y_n\in \spman}x^{\npos(Y_n)}=\sum_{\sigma\in\mqn}x^{\ap(\sigma)}.
\end{equation}
\end{theorem}

%\begin{definition}
%Let $(c_1,c_2,\ldots,c_i)$ be one cycle of $\pi$. We say that $c_j$ is a {\it cycle descent} if $c_j>c_{j+1}$ for $1<j<i$.
%\end{definition}
%Let $\cdes(\pi)$ be the number of cycle descents of $\pi$.
%For example, for $\pi=(1,3,\textbf{4},2)(5,7)(6)$, we have $\cdes(\pi)=1$.
%For $\pi\in\msn$, it is clearly that $\exc(\pi)+\cyc(\pi)+\cdes(\pi)=n$. Therefore,
%it follows from~\eqref{Nnx-exc-cyc} that
%\begin{equation*}\label{Nnx-cdes}
%N_n(x)=\sum_{\pi\in\msn}x^{\cyc(\pi)+\cdes(\pi)}2^{n-\cyc(\pi)}.
%\end{equation*}
Let $\nega(Y_n)$ and $\zero(Y_n)$ be the number of negative entries and 0's in $Y_n$, respectively. Then
$\npos(Y_n)=\nega(Y_{n})+\zero(Y_{n})$.
The second main result is the following.
\begin{theorem}\label{thm05}
For any $n\geq 1$,
\begin{equation}\label{bijection03}
\sum_{Y_{n}\in \spman}x^{\nega(Y_{n})}y^{\zero(Y_{n})}=\sum_{\pi\in\msn}2^{n-\cyc(\pi)}x^{n-\cyc(\pi)-\exc(\pi)}y^{\cyc(\pi)}.
\end{equation}
%\begin{equation}\label{bijection03}
%\sum_{Y_{n}\in \spman}x^{\nega(Y_{n})}y^{\st(Y_{n})}=\sum_{\pi\in\msn}2^{n-\cyc(\pi)}x^{n-\exc(\pi)-\cyc(\pi)}y^{\cyc(\pi)}.
%\end{equation}
In particular,
$$\sum_{Y_{n}\in \spman}x^{\npos(Y_n)}=\sum_{\pi\in\msn}2^{n-\cyc(\pi)}x^{n-\exc(\pi)}.$$
%$$\sum_{Y_{n}\in \spman}\left(\frac{1}{2}\right)^{n-\zero(Y_n)}x^{\zero(Y_n)}=\sum_{\pi\in\msn}x^{\cyc(\pi)}.$$
%\begin{equation}\label{bijection03}
%%\end{equation}
%Equivalently,
%\begin{equation*}
%\sum_{A_{n}\in \myn}x^{\nega(A_{n})}y^{\st(A_{n})+1}=2^{n+1}\sum_{\pi\in\msnn}x^{\cdes(\pi)}\left(\frac{y}{2}\right)^{\cyc(\pi)}.
%\end{equation*}
\end{theorem}

%Recall that $\nega(Y_{n})+\st(Y_{n})+\pos(Y_n)=n$.
%The following corollary is immediate.
%\begin{cor}\label{cor-Anx}
%%For $n\geq 1$, we have
%$$A_n(x)=\sum_{Y_{n}\in \myn}\left(\frac{1}{2}\right)^{\nega(Y_{n})+\pos(Y_n)}x^{\pos(Y_n)}.$$
%Equivalently,
%$$2^nA_n(z)=\sum_{Y_{n}\in \spman}2^{\zero(Y_{n})}z^{\pos(Y_n)}.$$
%\end{cor}
%\begin{proof}

%Setting $x=\frac{1}{2},~y=1$ and replacing $z$ by $\frac{1}{2}z$ in~\eqref{bijection03}, we have
%\begin{equation}\label{Eulerian}
%\sum_{Y_{n}\in \spman}\left(\frac{1}{2}\right)^{\nega(Y_{n})+\pos(Y_n)}z^{\pos(Y_n)}=\sum_{\pi\in\msn}z^{\exc(\pi)}.
%\end{equation}
%Multiplying both sides of~\eqref{Eulerian} by $2^n$, we get the corollary.
%\end{proof}

In the following subsections, we will give
constructive proofs for the main results.
%As a consequence, we get a combinatorial proof of the following equalities:
%\begin{equation}\label{bijection04}
%\sum_{\sigma\in\mqn}x^{\ap(\sigma)}=\sum_{\pi\in\msn}2^{n-\cyc(\pi)}x^{n-\exc(\pi)}=\sum_{\m\in\mmn}x^{\so(\m)}.
%\end{equation}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\subsection{Constructive Proof of the left equality of~\eqref{bijection01}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{A bijection between $\spma$-sequences and Perfect matchings}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hspace*{\parindent}

We define
\begin{align*}
 \spma_{n,k}&=\{Y_n\in\spman\mid \npos(Y_n)=k\}, \\
  \mm_{2n,k}&=\{\m\in\mmn\mid \mk(\m)=\emph{k}\}.
\end{align*}
%Let $\A_n,k$ be the set of all Stirling permutations $\sigma$ of order $n$ with $\ap(\sigma) = k$;
Now we start to construct a bijection, denoted by $\Phi_1$, between $\spma_{n,k}$ and $\mm_{2n,k}$. When $n=1$, we have
$y_1=0$. Set $\Phi_1(Y_1)=(1,2)$. This gives a bijection between $\spma_{1,1}$ and $\mm_{2,1}$.
Let $n=m$. Suppose $\Phi_1$ is a bijection between $\spma_{m,k}$ and $\mm_{2m,k}$ for all $k$.
Consider the case $n=m+1$. Let $Y_{m+1}=(y_1,y_2,\ldots,y_m,y_{m+1})\in \spma_{m+1}$.
Then $Y_m=(y_1,y_2,\ldots,y_m)\in \spma_{m,k}$ for some $k$.
Assume $\Phi_1(Y_m)\in \mm_{2m,k}$. Consider the following five cases:
\begin{enumerate}
  \item [\rm ($i$)] If $y_{m+1}=2i-1>0$, then let $\Phi_1(Y_{m+1})$ be obtained from $\Phi_1(Y_m)$ by replacing the $i$th marked block $(c,d)$ by two blocks $(c,2m+1),(d,2m+2)$. In this case, $(c,2m+1)$ is an unmarked block and $(d,2m+2)$ is a marked block. Hence, $\mk(\Phi_1(Y_{m+1}))=\mk(\Phi_1(Y_m))=k$;
  \item [\rm ($ii$)] If $y_{m+1}=2i>0$, then let $\Phi_1(Y_{m+1})$ be obtained from $\Phi_1(Y_m)$ by replacing the $i$th marked block $(c,d)$ by two blocks $(c,2m+2),(d,2m+1)$. Hence, $\mk(\Phi_1(Y_{m+1}))=\mk(\Phi_1(Y_m))=k$;
 \item [\rm ($iii$)] If $y_{m+1}=-(2i-1)<0$, then let $\Phi_1(Y_{m+1})$ be obtained from $\Phi_1(Y_m)$ by replacing the $i$th unmarked block $(e,f)$ by two blocks $(e,2m+1),(f,2m+2)$. In this case, $\mk(\Phi_1(Y_{m+1}))=\mk(\Phi_1(Y_m))+1=k+1$;
  \item [\rm ($iv$)] If $y_{m+1}=-2i<0$, then let $\Phi_1(Y_{m+1})$ be obtained from $\Phi_1(Y_m)$ by replacing the $i$th unmarked block $(e,f)$ by two blocks $(e,2m+2),(f,2m+1)$. In this case, $\mk(\Phi_1(Y_{m+1}))=\mk(\Phi_1(Y_m))+1=k+1$;
  \item [\rm ($v$)] If $y_{m+1}=0$, then let $\Phi_1(Y_{m+1})$ be obtained from $\Phi_1(Y_m)$ by appending the marked block $(2m+1,2m+2)$ right after $\Phi_1(Y_{m})$. In this case, $$\mk(\Phi_1(Y_{m+1}))=\mk(\Phi_1(Y_m))+1=k+1.$$
\end{enumerate}
After the above step, we write the obtained perfect matching $\Phi_1(Y_{m+1})$ in standard form.
It is easy to verify that if $y_{m+1}\in P_{\npos(Y_m)}$ (resp. $y_{m+1}\in N_{\pos(Y_m)}$),
then $\Phi_1(Y_{m+1})\in \mm_{2m+2,k}$ (resp. $\Phi_1(Y_{m+1})\in \mm_{2m+2,k+1}$).
By induction, we see that $\Phi_1$ is the desired bijection between $\spma_{n,k}$ and $\mm_{2n,k}$,
which also gives a constructive proof of the left equality of~\eqref{bijection01}.

In the following example, if $(a,b)$ is a marked block, then we put the entries $a$ and $b$ into a square bracket, i.e., replace $(a,b)$ by $[a,b]$.
Otherwise, the parenthesis that contains $a$ and $b$ unchanged.
\begin{ex}
Let $Y_4=(0,1,-2,4)$.
The correspondence between $Y_4$ and $\Phi_1(Y_4)$ is built up as follows:
\begin{align*}
0&\Leftrightarrow \{[1,2]\};\\
1&\rightarrow \{[1,2]\}\Leftrightarrow \{(1,3),[2,4]\};\\
-2&\rightarrow \{(1,3),[2,4]\}\Leftrightarrow \{[1,6],(3,5),[2,4]\}=\{[1,6],[2,4],(3,5)\};\\
4&\rightarrow \{[1,6],[2,4],(3,5)\}\Leftrightarrow \{[1,6],[2,8],(4,7),(3,5)\}=\{[1,6],[2,8],(3,5),(4,7)\}.
%-1&\rightarrow \{[1,6],[2,8],(3,5),(4,7)\}\Leftrightarrow \{[1,6],[2,8],(3,9),[5,10],(4,7)\}=\{[1,6],[2,8],(3,9),(4,7),[5,10]\}.\\
\end{align*}
\end{ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{A bijection between $\spma$-sequences and Stirling permutations}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hspace*{\parindent}

Let$\mq\left(P_{\npos(Y_k)}\cup N_{\pos(Y_k)}\right)$ be the set of Stirling permutations of order $k$ with exactly $\npos(Y_k)$ ascent plateaus.
In particular, $\mq \left(P_1\cup N_0\right)=\{11 \}$, $\mq \left(P_1\cup N_1\right)=\{2211,1221\}$ and $\mq \left(P_2\cup N_0\right)=\{1122\}$.
We now introduce a definition of \emph{labeled Stirling permutations}.
\begin{definition}
Let $\sigma\in \mq\left(P_{\npos(Y_k)}\cup N_{\pos(Y_k)}\right)$.
If $i_1<i_2<\ldots<i_{\npos(Y_k)}$ are the ascent plateaus of $\sigma$, then we put the superscript labels $2\ell-1$ before $i_{\ell}$ and $2\ell$ after it,
where $1\leq \ell\leq \npos(Y_k)$. In the remaining positions, we put the superscript labels $-1,-2,\ldots,-2\pos(Y_k)$ and $0$ from left to right.
\end{definition}
As an example, the labeled version of 13324421 is given by $^{-1}1^{1}3^{2}3^{-2}2^{3}4^{4}4^{-3}2^{-4}1^{0}$.
We define $$\mq_{n,k}=\{\sigma\in\mqn\mid \ap(\sigma)=k\}.$$

Now we start to construct a bijection, denoted by $\Phi_2$, between $\spma_{n,k}$ and $\mq_{n,k}$.
When $n=1$, we have $y_1=0$. Set $\Phi_2(Y_1)=11$. This gives a bijection between $\spma_{1,1}$ and $\mq_{1,1}$.
Let $n=m$. Suppose $\Phi_2$ is a bijection between $\spma_{m,k}$ and $\mq_{m,k}$ for all $k$.
Consider the case $n=m+1$. Let $Y_{m+1}=(y_1,y_2,\ldots,y_m,y_{m+1})\in \spma_{m+1}$. Then
$Y_m=(y_1,y_2,\ldots,y_m)\in \spma_{m,k}$ for some $k$.
Assume $\Phi_2(Y_m)\in \mq_{m,k}$. Consider the following three cases:
\begin{enumerate}
  \item [\rm ($i$)] If $y_{m+1}=i>0$, then let $\Phi_2(Y_{m+1})$ be obtained from $\Phi_2(Y_{m})$ by
inserting the pair $(m+1)(m+1)$ to the position of $\Phi_2(Y_m)$ with label $i$. Hence $Y_{m+1}\in \spma_{m+1,k}$ and $\Phi_2(Y_{m+1})\in \mq_{m+1,k}$.
 \item [\rm ($ii$)] If $y_{m+1}=-i<0$, then let $\Phi_2(Y_{m+1})$ be obtained from $\Phi_2(Y_{m})$ by
inserting the pair $(m+1)(m+1)$ to the position of $\Phi_2(Y_m)$ with label $-i$. Hence $Y_{m+1}\in \spma_{m+1,k+1}$ and $\Phi_2(Y_{m+1})\in \mq_{m+1,k+1}$.
 \item [\rm ($iii$)] If $y_{m+1}=0$, then let $\Phi_2(Y_{m+1})$ be obtained from $\Phi_2(Y_{m})$ by appending the pair $(m+1)(m+1)$
 right after $\Phi_2(Y_{m})$. Hence $Y_{m+1}\in \spma_{m+1,k+1}$ and $\Phi_2(Y_{m+1})\in \mq_{m+1,k+1}$.
\end{enumerate}
By induction, we see that $\Phi_2$ is the desired bijection between $\spma_{n,k}$ and $\mq_{n,k}$ for all $k$,
which also gives a constructive proof of the right equality of~\eqref{bijection01}.

%We now present an example to illustrate the bijection between $\myn$ and $\mqnn$.
\begin{ex}
Let $Y_4=(0,2,-1,3)$.
The correspondence between $Y_4$ and $\Phi_2(Y_4)$ is built up as follows:
\begin{align*}
0&\Leftrightarrow 11;\\
2&\rightarrow ^{1}1^{{2}}1^{0}\Leftrightarrow 1221;\\
-1&\rightarrow  ^{-1}1^{1}2^{2}2^{-2}1^{0}\Leftrightarrow 331221;\\
3&\rightarrow ^{1}3^{2}3^{-1}1^{{3}}2^{4}2^{-2}1^{0}\Leftrightarrow 33144221.
%-2&\rightarrow ^{1}3^{2}3^{-1}1^{3}4^{4}4^{\textbf{-2}}2^{-3}2^{-4}1^{0}\Leftrightarrow 3314455221.
%2&\rightarrow ^{1}3^{\textbf{2}}3^{-1}1^{3}4^{4}4^{5}5^{6}5^{-2}2^{-3}2^{-4}1^{0}\Leftrightarrow 366314455221.
\end{align*}
\end{ex}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{A map from $\spma$-sequences to permutations}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\hspace*{\parindent}

In the following discussion, we always write $\pi\in\msn$
by its \emph{standard cycle decomposition}, in which each
cycle is written with its smallest entry first and the cycles are written in ascending order of their
smallest entry.
We now introduce a definition of \emph{labeled permutations}.
\begin{definition}
Let $\pi\in\msn$ with $p$ excedances.
If $i_1<i_2<\cdots <i_p$ are the excedances,
then we put superscript labels $-k$ between $i_k$ and $\pi(i_k)$, where $1 \leq k\leq p$.
In the remaining positions except the first position of each cycle, we put the superscript labels $1,2,\ldots,n-p$ from left to right.
\end{definition}

%As an example, the labeled version of $({1},{3},7,4,2)(5)({6},8)$ is given by
%$({1}~^{-1},~{3}^{-2},~7~^{1}~4~^{2},~2~^{3})(5^{4})({6}~^{-3}~,8~^{5}).$

The number of {\it anti-excedances} of $\pi\in\msn$ is defined by $\aexc(\pi)=n-\exc(\pi)$.
Let $$\msss_{n,k}=\{\pi\in\msn \mid \aexc(\pi)=k\}.$$
Now we start to construct a map, denoted by $\Phi_3$, from $\spma_{n,k}$ to $\msss_{n,k}$.
When $n=1$, we have $y_1=0$. Set $\Phi_3(Y_1)=(1)$. This gives a map from $\spma_{1,1}$ to $\msss_{1,1}$.
Let $n=m$. Suppose $\Phi_3$ is a map from $\spma_{m,k}$ to $\msss_{m,k}$ for all $k$ and
there are $2^{m-t}$ sequences in $\spma_{m,k}$ are mapped
to one permutation $\pi\in \msss_{m,k}$ with $\cyc(\pi)=t$.
Consider the case $n=m+1$. Let $Y_{m+1}=(y_1,y_2,\ldots,y_m,y_{m+1})\in \spma_{m+1}$. Then
$Y_m=(y_1,y_2,\ldots,y_m)\in \spma_{m,k}$ for some $k$.
Assume $\Phi_3(Y_m)\in \msss_{m,k}$. Consider the following three cases:
\begin{enumerate}
  \item [\rm ($i$)] If $y_{m+1}=2i-1>0$ or $y_{m+1}=2i>0$, then let $\Phi_3(Y_{m+1})$ be obtained from $\Phi_3(Y_{m})$
  by inserting the entry $m+1$ to the position of $\Phi_3(Y_m)$ with label $i$. Since $\exc(\Phi_3(Y_{m+1})=\exc(\Phi_3(Y_{m})+1=m-k+1$, we have $\aexc(\Phi_3(Y_{m+1}))=k$. Moreover, $\cyc(\Phi_3(Y_{m+1}))=\cyc(\Phi_3(Y_{m}))$.
  %Hence we have two sequences $Y_{m+1}\in \spma_{m+1,k}$ map to one element
  %$\Phi_3(Y_{m+1})\in \msss_{m+1,k}$.
  Therefore, we have
$2\cdot2^{m-t}=2^{m+1-t}$ sequences in $\spma_{m+1,k}$ that are mapped to one permutation $\pi\in \msss_{m+1,k}$ with
$\cyc(\pi)=t$.
 \item [\rm ($ii$)] If $y_{m+1}=-(2i-1)<0$ or $y_{m+1}=-2i<0$, then let $\Phi_3(Y_{m+1})$ be obtained from $\Phi_3(Y_{m})$
  by inserting the entry $m+1$ to the position of $\Phi_3(Y_m)$ with label $-i$. Since $\exc(\Phi_3(Y_{m+1})=\exc(\Phi_3(Y_{m})=m-k$, we have
  $\aexc(\Phi_3(Y_{m+1}))=k+1$. Moreover, $\cyc(\Phi_3(Y_{m+1}))=\cyc(\Phi_3(Y_{m}))$.
  %Hence we have two sequences $Y_{m+1}\in \spma_{m+1,k+1}$ map to one element
  %$\Phi_3(Y_{m+1})\in \msss_{m+1,k+1}$.
  Therefore, we have $2\cdot2^{m-t}=2^{m+1-t}$ sequences in $\spma_{m+1,k+1}$ that are mapped to one permutation $\pi\in \msss_{m+1,k+1}$ with
$\cyc(\pi)=t$.
 \item [\rm ($iii$)] If $y_{m+1}=0$, then let $\Phi_3(Y_{m+1})$ be obtained from $\Phi_3(Y_{m})$ by appending a new cycle $(m+1)$ right after $\Phi_3(Y_{m})$.
 Since $\exc(\Phi_3(Y_{m+1})=\exc(\Phi_3(Y_{m})=m-k$, we have $\aexc(\Phi_3(Y_{m+1}))=k+1$. Moreover, $\cyc(\Phi_3(Y_{m+1}))=\cyc(\Phi_3(Y_{m}))+1$.
 %Hence we have one sequence $Y_{m+1}\in \spma_{m+1,k+1}$ maps to one element
  %$\Phi_3(Y_{m+1})\in \msss_{m+1,k+1}$.
  Therefore, we have $1\cdot2^{m-t}=2^{m-t}$ sequences in $\spma_{m+1,k+1}$ that are mapped to one permutation $\pi\in \msss_{m+1,k+1}$ with
$\cyc(\pi)=t+1$.
  \end{enumerate}
After the above step, we first write the obtained $\Phi_3(Y_{m+1})$ in standard cycle decomposition, and then label it.
By induction,
we see that $\Phi_3$ is the desired map from $\spma_{n,k}$ to $\msss_{n,k}$, which also
gives a constructive proof of~\eqref{bijection03}.

\begin{ex}
Given $\pi=(1~3 ~5~ 2)(4)$. The map $\Phi_3$ can be done if you proceed as follows:
\begin{align*}
y_1=0~&\rightarrow (1^{1});\\
y_2=1~\textrm{or}~ y_2=2~&\rightarrow (1~^{-1}~2~^{1});\\
y_3=-1~\textrm{or}~ y_3=-2~&\rightarrow (1~^{-1}~3~^{1}~2~^{2});\\
y_4=0~&\rightarrow (1~^{-1}~3~^{1}~2~^{2})(4~^{3});\\
y_5=1~\textrm{or}~ y_5=2~&\rightarrow (1^{-1}3^{-2}5^{1}2^{2})(4^{3}).
%(1~^{-1}~3~^{-2}~5~^{1}~2^{2})(4^{3})&\rightarrow (1,3,5,2,6)(4) \Leftrightarrow y_6=3~\textrm{or}~ y_6=4.
\end{align*}
Hence, by $\Phi_3$, there are eight $\spma$-sequences that are mapped to $\pi$:
$$(0,1,-1,0,1);(0,1,-1,0,2);(0,1,-2,0,1);(0,1,-2,0,2);$$
$$(0,2,-1,0,1);(0,2,-1,0,2);(0,2,-2,0,1);(0,2,-2,0,2).$$
\end{ex}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Concluding remarks}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
The key observation of the paper is the recurrence relation~\eqref{recurrence-01}, from which we discover the
relationship among Stirling permutations, the cycle structure of permutations and
perfect matchings. We believe that the techniques developed in the paper
can be used to deal with various combinatorial structures.
Moreover, it would be interesting to study pattern avoidance
properties of the $\spma$-sequences.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The authors thank the referee for his valuable suggestions which lead to a substantial improvement of the paper.
They also thank Chan-Liang Chung for his valuable discussion.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{thebibliography}{99}
\bibitem{Bona08}
M. B\'ona, Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel
and Stanley, \newblock {\em SIAM J. Discrete Math.}, 23:401--406, 2008/09.

\bibitem{Bre94}
F. Brenti. \newblock $q$-Eulerian polynomials arising from Coxeter groups.
\newblock {\em European J. Combin.}, 15:417--441, 1994.

\bibitem{Bre00}
F. Brenti. \newblock A class of $q$-symmetric functions arising from plethysm.
\newblock {\em J. Combin. Theory Ser. A}, 91:137--170, 2000.

%\bibitem{Chow08}
%C.-O. Chow, On certain combinatorial expansions of the Eulerian polynomials, \newblock {\em Adv. in Appl. Math.} 41 (2008), 133--157.


\bibitem{Dilks09}
K. Dilks, T.K. Petersen, J.R. Stembridge. \newblock Affine descents and the Steinberg torus. \newblock {\em Adv. in Appl. Math.},
42:423--444, 2009.

\bibitem{FS70}
D. Foata, M. Sch\"utzenberger. \newblock Th\'eorie G\'eom\'etrique des
Polyn\^omes Euleriens. \newblock {\em Lecture Notes in Mathematics}, vol. 138,
Springer-Verlag, Berlin-New York, 1970.

\bibitem{Gessel78}
I. Gessel and R.P. Stanley. \newblock Stirling polynomials. \newblock {\em J. Combin. Theory Ser.
A}, 24:25--33, 1978.


\bibitem{Haglund12}
J. Haglund, M. Visontai. \newblock Stable multivariate Eulerian polynomials and generalized Stirling permutations, \newblock {\em European J. Combin.}, 33:477--487, 2012.


\bibitem{Janson11}
S. Janson, M. Kuba and A. Panholzer. \newblock Generalized Stirling permutations, families of increasing trees and urn models,
\newblock {\em J. Combin. Theory Ser. A}, 118:94--114, 2011.


\bibitem{Ma13}
S.-M. Ma. \newblock A family of two-variable derivative polynomials for tangent and secant.
\newblock {\em Electron. J. Combin.}, 20(1):~\#P11, 2013.

\bibitem{Ma1302}
S.-M. Ma. \newblock Some combinatorial arrays generated by context-free grammars. \newblock {\em European J. Combin.}, 34:1081--1091, 2013.

\bibitem{Ma14}
S.-M. Ma, T. Mansour. \newblock The $1/k$-Eulerian polynomials and $k$-Stirling permutations. \newblock {\em Discrete Math.}, 338:1468--1472, 2015.

%\bibitem{Remmel14}
%J.B. Remmel, A.T. Wilson. \newblock Block patterns in Stirling permutations. \arxiv{1402.3358}.

%\bibitem{Savage1201}
%C.D. Savage and M.J. Schuster. \newblock Ehrhart series of lecture hall polytopes and Eulerian
%polynomials for inversion sequences. \newblock {\em J. Combin. Theory Ser. A}, 119: 850--870, 2012.

\bibitem{Savage1202}
C.D. Savage and G. Viswanathan. \newblock The $1/k$-Eulerian polynomials. \newblock {\em Electron. J. Combin.},
19(1):~\#P9, 2012.
\end{thebibliography}

\end{document}
