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

% 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}
\usepackage{xspace}
% 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}}}

% all overfull boxes must be fixed;
% i.e. there must be no text protruding into the margins


% declare theorem-like environments
\def\red{\textcolor{red} }
\def\l{\ell}
\def\w{w}
\def\u{\ensuremath{\mathcal U}\xspace}

\newtheorem{theorem}{Theorem}%[section]
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{conj}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{ex}[theorem]{Example}
\newtheorem{problem}[theorem]{Problem}


\newcommand{\cpk}{{\rm cpk\,}}
\newcommand{\bs}{{\mathfrak S}}
\newcommand{\lpk}{{\rm lpk\,}}
\newcommand{\uprun}{{\rm uprun\,}}
\newcommand{\pk}{{\rm pk\,}}
\newcommand{\des}{{\rm des\,}}
\newcommand{\Exc}{{\rm Exc\,}}
\newcommand{\exc}{{\rm exc\,}}
\newcommand{\rmin}{{\rm rmin\,}}
\newcommand{\cyc}{{\rm cyc\,}}
\newcommand{\fix}{{\rm fix\,}}
\newcommand{\DS}{\mathcal{DS}}
\newcommand{\mc}{{\mathcal C}_A}
\newcommand{\cc}{{\mathcal C}}
\newcommand{\man}{\mathfrak{A}_n}
\newcommand{\D}{\mathfrak{D}}
\newcommand{\msb}{\mathfrak{S}_8}
\newcommand{\msm}{\mathfrak{S}_m}
\newcommand{\mcn}{\mathfrak{C}_{2n}}
\newcommand{\mcnn}{\mathfrak{C}_{2n+1}}
\newcommand{\msn}{\mathfrak{S}_n}
\newcommand{\rss}{\mathcal{SS}}
\newcommand{\ms}{\mathfrak{S}}
\newcommand{\inv}{{\rm inv\,}}
\newcommand{\msnn}{\mathfrak{S}_{n+1}}
\newcommand{\ud}{{\rm ud\,}}
\newcommand{\as}{{\rm as\,}}
\newcommand{\rs}{\mathcal{RS}}
\newcommand{\bn}{{\rm\bf n}}
\newcommand{\lrf}[1]{\lfloor #1\rfloor}
\newcommand{\lrc}[1]{\lceil #1\rceil}
\newcommand{\sep}{\preceq}
\newcommand{\sgn}{{\rm sgn\,}}
\newcommand{\mqn}{\mathcal{Q}_n}
\newcommand{\z}{ \mathbb{Z}}
\newcommand{\asc}{{\rm asc\,}}
\DeclareMathOperator{\N}{\mathbb{N}}
\DeclareMathOperator{\LHP}{LHP}
\DeclareMathOperator{\R}{\mathbb{R}}
\DeclareMathOperator{\Q}{\mathbb{Q}}
\DeclareMathOperator{\re}{Re}
\newcommand{\rz}{{\rm RZ}}
\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}}}

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

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

\title{\bf The peak statistics on simsun permutations}

% 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) 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 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{Feb 1, 2016}{, 2016}{, 2016}\\
\small Mathematics Subject Classifications: 05A05, 05A15}

\begin{document}

\maketitle

\begin{abstract}
 In this paper, we study the relationship among left peaks,
interior peaks and up-down runs of simsun permutations. Properties of the generating polynomials, including the
recurrence relation, generating function and real-rootedness are studied. Moreover, we introduce and study
simsun permutations of the second kind.

  % keywords are optional
  \bigskip\noindent \textbf{Keywords:} Simsun permutations; Left peaks; Interior peaks; Alternating runs; Excedances
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Let $\msn$ denote the symmetric group of all permutations of $[n]$, where $[n]=\{1,2,\ldots,n\}$.
Let $\pi=\pi(1)\pi(2)\cdots\pi(n)\in\msn$. A descent of $\pi$ is an index $i\in [n-1]$ such that $\pi(i)>\pi(i+1)$.
We say that $\pi$ has no {\it double descents} if there is no
index $i\in [n-2]$ such that $\pi(i)>\pi(i+1)>\pi(i+2)$.
The permutation $\pi$ is called {\it simsun} if for all $k$, the
subword of $\pi$ restricted to $[k]$ (in the order
they appear in $\pi$) contains no double descents. For example,
$35142$ is a simsun permutation, but $35241$ is not.
Simsun permutations are useful in describing the action of the symmetric group on the
maximal chains of the partition lattice (see~\cite{Sundaram1994,Sundaram1995}).
They are a variant of Andr\'e permutations introduced by Foata and Sch\"utzenberger~\cite{Foata73}.
There has been much recent work related to simsun permutations~(see~\cite{Branden11,Chow11,Deutsch12,Eu14,Foata01,Hetyei98} for instance).

Let $a_i(n)$ be the number of distinct $S_n$-orbits such that the stabiliser of a maximal chain in the orbit is conjugate to the Young subgroup
$S_2^i\times S_1^{n-2i}$. Following Sundaram~\cite[Theorem 3.2]{Sundaram1994}, the numbers $a_i(n)$ satisfy the recurrence relation
\begin{equation}\label{ain-recu}
a_i(n+1)=ia_i(n)+(n-2i+2)a_{i-1}(n),
\end{equation}
with initial conditions $a_0(1)=1=a_1(2)$, $a_0(n)=0$ for $n>1$ and $a_i(n)=0$ if $2i>n$.
Let $|C|$ denote the cardinality of a set
$C$. The descent number of $\pi\in\msn$ is defined by $\des(\pi)=|\{i\in [n-1]: \pi(i)>\pi(i+1)\}|$.
Let $\rs_n$ be the set of simsun permutations of length $n$. Simion and Sundaram~\cite[p.~267]{Sundaram1994} discovered that $a_i(n)$ is the number of permutations in $\rs_{n-2}$ with $i-1$ descents and $|\rs_n|=E_{n+1}$,
where $E_{n}$ is the $n$th Euler number, which also is the number alternating permutations in $\msn$.
Let $$S(n,k)=|\{\pi\in\rs_n: \des(\pi)=k\}|.$$
In other words, let $S(n,k)=a_{k+1}(n+2)$.
We define
$S_n(x)=\sum_{k=0}^{\lrf{n/2}}S(n,k)x^k$.
It follows from~\eqref{ain-recu} that the numbers $S(n,k)$ satisfy the recurrence relation
\begin{equation}\label{Snk-recurrence}
S(n,k)=(k+1)S(n-1,k)+(n-2k+1)S(n-1,k-1),
\end{equation}
with the initial conditions $S(0,0)=1$ and $S(0,k)=0$ for $k\ge 1$, which is equivalent to
\begin{equation}\label{Snx-recu}
S_{n+1}(x)=(1+nx)S_n(x)+x(1-2x)S_n'(x),
\end{equation}
with $S_0(x)=1$. Let $RS(x,z)=\sum_{n\geq 0}S_n(x)\frac{z^n}{n!}$.
Chow and Shiu~\cite[Theorem~2.1]{Chow11} obtained that
\begin{equation}\label{Sxz-expon}
RS(x,z)=\left(\frac{\sqrt{2x-1}\sec\left(\frac{z}{2}\sqrt{2x-1}\right)}
{\sqrt{2x-1}-\tan\left(\frac{z}{2}\sqrt{2x-1}\right)}\right)^2.
\end{equation}
For convenience, here we list the first few terms of $S_n(x)$:
\begin{align*}
S_1(x)&=1,
S_2(x)=1+x,
S_3(x)=1+4x,
S_4(x)=1+11x+4x^2,
S_5(x)=1+26x+34x^2.
\end{align*}

%According to~\cite[Theorem~1]{Chow11}, the exponential generating function of $S_n(x)$ is given by
%$$S(x,z)=\sum_{n\geq 0}S_n(x)\frac{z^n}{n!}=\left(\frac{\sqrt{2x-1}\sec(\frac{z}{2}\sqrt{2x-1})}{\sqrt{2x-1}-\tan(\frac{z}{2}\sqrt{2x-1})}\right)^2$$
%
%Following~\cite[Theorem~1]{Chow11}, the exponential generating function of $S_n(x)$ is given by
% $$S(x,t)=\sum_{n\geq %0}S_n(x)\frac{z^n}{n!}=\left(\frac{\sqrt{2x-1}\sec\left(\frac{z}{2}\sqrt{2x-1}\right)}{\sqrt{2x-1}-\tan\left(\frac{z}{2}\sqrt{2x-1}\right)}\right)^2.$$
The number of peaks of permutations is certainly among the most important combinatorial statistics.
See, e.g.,~\cite{Billey13,Ma121,Ma123} and the references therein.
A {\it left peak} in $\pi$ is an index $i\in[n-1]$ such that $\pi(i-1)<\pi(i)>\pi(i+1)$, where we take $\pi(0)=0$.
Let $\lpk(\pi)$ denote the number of
left peaks in $\pi$. For example, $\lpk(21435)=2$.
Sundaram discovered that $a_i(n)$ is also the number of Andr\'e permutations in $\ms_{n-1}$ with $i$ left peaks (see~\cite[p.~175]{Sundaram1996}).
In fact, since any descent of a simsun permutation is a left peak, we have
\begin{equation*}\label{Snxlpk}
S_n(x)=\sum_{\pi\in\rs_n}x^{\lpk(\pi)}.
\end{equation*}

Let $\widehat{W}(n,k)=|\{\pi\in\msn: \lpk(\pi)=k\}|$.
Let
$\widehat{W}_n(x)=\sum_{k\geq0}\widehat{W}({n,k})x^k$.
The polynomials $\widehat{W}_n(x)$ satisfy the recurrence relation
\begin{equation*}\label{Wnkx-recurrence}
\widehat{W}_{n+1}(x)=(1+nx)\widehat{W}_n(x)+2x(1-x)\widehat{W}_n'(x),
\end{equation*}
with initial conditions $\widehat{W}_0(x)=\widehat{W}_1(x)=1$ (see~\cite{Ma121} for instance).
Following~\cite[A008971]{Sloane}, the exponential generating function of $\widehat{W}_n(x)$ is given as follows:
\begin{equation}\label{Wxz-expon}
\widehat{W}(x,z)=\sum_{n\geq 0}\widehat{W}_n(x)\frac{z^n}{n!}
=\frac{\sqrt{1-x}}{\sqrt{1-x}\cosh(z\sqrt{1-x})-\sinh(z\sqrt{1-x})}.
\end{equation}
By comparing~\eqref{Sxz-expon} with~\eqref{Wxz-expon}, we observe that
$RS(x,z)={\widehat{W}}^2\left(2x,z/2\right)$,
which leads to the following formula:
\begin{equation}\label{SnxWnx}
S_n(x)=\frac{1}{2^n}\sum_{k=0}^n\binom{n}{k}\widehat{W}_k(2x)\widehat{W}_{n-k}(2x).
\end{equation}

Denote by $B_n$ the hyperoctahedral group of rank $n$. Elements $\pi$ of $B_n$ 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\}$.
A {\it snake} of type $B_n$ is a signed permutation $\pi(1)\pi(2)\cdots\pi(n)$ of $B_n$ such that $0<\pi(1)>\pi(2)<\cdots\pi(n)$.
The $n$th {\it Springer number} $s_n$ is the number of snakes of type $B_n$.
Springer~\cite{Springer} derived the following generating function:
$$s(z)=\sum_{n\geq 0}s_n\frac{z^n}{n!}=\frac{1}{\cos z-\sin z}.$$
Recall that $S_n(1)=E_{n+1}$. It is clear that $\widehat{W}(2,z)=s(z)$.
Therefore,
as a special case of~\eqref{SnxWnx}, we get
$$E_{n+1}=\frac{1}{2^n}\sum_{k=0}^n\binom{n}{k}s_k s_{n-k}.$$
We refer the reader to~\cite{Chen11} for various structures related to Springer numbers.
Motivated by~\eqref{SnxWnx}, it is natural to further study peak statistics on simsun permutations.

This paper is organized as follows.
In Section~\ref{Section-2}, we give a constructive proof of a connection
between $S(n,k)$ and the number of permutations in $\ms_{n+1}$ with $k$ interior peaks.
%The numbers $S(n,k)$ arise often in combinatorics and other branches of mathematics~\cite[A094503,~A113897]{Sloane}
In Section~\ref{Section-3}, we count simsun permutations by their interior peaks. In Section~\ref{Section-4}, we count simsun permutations by their up-down runs. In Section~\ref{Section-5}, we introduce
simsun permutations of the second kind.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Relationship to interior peaks of permutations in $\msn$}\label{Section-2}
%\hspace*{\parindent}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
We first recall some basic definitions of peak statistics.
An {\it interior peak} in $\pi$ is an index $i\in\{2,3,\ldots,n-1\}$
such that $\pi(i-1)<\pi(i)>\pi(i+1)$. Let $\pk(\pi)$ denote the number of interior peaks
in $\pi$. For example, $\pk(21435)=1$. Let $W(n,k)$ be the number of permutations in $\msn$ with $k$ interior peaks and let $W_n(x)=\sum_{k\geq 0}W(n,k)x^k$.
%The polynomials $W_n(x)$ satisfy the recurrence relation
%\begin{equation*}
%W_{n+1}(x)=(nx-x+2)W_n(x)+2x(1-x)W'_n(x),
%\end{equation*}
%with initial conditions $W_1(x)=1,W_2(x)=2$ and $W_3(x)=4+2x$.
%It is well known~\cite[A008303]{Sloane} that
%\begin{equation*}
% \nonumber to remove numbering (before each equation)
% W(x,z)=\sum_{n\geq 1}W_n(x)\frac{z^n}{n!}=\frac{\sinh(z\sqrt{1-x})}{\sqrt{1-x}\cosh(z\sqrt{1-x})-\sinh(z\sqrt{1-x})}.
%\end{equation*}
We say that $\pi$ changes direction at position $i$ if either $\pi({i-1})<\pi(i)>\pi(i+1)$, or
$\pi(i-1)>\pi(i)<\pi(i+1)$, where $i\in\{2,3,\ldots,n-1\}$. We say that $\pi$ has $k$ {\it alternating runs} if there are $k-1$ indices $i$ where $\pi$ changes direction~(see~\cite{Andre84}).
Let $R(n,k)$ denote the number of permutations in $\msn$ with $k$ alternating runs and let $R_n(x)=\sum_{k=1}^{n-1}R(n,k)x^k$.
Let $d(n,k)$ denote the number of increasing 0-1-2 trees on $[n]$ with $k$ leaves (see~\cite[A094503]{Sloane}).
Let $D_n(x)=\sum_{k\geq 1}d(n,k)x^k$.

It follows from~\cite[Proposition 4]{Chow11} that
$D_{n+1}(x)=xS_{n}(x)$ for $n\ge 0$.
Using~\cite[Corollary 2,~Theorem 11]{Ma123}, we get
\begin{equation}\label{Rnx-Wnx}
R_n(x)=\frac{x(1+x)^{n-2}}{2^{n-2}}W_n\left(\frac{2x}{1+x}\right)=2x(1+x)^{n-2}S_{n-1}\left(\frac{x}{1+x}\right)\quad\textrm{for $n\ge 2$}.
\end{equation}
%Andr\'e~\cite{Andre84}
Combining~\eqref{Rnx-Wnx} and~\cite[Eq.~(13)]{Ma122}, we get the following result.
\begin{prop}
For $n\geq 1$ and $0\leq k\leq \lrf{\frac{n}{2}}$, we have
%we have $W_{n+1}(2x)=2^nS_n(x)$.
\begin{equation}\label{WnkSnk}
W(n+1,k)=2^{n-k}S(n,k).
\end{equation}
Let ${n \brace i}$ be the Stirling number of the second kind and let
\begin{equation*}
p(n,n-2k+1)=(-1)^{k}\sum_{i\geq 1}i!{n \brace i}(-2)^{n-i}\left[\binom{i}{n-2k}-\binom{i}{n-2k+1}\right].
\end{equation*}
Then
$$S_n(x)=\frac{1}{2^{n+1}x}\sum_{k=0}^{\lrf{{n}/{2}}+1}p(n+1,n-2k+2)(2x-1)^k\quad\textrm{for $n\ge 1$}.$$
\end{prop}

In the rest of this section, we give a constructive proof of~\eqref{WnkSnk}.
Let $$D(\pi)=\{i\in[n-2]: \pi(i)>\pi(i+1)\}$$ be the descent set of $\pi\in\rs_{n}$.
It should be noted that if we get a permutation $\pi'\in\rs_{n+1}$ from a permutation $\pi\in\rs_{n}$
by inserting the entry $n+1$ into $\pi$, then the entry $n+1$ cannot be inserted before $\pi(i)$, where $i\in D(\pi)$.
In the following discussion, we always assume that all permutations in $\rs_{n}$ are prepended by 0.
That is, we identify a permutation $\pi(1)\pi(2)\cdots\pi(n)\in\rs_n$ with
the permutation $\pi(0)\pi(1)\pi(2)\cdots\pi(n)$, where $\pi(0)=0$.
Define $\rs_{n,k}=\{\pi\in\rs_n \mid \des(\pi)=k\}$. Set $\overleftarrow{D}(\pi)=\{i-1: i\in D(\pi)\}$.
We can now introduce a definition of the {\it labeled simsun permutations}.
\begin{definition}\label{def01}
Let $\pi\in\rs_{n,k}$.
Suppose $i_1<i_2<\cdots<i_k$ are elements of $D(\pi)$. Then we put the superscript label $x_{r}$
right after $\pi(i_{r})$, where $1\leq r\leq k$.
%Moreover, we put the superscript label $x_{k+1}$ in the end of $\pi$.
If $j_1<j_2<\cdots<j_{n-2k}$ are elements of the set $\{0,1,2,\ldots,n-1\}\setminus(D(\pi)\cup \overleftarrow{D}(\pi))$,
then we put the superscript label $y_{s}$
right after $\pi(j_s)$, where $1\leq s\leq n-2k$.
\end{definition}
%If we insert the entry $n+1$ into $\pi\in\rs_{n,k}$ with
%superscript label $y_s$ (resp. $x_r$), then the insertion of $n+1$ does (resp. does not) form a new descent.
Let $\ms_{n,k}=\{\pi\in\msn \mid \pk(\pi)=k\}$. We introduce a definition of {\it labeled permutations}.
\begin{definition}
Let $\pi\in\ms_{n,k}$.
Suppose $i_1<i_2<\cdots<i_k$ are indices of the interior peaks of $\pi$. Then we put the superscript labels $p_r$
immediately before and right after $\pi(i_{r})$, where $1\leq r\leq k$.
%Moreover, we put the superscript label $x_{k+1}$ in the end of $\pi$.
 If $j_1<j_2<\cdots<j_{n-2k-1}$ are elements of the set
 $\{1,2,3,\ldots,n-1\}\setminus (\{i_1,i_2,\ldots,i_k\}\cup \{i_1-1,i_2-1,\ldots,i_k-1\})$,
then we put the superscript label $q_{s}$
right after $\pi(j_s)$, where $1\leq s\leq n-2k-1$.
\end{definition}

In the following, we shall add labels to permutations in $\rs_{n,k}$ and $\ms_{n,k}$.
As an example, for $\pi=34125$, if we say that $\pi\in \rs_{5,1}$, then the labeling of $\pi$
is given by $^{y_1}34^{x_1}1^{y_2}2^{y_3}5$; if we say that $\pi\in\ms_{5,1}$, then the labeling of $\pi$
is given by $3^{p_1}4^{p_1}1^{q_1}2^{q_2}5$.

Now we construct a correspondence, denoted by $\Phi$, between $\rs_{n,k}$ and $\ms_{n+1,k}$.
When $n=1$, the correspondence between $\rs_{1,0}$ and $\ms_{2,0}$ is given by
$$^{y_1}1 \xlongleftrightarrow{\Phi} \{1^{q_1}2,2^{q_1}1\}.$$
When $n=2$, the correspondence between $\rs_{2,k}$ and $\ms_{3,k}$ is given by
\begin{align*}
^{y_1}1^{y_2}2&\xlongleftrightarrow{\Phi} \{1^{q_1}2^{q_2}3,3^{q_1}1^{q_2}2,2^{q_1}1^{q_2}3,3^{q_1}2^{q_2}1\};\\
2^{x_1}1& \xlongleftrightarrow{\Phi} \{1^{p_1}3^{p_1}2,2^{p_1}3^{p_1}1\}.
\end{align*}
Let $n=m$. Suppose $\Phi$ is a correspondence between $\rs_{m,k}$ and $\ms_{m+1,k}$ for all $k$.
More precisely, given an element $\pi\in\rs_{m,k}$. Suppose we have the correspondence
\begin{align*}
\pi&\xlongleftrightarrow{\Phi}\{\sigma_1,\sigma_2,\ldots,\sigma_{2^{m-k}}\},
\end{align*}
where $\sigma_i\in\ms_{m+1,k}$ for $1\leq i\leq 2^{m-k}$.
Consider the case $n=m+1$.
Suppose $\widehat{\pi}\in\rs_{m+1}$ is obtained from $\pi$ by inserting the entry $m+1$ into $\pi$.
We distinguish three cases:
\begin{enumerate}
  \item [\rm ($i$)] If $\widehat{\pi}(m+1)=m+1$, then we insert the entry $m+2$ at the front or at the end of each $\sigma_i$.
  In this case, the obtained elements in $\Phi(\widehat{\pi})$ all have $k$ interior peaks. Therefore, we get $2\cdot 2^{m-k}=2^{m+1-k}$ elements in $\ms_{m+2,k}$.
 \item [\rm ($ii$)] If the entry $m+1$ is inserted to the position of $\pi$ with label $x_r$,
 then we insert the entry $m+2$ to one of the positions of each $\sigma_i$ with label $p_r$. In this case, $\des(\widehat{\pi})=k$ and we get $2\cdot 2^{m-k}=2^{m+1-k}$ elements in $\ms_{m+2,k}$.
 \item [\rm ($iii$)] If the entry $m+1$ is inserted to the position of $\pi$ with label $y_s$,
 then we insert the entry $m+2$ to the position of each $\sigma_i$ with label $q_s$.
 In this case, $\des(\widehat{\pi})=k+1$ and we get $2^{m-k}=2^{(m+1)-(k+1)}$ elements in $\ms_{m+2,k+1}$.
  \end{enumerate}
%After the above step, we label $\widehat{\pi}$ and these permutations in the set $\Phi(\widehat{\pi})$.
It is straightforward to show that each labeled permutation in $\Phi(\widehat{\pi})$ will be obtained exactly once in this way.
Conversely, given an element $\tau$ of $\ms_{m+2,k}$. Removing the largest entry $m+2$ of $\tau$, we can find the position of the largest entry of the corresponding
simsun permutation in $\rs_{m+1}$.
As illustrated in example~\ref{example01}, we can get an unique element of
$\rs_{m+1}$ by repeatedly removing the largest entry.
By induction, we see that $\Phi$ is the desired correspondence between $\rs_{m,k}$ and $\ms_{m+1,k}$, which also
gives a constructive proof of~\eqref{WnkSnk}.

%Here we present an example for illustration the correspondence.
\begin{ex}\label{example01}
Given $\pi=312\in\rs_{3,1}$. The correspondence between $\pi$ and $\Phi(\pi)$ is built up as
follows:
\begin{align*}
^{y_1}1~&\xlongleftrightarrow{\Phi} \{1^{q_1}2,2^{q_1}1\};\\
^{y_1}1^{y_2}2&\xlongleftrightarrow{\Phi} \{1^{q_1}2^{q_2}3,3^{q_1}1^{q_2}2,2^{q_1}1^{q_2}3,3^{q_1}2^{q_2}1\};\\
3^{x_1}1^{y_1}2~&\xlongleftrightarrow{\Phi} \{1^{p_1}4^{p_1}2^{q_1}3,3^{p_1}4^{p_1}1^{q_1}2,2^{p_1}4^{p_1}1^{q_1}3,3^{p_1}4^{p_1}2^{q_1}1\}.
%^{y_1}34^{x_1}1^{y_2}2~&\xlongleftrightarrow{\Phi} %\{1^{p_1}5^{p_1}4^{q_1}2^{q_2}3,3^{p_1}5^{p_1}4^{q_1}1^{q_2}2,2^{p_1}5^{p_1}4^{q_1}1^{q_2}3,3^{p_1}5^{p_1}4^{q_1}2^{q_2}1,\\
%     ~~~~~~~&1^{q_1}4^{p_1}5^{p_1}2^{q_2}3,3^{q_1}4^{p_1}5^{p_1}1^{q_2}2,2^{q_1}4^{p_1}5^{p_1}1^{q_2}3,3^{q_1}4^{p_1}5^{p_1}2^{q_2}1\}.
%34125~&\xlongleftrightarrow{\Phi} \{154236,354126,254136,354216, 615423,635412,625413,635421,\\
% ~~~~~~~&145236,345126,245136,345216, 614523,634512,624513,634521\}.
%(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*}
\end{ex}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Interior peaks of simsun permutations}\label{Section-3}
%\hspace*{\parindent}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Let $\rs_n^{+}=\{\pi\in\rs_n: \pi(1)>\pi(2)\}$ and $\rs_n^{-}=\{\pi\in\rs_n: \pi(1)<\pi(2)\}$.
For $\pi\in\rs_n^{+}$, we have $\lpk(\pi)=\pk(\pi)+1$. While for $\pi\in\rs_n^{-}$, we have
$\lpk(\pi)=\pk(\pi)$.

We define
\begin{align*}
P_n(x)&=\sum_{\pi\in\rs_n}x^{\pk(\pi)}=\sum_{k\geq 0} P(n,k)x^k,\\
P^{+}_n(x)&=\sum_{\pi\in\rs_n^{+}}x^{\pk(\pi)}=\sum_{k\geq 0} P^{+}(n,k)x^k, \\
P^{-}_n(x)&=\sum_{\pi\in\rs_n^{-}}x^{\pk(\pi)}=\sum_{k\geq 0} P^{-}(n,k)x^k.
\end{align*}

The following lemma is a fundamental result.
\begin{lemma}\label{lemma01}
For $n\geq 2$, we have
\begin{equation}\label{Pnk-recu01}
P^+(n+1,k)=(k+1)P^+(n,k)+(n-2k)P^+(n,k-1)+P^-(n,k),
\end{equation}
\begin{equation}\label{Pnk-recu02}
P^-(n+1,k)=(k+1)P^-(n,k)+(n-2k+1)P^-(n,k-1)+P^+(n,k-1).
\end{equation}
Equivalently,
the polynomials $P_{n}^+(x)$ and $P_{n}^-(x)$ satisfy the following recurrence relations
\begin{align*}
P_{n+1}^+(x)&=((n-2)x+1)P_{n}^+(x)+x(1-2x)\frac{d}{dx}P_{n}^+(x)+P_{n}^-(x),\\
P_{n+1}^-(x)&=((n-1)x+1)P_{n}^-(x)+x(1-2x)\frac{d}{dx}P_{n}^-(x)+xP_{n}^+(x).
\end{align*}
%for $n\geq 2$, with initial conditions $P^{+}_1(x)=P^{+}_2(x)=P^{-}_1(x)=P^{-}_2(x)=1$.
\end{lemma}
\begin{proof}
We now prove~\eqref{Pnk-recu01}.
In order to get a permutation $\pi'\in\rs_{n+1}^+$ with $k$ interior peaks from a permutation $\pi\in\rs_{n}$,
there are three ways to insert the entry $n+1$ into $\pi$:
\begin{enumerate}
\item [(a)] If $\pi\in \rs_n^+$ and $\pk(\pi)=k$, then we can insert the entry $n+1$ right after an interior peak of $\pi$ or put the entry $n+1$ at the end of $\pi$.
As we have $P^+(n,k)$ choices for $\pi$, this accounts for $(k+1)P^+(n,k)$ possibilities.
\item [(b)] If $\pi\in \rs_n^+$ and $\pk(\pi)=k-1$, then there are $n-2k$ positions could be inserted the entry $n+1$, since we cannot insert the entry $n+1$ immediately before or right after each left peak of $\pi$.
 As we have $P^+(n,k-1)$ choices for $\pi$, this accounts for $(n-2k)P^+(n,k-1)$ possibilities.
 \item [(c)] If $\pi\in \rs_n^-$ and $\pk(\pi)=k$, then we have to put the entry $n+1$ at the front of $\pi$.
 \end{enumerate}
This completes the proof of~\eqref{Pnk-recu01}. In the same way, one can prove~\eqref{Pnk-recu02}.
\end{proof}

The first few terms of the $P_n(x),P^{+}_n(x)$ and $P^{-}_n(x)$ are respectively given as follows:
\begin{align*}
P_1(x)& =1,P_2(x) =2,P_3(x)=3+2x,P_4(x)=4+12x,P_5(x)=5+44x+12x^2;\\
P^{+}_1(x)& =1,P^{+}_2(x)=1,P^{+}_3(x)=2,P^{+}_4(x)=3+4x,P^{+}_5(x)=4+22x;\\
P^{-}_1(x)& =1,P^{-}_2(x) =1,P^{-}_3(x)=1+2x,P^{-}_4(x)=1+8x,P^{-}_5(x)=1+22x+12x^2.
\end{align*}
By Lemma~\ref{lemma01}, it is easy to deduce that $$\deg P^{+}_n(x)=\lrf{{(n-2)}/{2}},~\deg P_n(x)=\deg P^{-}_n(x)=\lrf{{(n-1)}/{2}}.$$

\begin{lemma}\label{lemma02}
For $n\geq 1$, we have
\begin{equation}\label{PnkSnk01}
P^{+}(n+1,k)=(n-2k)S(n,k),~P^{-}(n+1,k)=(1+k)S(n,k).
\end{equation}
Equivalently,
\begin{equation}\label{PnkxSnkx01}
P_{n+1}^+(x)=nS_n(x)-2xS_n'(x),~P_{n+1}^-(x)=S_n(x)+xS_n'(x).
\end{equation}
\end{lemma}
\begin{proof}
We prove~\eqref{PnkSnk01} by induction. If $n=1$, the result
is obvious, so we proceed to the inductive step.
Suppose the result holds for $n=m$. For $n=m+1$, combining~\eqref{Snk-recurrence} and~\eqref{Pnk-recu01}, we have
\begin{align*}
P^{+}(m+2,k)&=(k+1)P^+(m+1,k)+(m+1-2k)P^+(m+1,k-1)+P^-(m+1,k)\\
&=(k+1)(m-2k)S(m,k)+(m+1-2k)(m+2-2k)S(m,k-1)+\\&(k+1)S(m,k)\\
&=(k+1)(m-2k)S(m,k)+(m+1-2k)(m+2-2k)S(m,k-1)+\\
&S(m+1,k)-(m+2-2k)S(m,k-1)\\
&=(m-2k)[(k+1)S(m,k)+(m+2-2k)S(m,k-1)]+S(m+1,k)\\
&=(m-2k)S(m+1,k)+S(m+1,k)\\
&=(m+1-2k)S(m+1,k).
\end{align*}
Along the same lines, one can prove $P^{-}(n+1,k)=(1+k)S(n,k)$.
\end{proof}

It is clear that $P(n,k)=P^+(n,k)+P^{-}(n,k)$ for $n\geq 2$. We can now conclude the following result from the discussion above.
\begin{theorem}
For $n\geq 1$, we have
\begin{equation}\label{PnkSnk02}
P(n+1,k)=(n+1-k)S(n,k),
\end{equation}
or equivalently,
\begin{equation}\label{PnkxSnkx02}
P_{n+1}(x)=(n+1)S_n(x)-xS_n'(x).
\end{equation}
Furthermore, we have
\begin{equation}\label{pnk-recurrence}
P(n+1,k)=\frac{(k+1)(n-k+1)}{n-k}P(n,k)+(n-2k+1)P(n,k-1)
\end{equation}
for $0\leq k\leq \lrf{n/2}$.
In particular, $P(n,0)=n$ and $P(n,1)=(n-1)(2^{n-1}-n)$ for $n\geq 1$.
\end{theorem}

It should be noted that~\eqref{pnk-recurrence} follows immediately from
~\eqref{Snk-recurrence} and~\eqref{PnkSnk02}.
%For $1\leq n\leq 7$, the numbers $P(n,k)$ can be arranged as follows with $P(n,k)$ in row $n$ and column $k$:
%$$\begin{array}{ccccc}
%  1 &  &  &  & \\
%  2 &  &  &  & \\
%  3 & 2 &  &  & \\
%  4 & 12 &  &  & \\
%  5 & 44 & 12 &  &  \\
%  6 & 130 & 136 &  & \\
%  7 & 342&900 &136&
%\end{array}$$

We now recall some notations from~\cite{gw96} concerning the zeros of polynomials.
%A polynomial $p\in\R[x]$ is {\it standard} if its leading coefficient is positive.
Let $\rz$ denote the set of real polynomials with only real zeros.
Furthermore, denote by $\rz(I)$ the set of such polynomials all of
whose zeros are in the interval $I$.
Suppose that $p,q\in\rz$,
the zeros of $p$ are $\xi_1\leqslant\cdots\leqslant\xi_n$,
and the zeros of $q$ are $\theta_1\leqslant\cdots\leqslant\theta_m$.
We say that $p$ {\it interlaces} $q$ if $\deg q=1+\deg p$ and the zeros of
$p$ and $q$ satisfy
$$
\theta_1\leqslant\xi_1\leqslant\theta_2\leqslant\cdots\leqslant\xi_n
\leqslant\theta_{n+1}.
$$
We also say that $p$ {\it alternates left of} $q$ if $\deg p=\deg q$
and the zeros of $p$ and $q$ satisfy
$$
\xi_1\leqslant\theta_1\leqslant\xi_2\leqslant\cdots\leqslant\xi_n
\leqslant\theta_n.
$$
%More generally, we say that $p$ interlaces (resp., alternates left of)
%$q$ in $I\subseteq\R$ if the zeros of $p$ and $q$ in $I$ satisfy the
%corresponding property.
%This refined notion of interlacing and alternating properties will
%make statements of results handy.
We use the notation $p\dagger q$ for ``$p$ interlaces $q$,''
$p\ll q$ for ``$p$ alternates left of $q$,'' and $p\prec q$ for
either $p\dagger q$ or $p\ll q$. For notational convenience,
let $a\prec bx+c$ for any real constants $a,b,c$.

We now recall a result on the real-rootedness of $S_n(x)$.
%Here we recall a result of~\cite{Chow11}.
\begin{lemma}[{\cite[Theorem~2.1]{Chow11}}]
For $n\geq 2$, we have $S_n(x)\in\rz(-\infty,0)$ and $S_n(x)\prec S_{n+1}(x)$.
\end{lemma}

Let $\sgn$ denote the sign function defined on $\mathbb{R}$.
\begin{theorem}
For $n\geq 2$, we have $P_n(x),P^{+}_n(x),P^{-}_n(x)\in\rz(-\infty,0)$ and
  $$P_{n+1}(x)\ll S_n(x),~ P^{+}_{n+1}(x)\prec S_n(x),~S_n(x)\ll P^{-}_{n+1}(x).$$
\end{theorem}
\begin{proof}
For $n\geq 2$, let $r_{\lrf{n/2}}<r_{\lrf{n/2}-1}<\cdots<r_2<r_1$ be the distinct zeros of $S_n(x)$.
Then by~\eqref{PnkxSnkx02}, we get $\sgn P_{n+1}(r_i)=(-1)^{i-1}$ for $i=1,2,\ldots,\lrf{n/2}$.
Hence $P_{n+1}(x)$ has precisely one zero in each of $\lrf{n/2}-1$ intervals $(r_{\lrf{n/2}},r_{\lrf{n/2}-1}),\ldots,(r_2,r_1)$.
Recall that $\deg P_{n+1}(x)=\lrf{{n}/{2}}$.
If $n=2k+1$ is odd, then $\sgn P_{n+1}(r_k)=(-1)^{k-1}$ and
$\sgn P_{n+1}(-\infty)=(-1)^k$. If $n=2k+2$ is even, then $\sgn P_{n+1}(r_{k+1})=(-1)^{k}$ and
$\sgn P_{n+1}(-\infty)=(-1)^{k+1}$. Thus $P_{n+1}(x)$ has an additional zero in the interval $(-\infty,r_{\lrf{n/2}})$.
Therefore, we have $P_{n+1}(x)\ll S_n(x)$.
Similarly, by using~\eqref{PnkxSnkx01}, one can derive $P^{+}_{n+1}(x)\prec S_n(x)$ and $S_n(x)\ll P^{-}_{n+1}(x)$.
\end{proof}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Up-down runs of simsun permutations}\label{Section-4}
%\hspace*{\parindent}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
An {\it alternating subsequence} of $\pi\in\msn$ is a subsequence $\pi(i_1),\pi(i_2),\ldots,\pi(i_k)$ satisfying
$$\pi(i_1)>\pi(i_2)<\pi(i_3)>\cdots\pi(i_k),$$
where $i_1<i_2<\cdots <i_k$. Motivated by the study of the longest increasing subsequences,
Stanley~\cite{Sta08} initiated a study of the longest alternating subsequences.
Let $\l_n(\pi)$ be the length (number of terms) of the longest alternating subsequence of a permutation $\pi\in\msn$.
%From then on, there is a rich literature devoted to the length (number of terms) of the longest alternating subsequence of permutations (see~\cite{Firro07,Pak15} for instance).
The {\it up-down runs} of a permutation $\pi$ are the alternating runs of $\pi$ endowed with a 0
in the front~(see~\cite[A186370]{Sloane}). For example, the permutation $\pi=514623$ has 4 alternating runs and 5 up-down runs.
%Clearly, the number of up-down runs of $\pi$ equals the length of the longest alternating subsequence of $\pi$.
Let $\uprun(\pi)$ be the number of up-down runs of $\pi$. It is clear that $\uprun(\pi)=\l_n(\pi)$ for $\pi\in\msn$.
We define $$T_n(x)=\sum_{\pi\in\rs_n}x^{\uprun(\pi)}=\sum_{k=1}^nT(n,k)x^k.$$
The first few terms of $T_n(x)$ are
\begin{align*}
  T_1(x) =x,~T_2(x) =x+x^2,~T_3(x)=x+2x^2+2x^3,~T_4(x)=x+3x^2+8x^3+4x^4.
 % T_5(x)&= x+4x^2+22x^3+22x^4+12x^5.
\end{align*}
\begin{theorem}
For $n\geq 1$, the numbers $T(n,k)$ satisfy the recurrence relation
\begin{equation}\label{Tnk-recu}
T(n,k)=\lrc{k/2}T(n-1,k)+T(n-1,k-1)+(n-k+1)T(n-1,k-2),
\end{equation}
with initial conditions $T(0,0)=1$ and $T(0,k)=0$ for $k>0$ or $k<0$.
\end{theorem}
\begin{proof}
There are three ways in which a permutation $\pi'\in\rs_{n}$ with $\uprun(\pi')=k$
can be obtained from a permutation $\pi\in\rs_{n-1}$ by inserting the entry $n$ into $\pi$.
\begin{enumerate}
\item [(a)] If $\uprun(\pi)=k$, then we can insert the entry $n$ right after the end of
each ascending run. This accounts for $\lrc{k/2}T(n-1,k)$ possibilities.
\item [(b)] If $\uprun(\pi)=k-1$, then we distinguish two cases: when $\pi$ ends with an
ascending run, we insert the entry $n$ to the front of the last entry of $\pi$; when $\pi$ ends with
descending run, we insert the entry $n$ at the end of $\pi$.
This gives $T(n-1,k-1)$ possibilities.
\item [(c)] If $\uprun(\pi)=k-2$,
then we can insert the entry $n$ into the remaining $n-k+1$ positions.
This gives $(n-k+1)T(n-1,k-2)$ possibilities.
\end{enumerate}
This completes the proof of~\eqref{Tnk-recu}.
\end{proof}

Note that $S(n,0)=T(n,1)=1$,
corresponding to the permutation $12\cdots n$. Recall that an element $\pi$ of $\msn$ is {\it alternating} if $\pi(1)>\pi(2)<\pi(3)>\cdots \pi(n)$. In other words, $\pi(i)<\pi({i+1})$ if $i$ is even and $\pi(i)>\pi({i+1})$ if $i$ is odd.
If $n=2m$ is even, then $S(2m,m)=T(2m,2m)$, corresponding to
the number of alternating permutations in $\rs_{2m}$. If $n=2m+1$ is odd, applying the complement operation $\phi$ to $\pi\in\rs_n$, i.e., $\phi(\pi(i))=\pi(n+1-i)$,
it is clear that $P(2m+1,m)=T(2m+1,2m+1)$ counts the number of alternating permutations in $\rs_{2m+1}$.
In general, by analyzing permutations in $\rs_n^{+}$ and $\rs_n^{-}$, it is easy to verify that
\begin{equation*}\label{SnkTnkPnk}
S(n,k)=T(n,2k)+T(n,2k+1),~P(n,k)=T(n,2k+1)+T(n,2k+2).
\end{equation*}
Equivalently, we have
\begin{equation}\label{TnxSnxPnx}
(1+x)T_n(x)=xS_n(x^2)+x^2P_n(x^2)\quad\textrm{for $n\ge 1$.}
\end{equation}

\begin{theorem}
For $n\geq 0$, we have
\begin{equation*}
T_{n+1}(x)=x(1+nx)S_n(x^2)+\frac{1}{2}x^2(1-2x)S_n'(x^2).
\end{equation*}
%and $P_n(x)\prec S_n(x)$.
\end{theorem}
\begin{proof}
It follows from~\eqref{Snx-recu},~\eqref{PnkxSnkx02} and~\eqref{TnxSnxPnx} that
\begin{align*}
 (1+x)T_{n+1}(x)&=xS_{n+1}(x^2)+x^2P_{n+1}(x^2) \\
  & =x((1+nx^2)S_n(x^2)+\frac{1}{2}x(1-2x^2)S_n'(x^2))+\\&x^2((n+1)S_n(x^2)-\frac{x}{2}S_n'(x^2))\\
  & =x(1+(n+1)x+nx^2)S_n(x^2)+\frac{1}{2}x^2(1-x-2x^2)S_n'(x^2)\\
  &=x(1+x)(1+nx)S_n(x^2)+\frac{1}{2}x^2(1+x)(1-2x)S_n'(x^2).
\end{align*}
The statement immediately follows.
\end{proof}

We call the simsun permutations discussed above to be the simsun permutations of the first kind. In the next section, we shall introduce
the simsun permutations of the second kind.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Simsun permutations of the second kind}\label{Section-5}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In this section, we always write $\pi\in\msn$ in {\it standard
cycle decomposition}, where each cycle is written with its smallest entry first and the
cycles are written in increasing order of their smallest entry.
%and that of fixed points is $\fix(\pi)=\#\{i\in [n]: \pi(i)=i\}$.
%As usual, we denote by $\cyc(\pi)$ the number of cycles of $\pi$.
%Combinatorial statistics on cycle notation have been extensively studied in
%recent years from several points of view (see, e.g.,~\cite{Bre00,Zeng12}).
%We say that $\pi$ is a circular permutation if it has only one cycle.
%Let $A=\{x_1,x_2,\ldots,x_k\}$ be a finite set of positive integers with $k\geq 1$,
%and let $\mc$ be the set of all circular permutations of $A$. We always write
%each circular permutation $w\in\mc$ by using the {\it canonical presentation} $w=(y_1,y_2,\ldots ,y_k)$, where $y_1=\min {A}$, $y_i=w^{i-1}(y_1)$ for $2\leq i\leq k$ and $y_1=w^{k}(y_1)$.
For each $\pi\in\msn$, we say that $\pi$ has an {\it excedance} at $i$ if $\pi(i)>i$.
The excedance number of $\pi$ is defined by
$\exc(\pi)=\#\{i\in [n-1]: \pi(i)>i\}$.
%MacMahon~\cite[vol I, p.~186]{MacMahon1915} observed that
%\begin{equation*}\label{des-exc}
%\#\{\pi\in\msn: \des(\pi)=k\}=\#\{\pi\in\msn: \exc(\pi)=k\}\quad\textrm{for $0\leq k<n$}.
%\end{equation*}
%The classical Eulerian polynomials are defined by
%$$A_n(x)=\sum_{\pi\in\msn}x^{\des(\pi)}=\sum_{\pi\in\msn}x^{\exc(\pi)}.$$
%Any permutation statistic that is equidistributed with $\des$ and $\exc$ is said to be an
%Eulerian statistic. The Eulerian statistics have been extensively studied (see, e.g.,~\cite{Bona12,Branden06,Bre94}).
Following~\cite{Zeng12}, for $\pi\in\msn$, a value $x=\pi(i)$ is called a {\it double excedance} if
$i=\pi^{-1}(x)<x<\pi(x)$, and we say that $x=\pi(i)$ is a {\it cyclic peak} if $i=\pi^{-1}(x)<x>\pi(x)$.
Let $\cpk(\pi)$ denote the number of cyclic peaks of $\pi$.

\begin{definition}
We say that $\pi\in\msn$ is a {\it simsun permutation of the second kind} if for all $k\in [n]$,
after removing the $k$ largest letters of $\pi$, the resulting permutation has no double excedances.
\end{definition}

For example, $(1,5,3,4)(2)$ is not a simsun permutation of the second kind since when we remove the letter 5,
the resulting permutation $(1,3,4)(2)$ contains a double excedance.
Let $\rss_n$ be the set of the simsun permutations of the second kind of length $n$.
It is clear that $\exc(\pi)=\cpk(\pi)$ for $\pi\in\rss_n$.
We say that $\pi(i)$ is a {\it right-to-left minimum} of $\pi$ if $\pi(i)<\pi(j)$ for $j>i$.
Let $\rmin$ denote the number of right-to-left minima of $\pi$. Let $\cyc(\pi)$ be the number of cycles of $\pi$.

In the following, we shall present a constructive proof of the following identity:
\begin{equation}\label{des-exc}
|\{\pi\in\rs_n:\des(\pi)=k,\rmin(\pi)=\ell)\}|=|\{\pi\in\rss_n:\exc(\pi)=k,\cyc(\pi)=\ell)\}|.
\end{equation}
%\begin{equation}\label{des-exc}
%\sum_{\pi\in\rs_n}x^{\des(\pi)}=\sum_{\pi\in\rss_n}x^{\exc(\pi)}.
%\end{equation}

Let $\rss_{n,k}=\{\pi\in\rss_n \mid \exc(\pi)=k\}$.
As a variant of Definition~\ref{def01},
we introduce a definition of the {\it labeled simsun permutations of the second kind}.
\begin{definition}
Let $\sigma\in\rss_{n,k}$.
Suppose $i_1<i_2<\cdots<i_k$ are the excedances of $\sigma$. Then we put the superscript labels $u_r$
right after $i_{r}$, where $1\leq r\leq k$.
In the remaining positions
except the first position of each cycle and the positions right after $\sigma(i_r)$, we put the superscript labels $v_1,v_2,\ldots,v_{n-2k}$
from left to right.
\end{definition}

As an example, for $\sigma=(1,3)(2,4)(5)\in \rss_{5,2}$, the labeling of $\sigma$ is $(1^{u_1}3)(2^{u_2}4)(5^{v_1})$.

Now we start to construct a bijection, denoted by $\Psi$, between $\rs_{n,k}$ and $\rss_{n,k}$.
When $n=1$, we have $\rs_{1,0}=\{^{y_1}1\}$. Set $\Psi(^{y_1}1)=(1^{v_1})$.
This gives a bijection between $\rs_{1,0}$ and $\rss_{1,0}$.
Let $n=m$. Suppose $\Psi$ is a bijection between $\rs_{m,k}$ and $\rss_{m,k}$ for all $k$.
%Consider the case$n=m+1$.
Given $\pi\in\rs_{m,k}$. Suppose $\Psi(\pi)=\sigma$. Consider the following three cases:
\begin{enumerate}
  \item [\rm ($i$)] If $\widehat{\pi}$ is obtained from $\pi$ by inserting the entry $m+1$ to the position of $\pi$ with label $x_r$, then we insert the entry $m+1$ to $\sigma$ with label $u_r$.
In this case, $\des(\widehat{\pi})=\exc(\Psi(\widehat{\pi}))=k$. Hence $\widehat{\pi}\in\rs_{m+1,k}$ and $\Psi(\widehat{\pi})\in\rss_{m+1,k}$.
 \item [\rm ($ii$)] If $\widehat{\pi}$ is obtained from $\pi$ by inserting the entry $m+1$ to the position of $\pi$ with label $y_r$, then we insert $m+1$ to $\sigma$ with label $v_r$.
In this case, $\des(\widehat{\pi})=\exc(\Psi(\widehat{\pi}))=k+1$. Hence $\widehat{\pi}\in\rs_{m+1,k+1}$ and $\Psi(\widehat{\pi})\in\rss_{m+1,k+1}$.
 \item [\rm ($iii$)] If $\widehat{\pi}$ is obtained from $\pi$ by inserting the entry $m+1$ at the end of $\pi$, then we append $(m+1)$ to $\sigma$ as a new cycle. Hence $\widehat{\pi}\in\rs_{m+1,k}$ and $\Psi(\widehat{\pi})\in\rss_{m+1,k}$. From this case, we see that $\rmin(\widehat{\pi})=\rmin(\pi)+1$ if and only if $\cyc(\Psi(\widehat{\pi}))=\cyc(\sigma)+1$.
\end{enumerate}
By induction, we see that $\Psi$ is the desired bijection between $\rs_{m,k}$ and $\rss_{m,k}$ for all $k$,
which also gives a constructive proof of~\eqref{des-exc}.

\begin{ex}
Given $\pi=3412\in\rs_{4,1}$.
The correspondence between $\pi$ and $\Psi(\pi)$ is built up as follows:
\begin{align*}
^{y_1}1&\Leftrightarrow (1^{v_1});\\
^{y_1}1^{y_2}2&\Leftrightarrow (1^{v_1})(2^{v_2});\\
3^{x_1}1^{y_1}2&\Leftrightarrow (1^{u_1}3)(2^{v_1});\\
^{y_1}34^{x_1}1^{y_2}2&\Leftrightarrow (1^{u_1}43^{v_1})(2^{v_2}).
%-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}

%\begin{theorem}
%For any $1\leq k\leq \lrf{n/2}$, we have
%\begin{equation}
%\#\{\pi\in\rs_n: \des(\pi)=k\}=\#\{\pi\in\rss_n: \exc(\pi)=k\}.
%\end{equation}
%Equivalently,
%$$\sum_{\pi\in\rs_n}x^{\des(\pi)}=\sum_{\pi\in\rss_n}x^{\exc(\pi)}.$$
%\end{theorem}
%The number of fixed points of $\pi$ is $\fix(\pi)=\#\{i\in [n]: \pi(i)=i\}$.
%As usual, we denote the number of cycles of $\pi$ by $\cyc(\pi)$.
Consider the following enumerative polynomials
$$S_n(x,q)=\sum_{\pi\in\rss_n}x^{\exc(\pi)}q^{\cyc(\pi)}.$$
Let $S=S(x,q;z)=\sum_{n\geq0}S_n(x,q)\frac{z^n}{n!}$. We now present the main result of this section.

\begin{theorem}\label{thm13}
The polynomials $S_n(x,q)$ satisfy the recurrence relation
\begin{equation}\label{Snxq-recu}
S_{n+1}(x,q)=(q+nx)S_n(x,q)+x(1-2x)\frac{\partial}{\partial x}(S_n(x,q)),
\end{equation}
with the initial condition $S_0(x,q)=1$. Furthermore,
\begin{equation}\label{Sxzq}
S(x,q;z)=RS^q(x,z).
\end{equation}
\end{theorem}
\begin{proof}
Let $n$ be a fixed positive integer and given $\sigma\in\rss_n$.
Let $\sigma_i$ be an element of $\rss_{n+1}$ obtained from $\sigma$ by inserting the entry
$n+1$, in the standard cycle decomposition of $\sigma$, right after $i$ if
$i$ is not a cyclic peak of $\sigma$ and $i\in [n]$ or as a new cycle $(n+1)$ if $i=n+1$.
It is clear that
$$ \cyc(\sigma_i)=\left\{
              \begin{array}{ll}
                \cyc(\sigma), & \hbox{if $i\in [n]$;} \\
                \cyc(\sigma)+1, & \hbox{if $i=n+1$.}
              \end{array}
            \right.
$$
Therefore, we have
\begin{align*}
S_{n+1}(x,q)&=\Sigma_{\pi\in\rss_{n+1}}x^{\exc(\pi)}q^{\cyc(\pi)}\\
  &=\Sigma_{i=1}^{n+1}\Sigma_{\sigma\in\rss_{n}}x^{\exc(\sigma_i)}q^{\cyc(\sigma_i)}\\
  &=\Sigma_{\sigma\in\rss_{n}}x^{\exc(\sigma)}q^{\cyc(\sigma)+1}+
\Sigma_{i=1}^{n}\Sigma_{\sigma\in\rss_{n}}x^{\exc(\sigma_i)}q^{\cyc(\sigma)}\\
  &=qS_n(x,q)+\Sigma_{\sigma\in\rss_{n}}(\exc(\sigma)x^{\exc(\sigma)}+(n-2\exc(\sigma))x^{\exc(\sigma)+1})q^{\cyc(\sigma)}\\
  &=qS_n(x,q)+nxS_n(x,q)+\Sigma_{\pi\in\rss_n}(1-2x)\exc(\sigma)x^{\exc(\sigma)}q^{\cyc(\sigma)},\\
\end{align*}
and~\eqref{Snxq-recu} follows.
By rewriting~\eqref{Snxq-recu} in terms of the generating function $S$, we have
\begin{equation}\label{Sxz-pde}
(1-xz)S_z=qS+x(1-2x)S_x.
\end{equation}
It is routine to check that the generating function
$\widetilde{S}=\widetilde{S}(x,q;z)=RS^q(x,z)$
satisfies~\eqref{Sxz-pde}. Also, this generating function gives $\widetilde{S}(x,q;0)=1,\widetilde{S}(x,0;z)=1$
and $\widetilde{S}(0,q;z)=e^{qz}$. Hence $S=\widetilde{S}$.
\end{proof}

Combining~\eqref{Snxq-recu} and~\cite[Theorem 2]{Ma08}, we get the following corollary.
\begin{cor}
If $q> 0$, then $S_n(x,q)$ has nonpositive and simple zeros for $n\geq 2$.
\end{cor}
%\begin{equation}
%\sum_{n\geq0}S_n(x,y,q)\frac{z^n}{n!}=e^{qz(y-1)}S(x,z)^q.
%\end{equation}
Using~\eqref{Sxzq}, it is easy to verify that
$$S(1,q;z)=\frac{1}{(1-\sin z)^q}.$$
and for $n\geq 1$, we have
$$S_{n}(x,-1)=\left\{
               \begin{array}{ll}
                 (1-x)(1-2x)^{m-1}, & \hbox{if $n=2m$;} \\
                 -(1-2x)^m, & \hbox{if $n=2m+1$.}
               \end{array}
             \right.$$

A cycle $(b(1),b(2),\ldots)$ is said to be up-down if
it satisfies $b(1)<b(2)>b(3)<\cdots$, where $b_1$ is the smallest element of this cycle.
We say that a permutation $\pi$ is {\it cycle-up-down} if it is a product
of up-down cycles.
Let $\triangle_n$ be the set of cycle-up-down permutations in $\msn$.
Deutsch and Elizalde~\cite[p.~193]{Deutsch11} discovered that
$$\sum_{n\geq 0}\sum_{\pi\in\triangle_n}q^{\cyc(\pi)}\frac{z^n}{n!}=S(1,q;z).$$
Therefore, we have
$$\sum_{\pi\in\rss_n}q^{\cyc(\pi)}=\sum_{\pi\in\triangle_n}q^{\cyc(\pi)}.$$

Let $\fix(\pi)$ be the number of {\it fixed points} of $\pi$, i.e., $\fix(\pi)=|\{i\in [n]: \pi(i)=i\}|$.
Define $$F_n(x,y,q)=\sum_{\pi\in\rss_n}x^{\exc(\pi)}y^{\fix(\pi)}q^{\cyc(\pi)}.$$
Note that
\begin{align*}
F_{n}(x,y,q)&=\sum_{i=0}^n\binom{n}{i}(yq-q)^i\sum_{\pi\in\rss_{n-i}}x^{\exc(\pi)}q^{\cyc(\pi)}\\
            &=\sum_{i=0}^n\binom{n}{i}(yq-q)^iS_{n-i}(x,q).
\end{align*}
Using~\eqref{Sxzq}, we obtain
\begin{equation*}\label{Snxyqz-exp}
\sum_{n\geq 0}F_n(x,y,q)\frac{z^n}{n!}=e^{qz(y-1)}RS^q(x,z).
\end{equation*}
%A fixed-point-free permutation is called a {\it derangement}. Let $\DS_n$ denote the set of derangements in $\rss_n$.
%We define
%\begin{align*}
%DS_n(x,q)&=\sum_{\pi\in\DS_n}x^{\exc(\pi)}q^{cyc(\pi)}\\
%DS(x,q;z)&=\sum_{n\geq 0}DS_n(x,q)\frac{z^n}{n!}.
%\end{align*}
%%It follows from~\eqref{Snxyqz-exp} that
%\begin{equation}\label{Dxqz-exp}
%DS(x,q;z)=e^{-qz}S(x,z)^q.
%\end{equation}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Concluding remarks}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
In this paper we study the peak statistics on simsum permutations.
It is well known that the descent statistic is equidistributed over $n$-simsun permutations and
$n$-Andr\'e permutations~(see~\cite{Chow11}), and there are bijections between simsun permutations and
increasing 1-2 trees~(see~\cite{Chuang12} for instance).
Therefore, one can find corresponding results on Andr\'e permutations and increasing 1-2 trees.
For example, $S(1,q;z)$ also is the (shifted) exponential generating function that counts Andr\'e permutations with
respect to the size and the number of right-to-left minima (see~\cite[Proposition~1]{Disanto14}).
Furthermore, it would be interesting to derive similar results on signed simsum permutations
introduced by Ehrenborg and Readdy~\cite{Ehrenborg98}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgements}
The authors thank the referees for their valuable suggestions which lead to a substantial improvement of the paper.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{thebibliography}{26}
\bibitem{Andre84}
D. Andr\'e. \newblock \'Etude sur les maxima, minima et s\'equences des permutations.
\newblock {\em  Ann. Sci. \'Ecole Norm. Sup.}, 3(1):121--135, 1884.

\bibitem{Billey13}
S. Billey, K. Burdzy, B.E. Sagan. \newblock Permutations with given peak set. \newblock {\em J. Integer Seq.}, 16: Article 13.6.1, 2013.



\bibitem{Branden11}
P. Br\"and\'en and A. Claesson. \newblock Mesh patterns and the expansion of permutation statistics as
sums of permutation patterns. \newblock {\em  Electron. J. Combin.}, 18(2): \#P5, 2011.



\bibitem{Chen11}
W.Y.C. Chen, N.J.Y. Fan, J.Y.T. Jia. \newblock Labeled ballot paths and the Springer numbers.
\newblock {\em SIAM J. Discrete Math.}, 25:1530--1546, 2011.


\bibitem{Chow11}
C-O. Chow, W. C. Shiu. \newblock Counting simsun permutations by descents. \newblock {\em Ann. Comb.}, 15:625--635, 2011.

\bibitem{Chuang12}
W.-C. Chuang, S.-P. Eu, T.-S. Fu, Y.-J. Pan. \newblock On simsun and double simsun permutations avoiding a pattern of length three.
\newblock {\em Fund. Inform.}, 117:155--177, 2012.


\bibitem{Deutsch11}
E. Deutsch and S. Elizalde. \newblock Cycle-up-down permutations. \newblock {\em Australas. J. Combin.}, 50:187--199, 2011.

\bibitem{Deutsch12}
E. Deutsch, S. Elizalde. \newblock Restricted simsun permutations.
\newblock {\em Ann. Combin.}, 16(2):253--269, 2012.

\bibitem{Disanto14}
F. Disanto. \newblock Andr\'e permutations, right-to-left and left-to-right minima.
\newblock {\em S\'eminaire Lothar. Combin.}, 70:Article B70f, 2014.



\bibitem{Ehrenborg98}
R. Ehrenborg, M. Readdy. \newblock Coproducts and the cd-index. \newblock {\em J. Algebraic Combin.}, 8:273--299, 1998.


\bibitem{Eu14}
S.-P. Eu, T.-S. Fu, Y.-J. Pan. \newblock A refined sign-balance of simsun permutations.
\newblock {\em European J. Combin.}, 36:97--109, 2014.

\bibitem{Foata73}
D. Foata and M.P. Sch\"utzenberger. \newblock {\em Nombres d'Euler et permutations alternantes}, in \newblock {A Survey of Combinatorial
Theory}, J.N. Srivastava et al. (Eds.), Amsterdam, North-Holland, pages 173--187, 1973.

\bibitem{Foata01}
D. Foata, G.-N. Han. \newblock Arbres minimax et polyn\^{o}mes d'Andr\'e. \newblock {\em Adv. in Appl. Math.}, 27:367--389, 2001.



\bibitem{gw96}
J.~Garloff, D.G.~Wagner. \newblock Hadamard products of stable polynomials are stable. \newblock {\em J. Math. Anal. Appl.}, 202:797--809, 1996.


\bibitem{Hetyei98}
G. Hetyei, E. Reiner. \newblock Permutation trees and variation statistics. \newblock {\em European J. Combin.}, 19:847--866, 1998.

\bibitem{Ma121}
S.-M. Ma. \newblock Derivative polynomials and enumeration of permutations by number of interior and left peaks.
\newblock {\em Discrete Math.}, 312:405--412, 2012.

\bibitem{Ma122}
S.-M. Ma. \newblock An explicit formula for the number of permutations with a given number of alternating runs. \newblock {\em J. Combin. Theory Ser. A}, 119:1660--1664, 2012.

\bibitem{Ma123}
S.-M. Ma. \newblock Enumeration of permutations by number of alternating runs. \newblock {\em Discrete Math.}, 313:1816--1822, 2013.

\bibitem{Ma08}
S.-M. Ma, Y. Wang. \newblock $q$-Eulerian polynomials and polynomials with only real zeros. \newblock {\em Electron. J. Combin.}, 15:R17, 2008.

\bibitem{Zeng12}
H. Shin, J. Zeng. \newblock The symmetric and unimodal expansion of Eulerian polynomials via continued fractions. \newblock {\em European J. Combin.} 33:111--127, 2012.


\bibitem{Sloane}
N.J.A. Sloane. \newblock {\em The On-Line Encyclopedia of Integer Sequences},
published electronically at
http://oeis.org, 2010.

\bibitem{Springer}
T.A. Springer. \newblock Remarks on a combinatorial problem. \newblock {\em Nieuw Arch. Wisk.}, 19:30--36, 1971.

\bibitem{Sta08}
R.P. Stanley. \newblock Longest alternating subsequences of permutations.
\newblock {\em Michigan Math. J.}, 57:675--687, 2008.

\bibitem{Sundaram1994}
S. Sundaram. \newblock The homology representations of the symmetric group on Cohen-Macaulay subposets of the partition lattice. \newblock {\em Adv. Math.}, 104(2):225--296, 1994.

\bibitem{Sundaram1995}
S. Sundaram. \newblock The homology of partitions with an even number of blocks. \newblock {\em J. Algebraic Combin.}, 4:69--92, 1995.

\bibitem{Sundaram1996}
S. Sundaram. \newblock Plethysm, partitions with an even number of blocks and Euler numbers. DIMACS Series
in Discrete Mathematics and Theoretical Computer Science 24, (Billera, Greene, Simion,
Stanley, eds.), \newblock {\em Amer. Math. Soc.}, 171--198, 1996.

\end{thebibliography}
\end{document}
