<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[finalversion]{FPSAC2023}
\articlenumber{2}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{enumitem,shuffle}
\usepackage{tikz,color}
\usepackage{ifthen}
\usetikzlibrary{patterns,shapes,arrows,decorations.pathreplacing}
\tikzstyle{pnt}=[draw,ellipse,fill,inner sep=1pt]

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}  
\newtheorem{problem}[theorem]{Problem}  
\newtheorem{question}[theorem]{Question}  

\theoremstyle{definition}
\newtheorem{example}[theorem]{Example}  
\newtheorem{definition}[theorem]{Definition}   

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}  


\newcommand{\Q}{\mathcal{Q}}
\newcommand{\QQ}{\overline{\mathcal{Q}}}
\newcommand{\C}{\mathcal{C}} 
\newcommand{\A}{\mathcal{A}} 
\newcommand{\B}{\mathcal{B}} 
\newcommand{\M}{\mathcal{M}}
\newcommand{\D}{\mathcal{D}}
\renewcommand{\S}{\mathcal{S}}
\newcommand{\la}{\lambda}
\newcommand{\si}{\sigma}
\newcommand{\bij}{\varphi}
\newcommand{\nI}{\overline{I}}
\DeclareMathOperator\des{des}
\DeclareMathOperator\Des{Des}
\DeclareMathOperator\plat{plat}
\DeclareMathOperator\wdes{wdes}
\DeclareMathOperator\pea{pea}
\DeclareMathOperator\lpea{lpea}
\DeclareMathOperator\hpea{hpea}
\newcommand\LK{\hat{\kappa}}
\newcommand\LKC{\kappa}
\DeclareMathOperator\mat{mat}
\DeclareMathOperator\SYT{SYT}
\newcommand\id{\iota}
\newcommand\row{r}
\newcommand{\poly}{C}
\newcommand{\Cat}{\mathrm{Cat}}
\newcommand{\card}[1]{{\lvert #1 \rvert}}
\newcommand{\delete}[1]{}
\newcommand\nn{[n]\sqcup[n]}
\newcommand\uu{\texttt{u}}
\newcommand\dd{\texttt{d}}
\newcommand\nnk{\bigsqcup^k[n]}
\newcommand\hf{\hat{f}}
\newcommand\hfk{\hat{f}_k}
\newcommand\hg{\hat{g}}
\newcommand\hphi{\hat{\phi}}
\newcommand\N{\texttt{n}}
\newcommand\E{\texttt{e}}
\newcommand\ba{\textcolor{red}{|}}
\newcommand\ol{\overline}
\newcommand\s{s}
\newcommand\dy{d}

\newcommand\grid[1]{
 \draw (0,0) -- (#1,0) -- (#1,#1) -- (0,0);
 \foreach \x in {1,...,#1} {
        \draw[thin,dotted] (\x,0) -- (\x,\x) -- (#1,\x);
      }
}

\newcommand\doublegrid[1]{
 \draw[thin,dotted] (0,0) grid (#1,#1);
 \draw (0,0) rectangle (#1,#1);
 \draw (0,0)--(#1,#1); 
}

\newcommand\labelgrid[1]{
	\foreach [evaluate={\x =\sig[\i]}] \i in {1,...,#1} {
    	\draw (\i-.5,0) node[below] {\x};
		\draw (#1,\i-.5) node[right] {\x};
	}
}

\newcommand\labelgridDes[1]{
    \labelgrid{#1}
    \foreach [evaluate={\x =\sig[\i]},evaluate={\xx =\sig[\i-1]}] \i in {1,...,#1} {
    	\ifthenelse{\xx&gt;\x} {\draw[red] (\i-1,-.2)--(\i-1,-.8); 
    	                     \draw[red] (#1+.2,\i-1)--(#1+.8,\i-1);}
	}
}

\newcommand\Desdots[1]{
    \foreach \i in #1 {
        \draw[thick,red] (\i-.3,\i)--(\i+.3,\i);
        \draw[thick,red] (\i,\i-.3)--(\i,\i+.3);
        }
}

\newcommand\decorategrid[1]{
	\foreach [evaluate={\x =\sig[\i]},evaluate={\xx =\sig[\i-1]}] \i in {2,...,#1} {
    	\ifthenelse{\x&lt;\xx}{\draw[red] (\i-1,0) -- (\i-1,\i-1) -- (#1,\i-1);}{};
	}
	\foreach [evaluate={\x =\sig[\i]},evaluate={\ii=\i-1}] \i in {2,...,#1} {
		\foreach [evaluate={\y =\sig[\j]}] \j in {1,...,\ii} {
			\ifthenelse{\x&lt;\y}{\draw[red] (\i-1,\j) -- ++(.3,-.3);}{\draw[red] (\i,\j-1) -- ++(-.3,.3);};
		}
	}
}

\def\e{-- ++(1,0)}
\def\n{-- ++(0,1)}

\newcommand\gle[3]{
\draw (#1,#2) node[scale=.8] {#3};
}

\newcommand\ord[3]{
\draw[darkgray] (#1-.5,#2-.5) node[scale=.8] {{\texttt #3}};
}

\newcommand\arc[2]{ \draw[blue,very thick] (#1)  to [bend left=45] (#2);}
\newcommand\rect{\, \begin{tikzpicture}[scale=.25]
      \draw (0,0) rectangle (2,1);
\end{tikzpicture}\, 
}

%% define your title in the usual way
\title{The distribution of descents on nonnesting permutations}

%% define your authors in the usual way
%% use \addressmark{1}, \addressmark{2} etc for the institutions, and use \thanks{} for contact details
\author{Sergi Elizalde\thanks{\href{mailto:sergi.elizalde@dartmouth.edu}{sergi.elizalde@dartmouth.edu}}\addressmark{1}}

%% then use \addressmark to match authors to institutions here
\address{\addressmark{1}Department of Mathematics, Dartmouth College, Hanover, NH 03755}

%% put the date of submission here
\received{\today}

%% leave this blank until submitting a revised version
%\revised{}

%% put your English abstract here, or comment this out if you don't have one yet
%% please don't use custom commands in your abstract / resume, as these will be displayed online
%% likewise for citations -- please don't use \cite, and instead write out your citation as something like (author year)
\abstract{
Motivated by recent results about descents on Stirling and quasi-Stirling permutations, we consider permutations of the multiset $\{1,1,2,2,\dots,n,n\}$ that avoid the patterns $1221$ and $2112$. We call these nonnesting permutations, as they can be viewed as nonnesting matchings with labeled arcs.
We show that the polynomial describing the distribution of the number of descents is a product of an Eulerian polynomial and a Narayana polynomial. It follows that, rather unexpectedly, this polynomial is palindromic. We provide bijective proofs of these facts by composing various transformations on Dyck paths, including the Lalanne--Kreweras involution.}

%% put your French abstract here, or comment this out if you don't have one
%\resume{\lipsum[2]}

%% put your keywords here, or comment this out if you don't have them yet
\keywords{nonnesting, quasi-Stirling, canon permutation, Dyck path, Narayana}

%% you can include your bibliography however you want, but using an external .bib file is STRONGLY RECOMMENDED and will make the editor's life much easier
%% regardless of how you do it, please use numerical citations; i.e., [xx, yy] in the text

%% this sample uses biblatex, which (among other things) takes care of URLs in a more flexible way than bibtex
%% but you can use bibtex if you want
\usepackage[backend=bibtex]{biblatex}
\addbibresource{nonnesting_multiperm-fpsac-revised.bib}
%% note the \printbibliography command at the end of the file which goes with these biblatex commands


\begin{document}
\maketitle
%% note that you DO NOT have to put your abstract here -- it is generated by \maketitle and the \abstract and \resume commands above


\section{Introduction}

\subsection{Permutations of multisets and descents}

Given a sequence of positive integers $\pi=\pi_1\pi_2\dots\pi_m$, we say that $i$ is a {\em descent} of $\pi$ if $\pi_i&gt;\pi_{i+1}$, 
that it is a {\em plateau} if $\pi_i=\pi_{i+1}$, and that it is a {\em weak descent} if $\pi_i\ge\pi_{i+1}$.
Denote by $\des(\pi)$, $\plat(\pi)$ and $\wdes(\pi)=\des(\pi)+\plat(\pi)$ the number of descents, plateaus and weak descents of $\pi$, respectively. 

The distribution of descents on the set $\S_n$  of permutations of $[n]:=\{1,2,\dots,n\}$ is given by the Eulerian polynomials 
$$A_n(t)=\sum_{\sigma\in\S_n} t^{\des(\sigma)},$$
whose generating function is 
\begin{equation}
\label{eq:EulerianGF}
A(t,z)=\sum_{n\ge0} A_n(t) \frac{z^n}{n!}=\frac{t-1}{t-e^{(t-1)z}}.
\end{equation}
Note that the Eulerian polynomials are palindromic, in the sense that 
\begin{equation}\label{eq:Apali}
A_n(t)=t^{n-1}A_n(1/t),
\end{equation}
since
\begin{equation}\label{eq:desRsi}
\des(\sigma^R)=n-1-\des(\sigma),
\end{equation}
where $\sigma^R=\sigma_n\sigma_{n-1}\dots\sigma_1$ denotes the reversal of $\sigma$.

In 1978, Gessel and Stanley~\cite{gessel_stirling_1978} introduced {\em Stirling permutations}, defined as permutations $\pi_1\pi_2\dots\pi_{2n}$ of the multiset $\nn:=\{1,1,2,2,\dots,n,n\}$ satisfying that, if $i&lt;j&lt;k$ and $\pi_i=\pi_k$, then $\pi_j&gt;\pi_i$. In pattern avoidance terminology, this condition is equivalent to avoiding the pattern $212$. They showed that the distribution of the number of descents on such permutations is related to the Stirling numbers of the second kind. There is an extensive literature on these permutations and their generalizations to other multisets.

In 2019, Archer et al.~\cite{archer_pattern_2019} introduced a variation of Stirling permutations, which they call {\em quasi-Stirling permutations}.
These are permutations $\pi_1\pi_2\dots\pi_{2n}$ of  $\nn$ that avoid  $1212$ and $2121$, meaning that there do not exist $i&lt;j&lt;\ell&lt;m$ such that $\pi_i=\pi_\ell$ and $\pi_j=\pi_m$. The number of such permutations is $n!\,\Cat_n=\frac{(2n)!}{(n+1)!}$, where $\Cat_n$ is the $n$th Catalan number. The generating function for these permutations with respect to the number of descents and plateaus was later found in~\cite{elizalde_descents_2021}.

\begin{theorem}[\cite{elizalde_descents_2021}]
Denote by $\QQ_n$ the set of quasi-Stirling permutations of $\nn$, and let
$$\overline{Q}(t,u,z)=
\sum_{n\ge0} \sum_{\pi\in\QQ_n} t^{\des(\pi)}u^{\plat(\pi)} \frac{z^n}{n!}.
$$
Then this generating function satisfies the implicit equation
$$\overline{Q}(t,u,z)=A(t,z(t\overline{Q}(t,u,z)-t+u)),$$
%\frac{t-1}{t-e^{(t-1)z(t\overline{Q}(t,u,z)-t+u)}}.$$
where $A(t,z)$ is given by Equation~\eqref{eq:EulerianGF}.
\end{theorem}
In particular, it is shown that the number of $\pi\in\QQ_n$ with $n-1$ descents is equal to $(n+1)^{n-1}$.
Further generalizations of these results to multisets with an arbitrary number of copies of each element have recently been obtained by Yan et al.~\cite{yan_statistics_2021}%,yan_partial_2022} 
and by Fu and Li~\cite{fu_rooted_2022}.

\subsection{Nonnesting permutations}

A permutation $\pi$ of $\nn$ can be viewed as a labeled matching of $[2n]$, by placing an arc with label $k$ between $i$ with $j$ if $\pi_i=\pi_j=k$. The condition that $\pi$ avoids $1212$ and $2121$ is equivalent to the fact that this matching is {\em noncrossing}; see 
\cite[Exer.\ 60]{stanley_catalan_2015}. With this perspective, it is natural to also consider permutations
for which this matching is {\em nonnesting}; see \cite[Exer.\ 64]{stanley_catalan_2015}.

\begin{figure}[h]
\centering
  \begin{tikzpicture}[scale=0.6]
   \foreach [count=\i] \j in {4,4,3,1,1,5,2,2,5,3}
        \node[pnt,label=below:$\j$] at (\i,0)(\i) {};
   \arc{1}{2} \arc{3}{10} \arc{4}{5} \arc{6}{9} \arc{7}{8}
   
  \begin{scope}[shift={(13,0)}]
   \foreach [count=\i] \j in {3,5,3,2,5,2,1,4,1,4}
        \node[pnt,label=below:$\j$] at (\i,0)(\i) {};
   \arc{1}{3} \arc{2}{5} \arc{4}{6} \arc{7}{9} \arc{8}{10}
   \end{scope}
   \end{tikzpicture}
\caption{The matchings corresponding to the quasi-Stirling (noncrossing) permutation $4431152253$ and the nonnesting permutation $3532521414\in\C_5$.}
\label{fig:matching}
\end{figure}

\begin{definition}\label{def:nonnesting}
A permutation $\pi$ of the multiset $\nn$ is called {\em nonnesting} if it avoids the patterns $1221$ and $2112$; equivalently, if there do not exist $i&lt;j&lt;\ell&lt;m$ such that $\pi_i=\pi_m$ and $\pi_j=\pi_\ell$.
Denote by $\C_n$ the set of nonnesting permutations of $\nn$.
\end{definition}

The above condition on $\pi$ is equivalent to the requirement that the subsequence of $\pi$ determined by the first copy of each entry coincides with the subsequence determined by the second copy of each entry. This subsequence, which is a permutation in $\S_n$, will be denoted by $\s(\pi)$.
For example, if $\pi=3532521414\in\C_5$, then $\s(\pi)=35214\in\S_5$.

As in the noncrossing case, the number of nonnesting matchings of $[2n]$ is again the $n$th Catalan number \cite[Exer.\ 64]{stanley_catalan_2015}. Since there are $n!$ ways to assign labels to the arcs of a nonnesting matching to form a nonnesting permutation, it follows that
$$
|\C_n|=n!\,\Cat_n=\frac{(2n)!}{(n+1)!}.
$$

Motivated by the results on the distribution of the number of descents and plateaus on Stirling and quasi-Stirling permutations, here we  describe the distribution of these statistics on nonnesting permutations. We are interested in the polynomial
\begin{equation}\label{eq:polydef}
\poly_n(t,u)=\sum_{\pi\in\C_n} t^{\des(\pi)}u^{\plat(\pi)}.
\end{equation}

\subsection{Dyck paths and Narayana numbers}\label{sec:Narayana}

Let $\D_n$ be the set of lattice paths from $(0,0)$ to $(2n,0)$ with steps $\uu=(1,1)$ and $\dd=(1,-1)$ that do not go below the $x$-axis. Elements of $\D_n$ are called Dyck paths. A {\em peak} in a Dyck path is an occurrence of two adjacent steps $\uu\dd$. A peak is called a {\em low peak}  if these steps touch the $x$-axis, and a {\em high peak} otherwise. Denote the number of low peaks and the number of high peaks of $D\in\D_n$ by $\lpea(D)$ and $\hpea(D)$, respectively. Sometimes it will be convenient to instead draw Dyck paths with steps $\E=(1,0)$ and $\N=(0,1)$ playing the role of $\uu$ and $\dd$, respectively. Consider the {\em Narayana polynomials} $$N_n(t,u)=\sum_{D\in\D_n}t^{\hpea(D)}u^{\lpea(D)}.$$
From the usual decomposition of Dyck paths by the first return, one can deduce that
$$\sum_{n\ge0}N_n(t,u)z^n=\frac{2}{1+(1+t-2u)z+\sqrt{1-2(1+t)z+(1-t)^2z^2}}.$$

A consequence of the above expression is that, for $n\ge1$,
\begin{equation}\label{eq:Nt1Ntt} tN_n(t,1)=N_n(t,t),\end{equation} 
that is, the number of paths in $\D_n$ with $r-1$ high peaks equals the number of those with $r$ peaks, for all $r\in[n]$.
A bijective proof of this fact was given by Deutsch~\cite{deutsch_bijection_1998}. Another simple bijection $\rho:\D_n\to\D_n$ with the property that $\hpea(D)=\pea(\rho(D))-1$
is obtained by applying the inverse of the {\em rowmotion} map on order ideals of the poset of positive roots in type A; see~\cite{striker_promotion_2012} for details.

An interesting property of the polynomial~\eqref{eq:Nt1Ntt} is that it is palindromic, i.e., 
\begin{equation}\label{eq:Nttpali}
N(t,t)=t^{n+1}N(1/t,1/t);
\end{equation}
equivalently, the number of paths in $\D_n$ with $r$ peaks equals the number of those with $n+1-r$ peaks, for all $r\in[n]$. 
This can be proved bijectively using an involution $\LK:\D_n\to\D_n$ due to Lalanne~\cite{lalanne_involution_1992} and Kreweras~\cite{kreweras_sur_1970},
which has the property that
\begin{equation}\label{eq:LKpea}\pea(D)=n+1-\pea(\LK(D)).\end{equation}


This extended abstract is structured as follows. In \cref{sec:results} we present our main results. 
The proof of the formula giving the distribution of the number of descents and plateaus on nonnesting permutations can be found in the full version~\cite{long_version}; here we only give an overview of the bijections in the proof.
In \cref{sec:proofs_symmetry} we use these bijections, along with the Lalanne-Kreweras involution, to prove some symmetry properties of the distributions of the number of descents and weak descents on nonnesting permutations. Finally, \cref{sec:generalization} discusses some generalizations of our results to permutations of the multiset with $k$ copies of each entry, for any fixed $k$.


\section{Main results}\label{sec:results}

Our main result is the following strikingly simple expression for the polynomial $\poly_n(t,u)$ from Equation~\eqref{eq:polydef}, as a product of an Eulerian polynomial and a Narayana polynomial.

\begin{theorem}\label{thm:main} 
For $n\ge1$,
$$\poly_n(t,u)=A_n(t)\,N_n(t,u).$$
\end{theorem}

\begin{example}\label{ex:n4} Here are the polynomials $\poly_n(t,u)$ for $n\in\{2,3\}$, along with the factorizations given by \cref{thm:main}:
\begin{align*}
\poly_2(t,u)&amp;={u}^{2}+ ( 1+{u}^{2}) t+{t}^{2}=\left(1+t\right)\left({u}^{2}+t\right),\\
\poly_3(t,u)&amp;={u}^{3}+ ( 1+2u+4{u}^{3} ) t+ ( 5+8u+{u}^{3}
 ) {t}^{2}+ ( 5+2u ) {t}^{3}+{t}^{4}\\
 &amp;=\left(1+4t+t^2\right) \left({u}^{3}+ ( 1+2u ) t+{t}^{2}
\right). %\\
%\poly_4(t,u)&amp;={u}^{4}+ ( 1+2u+3{u}^{2}+11{u}^{4} ) t+ ( 15+24u+33{u}^{2}+11{u}^{4} ) {t}^{2}+ ( 56+44u+33{u}^{2}+{u}^{4} ) {t}^{3}\\ &amp; \quad + ( 56+24u+3{u}^{2} ) {t}^{4}
%+ ( 15+2u ) {t}^{5}+{t}^{6}\\
%&amp;=\left(1+11t+11t^2+t^3\right) \left({u}^{4}+ ( 1+2u+3{u}^{2} ) t+ ( 4+2u ) {t}^{2}+{t}^{3}\right).
\end{align*}
\end{example}

As a consequence, we obtain the following two statements about the symmetry of the distribution of descents and weak descents on nonnesting permutations.

\begin{corollary}\label{cor:symmetric_wdes}
The distribution of the number of weak descents on $\C_n$ is symmetric: for all $r$,
$$|\{\pi\in\C_n:\wdes(\pi)=r\}|=|\{\pi\in\C_n:\wdes(\pi)=2n-r\}|.$$
\end{corollary}

\begin{proof}
This follows from \cref{thm:main} and the fact that both $A_n(t)$ and $N_n(t,t)$ are palindromic. Indeed, Equations~\eqref{eq:Apali} and~\eqref{eq:Nttpali} imply that \[\poly_n(t,t)=A_n(t)N_n(t,t)=t^{2n}A(1/t)N_n(1/t,1/t)=t^{2n}\poly_n(1/t,1/t).\qedhere\]
\end{proof}

\begin{corollary}\label{cor:symmetric_des}
The distribution of the number of descents on $\C_n$ is symmetric: for all $r$,
$$|\{\pi\in\C_n:\des(\pi)=r\}|=|\{\pi\in\C_n:\des(\pi)=2n-2-r\}|.$$
\end{corollary}

\begin{proof}
In addition to Equation~\eqref{eq:Apali}, we now use the fact that $N_n(t,1)=t^{n-1}N_n(1/t,1)$, which follows from Equations~\eqref{eq:Nt1Ntt} and~\eqref{eq:Nttpali}. We obtain \[\poly_n(t,1)=A_n(t)N_n(t,1)=t^{2n-2}A(1/t)N_n(1/t,1)=t^{2n-2}\poly_n(1/t,1).\qedhere\]
\end{proof}

\begin{example} Setting $u=1$ in \cref{ex:n4}, we obtain the following palindromic expressions:
\begin{align*}
\poly_2(t,1)&amp;=1+2t+t^2=(1+t)(1+t),\\
\poly_3(t,1)&amp;=1+7t+14t^2+7t^3+t^4=(1+4t+t^2)(1+3t+t^2). %\\
%\poly_4(t,1)&amp;=1+17t+83t^2+134t^3+83t^4+17t^5+t^6=(1+11t+11t^2+t^3)(1+6t+6t^2+t^3).
\end{align*}
\end{example}

It is interesting to note that, in contrast to the symmetry of the Eulerian polynomials, there seems to be no obvious explanation for the symmetries described by \cref{cor:symmetric_wdes,cor:symmetric_des}. We remark that the analogous statements for quasi-Stirling permutations do not hold~\cite{elizalde_descents_2021}.
Bijective proofs of \cref{cor:symmetric_wdes,cor:symmetric_des} will be provided in \cref{sec:proofs_symmetry}.


To establish \cref{thm:main}, we prove a slightly stronger statement. For $\sigma\in\S_n$, define 
$$\C_n^\sigma=\{\pi\in\C_n:\s(\pi)=\sigma\},$$
which can be used to partition the set of nonnesting permutations as 
$\C_n=\bigsqcup_{\sigma\in\S_n} \C_n^\sigma$.
Letting 
\begin{equation}\label{eq:polysidef}
\poly_n^\sigma(t,u)=\sum_{\pi\in\C_n^\sigma}t^{\des(\pi)}u^{\plat(\pi)},
\end{equation}
we have the following refinement.

\begin{theorem}\label{thm:refined}
For all $\sigma\in\S_n$, 
$$\poly_n^\sigma(t,u)=t^{\des(\sigma)}N_n(t,u).$$
\end{theorem} 
Note that \cref{thm:main} follows immediately from \cref{thm:refined}, since 
$$\poly_n(t,u)=\sum_{\sigma\in\S_n}\poly_n^\sigma(t,u)=\sum_{\sigma\in\S_n}t^{\des(\sigma)}N_n(t,u)=A_n(t)N_n(t,u).$$

The proof of \cref{thm:refined} is omitted in this extended abstract but can be found in the full version~\cite{long_version}. Here we give an overview. A nonnesting permutation $\pi\in\C_n$ is uniquely determined by the underlying nonnesting matching $\mat(\pi)$ and the subsequence of first (equivalently, second) copies $\s(\pi)\in\S_n$. We denote by $\dy(\pi)$ the Dyck path that corresponds to $\mat(\pi)$ via the standard bijection between nonnesting matchings and Dyck paths. This path is obtained by reading $\pi$ from left to right and taking an $\E$ step for each first copy of an element, and an $\N$ step for each second copy; see \cref{fig:visualization}.
Under this representation, plateaus of $\pi$ correspond to low peaks of $D$, namely, occurrences of adjacent steps $\E\N$ that touch the diagonal, and so 
\begin{equation}\label{eq:plat=lpea}
    \plat(\pi)=\lpea(D).
\end{equation}

\begin{figure}[htb]
\centering
\begin{tikzpicture}[scale=.6]
  \begin{scope}[shift={(-17,2)}]
   \foreach [count=\i] \j in {2,5,2,5,3,1,6,3,7,4,1,6,7,4}
        \node[pnt,label=below:$\j$] at (\i,0)(\i) {};
   \arc{1}{3} \arc{2}{4} \arc{5}{8} \arc{6}{11} \arc{7}{12} \arc{9}{13} \arc{10}{14}
   \end{scope}
      \grid{7}
      \def\sig{{0,2,5,3,1,6,7,4}}
      \labelgrid{7}
      \draw[very thick,blue](0,0) \e\e\n\n\e\e\e\n\e\e\n\n\n\n;
      \draw[blue] (4.3,1.5) node {$D$};
\end{tikzpicture}
\caption{Representation of the permutation $\pi=25253163741674\in\C_7$ as a matching (left) and as Dyck path $D=\dy(\pi)$ 
in a labeled grid (right), where $\s(\pi)=2531674$.}
\label{fig:visualization}
\end{figure}

The map $\pi\mapsto(\s(\pi),\dy(\pi))$ is a bijection between $\C_n$ and $\S_n\times\D_n$. 
Given $\sigma\in\S_n$ and $D\in\D_n$, we denote by $\pi=\pi(\sigma,D)$ the unique permutation in $\C_n$ such that $\s(\pi)=\sigma$ and $\dy(\pi)=D$. 
The first step is to prove the theorem when $\sigma$ is the identity permutation, which we denote by
$\id=12\dots n\in\S_n$.
In this special case, all the descents of $\pi$ come from high peaks, namely, occurrences of $\E\N$ that do not touch the diagonal. Thus, 
\begin{equation}\label{eq:des=hpea}
    \des(\pi)=\hpea(D)
\end{equation} in this case, and it follows that 
$$
\poly_n^{\id}(t,u)=\sum_{\pi\in\C_n^{\id}}t^{\des(\pi)}u^{\plat(\pi)}=\sum_{D\in\D_n}t^{\hpea(D)}u^{\lpea(D)}=N_n(t,u).
$$

The computation of $\poly_n^{\si}(t,u)$ for arbitrary $\sigma$ is done in two stages. 
We first prove that, for fixed $n$, the polynomial $\poly_n^\sigma(t,u)$ depends only on the descent set of $\sigma$, by showing that swapping any two non-adjacent entries of $\sigma$ with consecutive values does not change this polynomial.
For any $S\subseteq[n-1]$, this allows us to define define $\poly_n^S(t,u)=\poly_n^\sigma(t,u)$, where $\sigma$ is any permutation in $\S_n$ with descent set $S$, and to reduce the problem to the case where $\sigma$ has a very specific form.  We then prove bijectively that if $S'$ is obtained from $S$ by removing its largest element, then $\poly_n^{S}(t,u)=t \poly_n^{S'}(t,u)$, so one can repeatedly apply this fact to remove all the elements from the descent set of $\sigma$, reducing the problem to the case of the identity permutation.
Our construction produces a bijection \begin{equation}\label{eq:phi_sigma} \phi_\sigma:\C^\sigma_n\to\C^{\id}_n \end{equation} satisfying that 
\begin{equation}\label{eq:desphi}
\des(\phi_\sigma(\pi))=\des(\pi)-\des(\sigma) \qquad\text{and}\qquad \plat(\phi_\sigma(\pi))=\plat(\pi)
\end{equation}
for all $\pi\in\C_n^\si$.

For example, if 
\begin{equation}\label{eq:example}
\si=281375496 \quad \text{and} \quad \pi=228183175437954696\in\C_9^\si,
\end{equation} 
then $\phi_\sigma(\pi)=112324354657896789$, where $\des(\sigma)=4$, $\des(\pi)=9$, and $\des(\phi_\sigma(\pi))=5$. The details of the construction can be found in~\cite{long_version}.

We conclude this section with two statements about the symmetry of the distributions of descents and weak descents on the set of nonnesting permutations having a fixed underlying~$\sigma$. These are simple consequences of \cref{thm:refined} and the palindromicity of $N_n(t,t)$ and $N_n(t,1)$, respectively.

\begin{corollary}\label{cor:symmetric_wdes_sigma}
For each $\sigma\in\S_n$, the distribution of the number of weak descents on $\C^\sigma_n$ is symmetric: for all $r$,
$$|\{\pi\in\C_n^\si:\wdes(\pi)-\des(\sigma)=r\}|=|\{\pi\in\C_n^\si:\wdes(\pi)-\des(\sigma)=n+1-r\}|.$$
\end{corollary}

\begin{corollary}\label{cor:symmetric_des_sigma}
For each $\sigma\in\S_n$, the distribution of the number of descents on $\C^\sigma_n$ is symmetric: for all $r$,
$$|\{\pi\in\C_n^\si:\des(\pi)-\des(\sigma)=r\}|=|\{\pi\in\C_n^\si:\des(\pi)-\des(\sigma)=n-1-r\}|.$$
\end{corollary}


\section{Bijective proofs of symmetry}\label{sec:proofs_symmetry}

Combining the bijection $\phi_\si$ from Equation~\eqref{eq:phi_sigma} with the involution $\LK$ from \cref{sec:Narayana}, one can give bijective proofs of \cref{cor:symmetric_wdes,cor:symmetric_des,cor:symmetric_wdes_sigma,cor:symmetric_des_sigma}.

The Lalanne--Kreweras involution $\LK$ can be interpreted as an involution on permutations $\LKC:\C_n^\id\to\C_n^\id$, by identifying each $\pi\in\C_n^\id$ with its associated Dyck path $\dy(\pi)\in\D_n$. Specifically, given $\pi\in\C_n^\id$ with associated Dyck path $D=\dy(\pi)$, define $\LKC(\pi)\in\C_n^\id$ to be the permutation whose associated Dyck path is $\LK(D)$.

If $\pi=\pi(\id,D)\in\C_n^\id$, Equations~\eqref{eq:plat=lpea} and~\eqref{eq:des=hpea} imply that $$\wdes(\pi)=\des(\pi)+\plat(\pi)=\hpea(D)+\lpea(D)=\pea(D).$$
Thus, the behavior of $\LK$ on the number of peaks described in Equation~\eqref{eq:LKpea} translates to the fact that, for any $\pi\in\C_n^\id$,
\begin{equation}\label{eq:LKCwdes}
\wdes(\pi)=n+1-\wdes(\LKC(\pi)).
\end{equation}

\begin{proof}[Bijective proof of \cref{cor:symmetric_wdes_sigma}]
Define an involution $\Phi_\si=\phi_\si^{-1}\circ\LKC\circ\phi_\si$ from $\C_n^\si$ to itself. 
Adding the two equalities in Equation~\eqref{eq:desphi},
\begin{equation}\label{eq:wdesphi}
    \wdes(\phi_\si(\pi))=\wdes(\pi)-\des(\si)
\end{equation}
for every $\pi\in\C_n^\sigma$. Using this property twice and applying Equation~\eqref{eq:LKCwdes}, it follows that
\begin{align}\nonumber
    \wdes(\pi)-\des(\si)&amp;=\wdes(\phi_\si(\pi))=n+1-\wdes(\LKC(\phi_\si(\pi)))\\ \label{eq:wdesPhi}
    &amp;=n+1-(\wdes(\Phi_\si(\pi))-\des(\si))
\end{align}
for every $\pi\in\C_n^\sigma$. Thus, the map $\Phi_\si$ provides the desired bijection.
\end{proof}

For example, for $\sigma$ and $\pi$ as in Equation~\eqref{eq:example}, we have $\Phi_\si(\pi)=281372581347549966$. Note that $\wdes(\pi)=10$ and $\wdes(\Phi_\si(\pi))=8$, satisfying Equation~\eqref{eq:wdesPhi}.


\begin{proof}[Bijective proof of \cref{cor:symmetric_wdes}]
Consider now the composition $\Psi_\si=\phi_{\si^R}^{-1}\circ\LKC\circ\phi_\si$, which is a bijection from $\C_n^\si$ to $\C_n^{\si^R}$.
By definition, the inverse of $\Psi_\si$ is simply $\Psi_{\si^R}$. Equation~\eqref{eq:wdesphi} for $\sigma$ and $\sigma^R$, together with Equation~\eqref{eq:LKCwdes}, imply that
\begin{align*}
\wdes(\pi)-\des(\si)=n+1-(\wdes(\Psi_\si(\pi))-\des(\si^R)).
\end{align*}
Using Equation~\eqref{eq:desRsi}, it follows that
\begin{equation}\label{eq:wdesPsi}
\wdes(\pi)=2n-\wdes(\Psi_\si(\pi)).
\end{equation}
Thus, the involution $\Psi:\C_n\to\C_n$ defined by $\Psi(\pi)=\Psi_\si(\pi)$ whenever $\pi\in\C_n^\sigma$ provides the desired bijection.
\end{proof}

\begin{proof}[Bijective proof of \cref{cor:symmetric_des_sigma}] 
Denote by $R$ the reversal map that takes $\pi$ to $\pi^R$, and define the composition $\ol\Phi_\si=R\circ\Phi_{\si^R}\circ R$, which is an involution from $\C_n^\si$ to itself.

Let $\pi\in\C_n^\sigma$. Using the fact that 
\begin{equation}\label{eq:desRwdes}
 \des(\pi^R)=2n-1-\wdes(\pi),
\end{equation}
together with Equation~\eqref{eq:desRsi}, we have
\begin{equation}\label{eq:desR}
    \des(\pi)-\des(\si)=n-(\wdes(\pi^R)-\des(\si^R)).
\end{equation}
Using  Equation~\eqref{eq:wdesPhi} with $\pi^R$ and $\si^R$ playing the roles of $\pi$ and $\sigma$, respectively, together with Equation~\eqref{eq:desR} applied twice, we get
\begin{align*}
\des(\pi)-\des(\si)=n-1-(\des(\ol\Phi_\si(\pi))-\des(\si)),
\end{align*}
and so $\ol\Phi_\si$ gives the desired bijection.
\end{proof}

\begin{proof}[Bijective proof of \cref{cor:symmetric_des}]
Consider the composition $\ol\Psi_\si=R\circ\Psi_{\si^R}\circ R$,  which is a bijection from $\C_n^\si$ to $\C_n^{\si^R}$.
The inverse of $\ol\Psi_\si$ is $\ol\Psi_{\si^R}$. Using Equation~\eqref{eq:wdesPsi} with $\pi^R$ and $\si^R$ playing the roles of $\pi$ and $\sigma$, together with Equation~\eqref{eq:desRwdes} applied twice, we get
$$\des(\pi)=2n-1-\wdes(\pi^R)=-1+\wdes(\Psi_{\si^R}(\pi^R))
=2n-2-\des(\ol\Psi_\si(\pi)).$$
Thus, the involution $\ol\Psi:\C_n\to\C_n$ defined by $\ol\Psi(\pi)=\ol\Psi_\si(\pi)$ whenever $\pi\in\C_n^\sigma$ provides the desired bijection.
\end{proof}


It might be possible to find simpler bijections
proving our results about symmetry of the distributions.

\begin{problem}
Give direct bijections proving \cref{cor:symmetric_wdes,cor:symmetric_des,cor:symmetric_wdes_sigma,cor:symmetric_des_sigma} that do not require passing through the case where $\sigma$ is the identity permutation.
\end{problem}

\section{Generalizations}\label{sec:generalization}

Denote by $\nnk$ the multiset consisting of $k$ copies of each number in $[n]$, so that $\bigsqcup^2[n]=\nn$.
Generalized Stirling permutations, often called $k$-Stirling permutations, are permutations of $\nnk$ that avoid the pattern $212$. This generalization, originally proposed by Gessel and Stanley~\cite{gessel_stirling_1978}, has been studied for example in~\cite{park_r-multipermutations_1994,janson_generalized_2011,kuba_analysis_2011}.

Similarly, $k$-quasi-Stirling permutations were defined by the author~\cite{elizalde_descents_2021} as those permutations of $\nnk$ that avoid the patterns $1212$ and $2121$. Permutations of $\nnk$ can be viewed as ordered set partitions on $[kn]$ into $n$ blocks of size $k$, where block $b$ consists of those $i\in[kn]$ such that $\pi_i=b$, for each $b\in[n]$. With this interpretation, a permutation avoids $1212$ and $2121$ if the underlying set partition is {\em noncrossing}, meaning that there are no $i&lt;j&lt;\ell&lt;m$ so that $i,\ell$ are in one block and $j,m$ are in another block; see
\cite[Exer.\ 159]{stanley_catalan_2015}.
The distribution of the number of descents and plateaus in $k$-quasi-Stirling permutations is given in~\cite{elizalde_descents_2021}.

There are several ways to generalize nonnesting permutations of $\nn$, as given by \cref{def:nonnesting}, to permutations of $\nnk$. Next we describe three different generalizations, which arise from distinct ways to view elements of $\C_n$: as pattern-avoiding multipermutations, as labeled nonnesting matchings, and as multipermutations where the subsequences of first copies and of second copies of each entry coincide.

\subsection{Permutations avoiding $1221$ and $2112$}

First we consider permutations $\pi$ of $\nnk$ that avoid the patterns $1221$ and $2112$, that is, there do not exist $i&lt;j&lt;\ell&lt;m$ such that $\pi_i=\pi_m\neq\pi_j=\pi_\ell$. Let $\A_n^{k}$ denote this set of permutations. For example, $\A_2^{3}=\{111222,112122,221211,222111\}$. 
When $k\ge3$, this definition is quite restrictive. The distribution of descents and plateaus is relatively simple in this case, see~\cite{long_version} for the proof of the next result.

\begin{theorem}\label{thm:Ank}
For $k\ge3$ and $n\ge1$, we have
$$\sum_{\pi\in\A_n^{k}} t^{\des(\pi)}u^{\plat(\pi)}=u^{(k-3)n+2}(u^2+t)^{n-1}A_n(t).$$
\end{theorem}

Setting $u=1$ and $u=t$ in \cref{thm:Ank}, respectively, it follows easily that the distribution of the number of descents (respectively, weak descents) on $\A_n^{k}$ is symmetric. Our proof provides a bijective explanation of these symmetries.

\subsection{Nonnesting permutations}

A second way to generalize \cref{def:nonnesting} to permutations of $\nnk$ is to require that the underlying set partition is {\em nonnesting}; see \cite{athanasiadis_noncrossing_1998,athanasiadis_piles_1999,chen_crossings_2007}
%,klazar_identities_2006,kasraoui_distribution_2006} 
and \cite[Exer.\ 164]{stanley_catalan_2015}.
In this case, a block $\{i_1,i_2,\dots,i_k\}_&lt;$ of the partition is represented by $k-1$ arcs $(i_1,i_2),(i_2,i_3),\dots,(i_{k-1},i_k)$,
and the partition is nonnesting if this representation does not contain any pair of nested arcs, i.e., two arcs $(i,m)$ and $(j,\ell)$ such that $i&lt;j&lt;\ell&lt;m$. In terms of the permutation $\pi$ of $\nnk$, an arc is placed between $i$ and $j$ if $\pi_i=\pi_j$ and there is no other copy of this value between positions $i$ and $j$ of $\pi$. 
%This is equivalent to requiring that $\pi$ avoids the {\em barred} patterns $12\overline{1}21$ and $21\overline{2}12$; see~\cite{west_sorting_1993,bousquet-melou_forest-like_2007} for other appearances of barred patterns in the literature. 
Following Athanasiadis~\cite{athanasiadis_piles_1999}, who first considered such permutations in a geometric context, we call these {\em nonnesting permutations}.
Let $\B_n^{k}$ denote the set of nonnesting permutations of $\nnk$.
Clearly, $\A_n^{k}\subseteq \B_n^{k}$, but the converse is not true in general. For example, $\B_2^{3}=\A_n^{k}\sqcup\{121212,212121\}$.

A bijection between noncrossing and nonnesting partitions that preserves the sizes of the blocks was given by Athanasiadis~\cite{athanasiadis_noncrossing_1998}. It follows that the number of nonnesting permutations of $\nnk$ equals the number of those where the underlying partition is noncrossing, namely, $k$-quasi-Stirling permutations. This number is given in~\cite{elizalde_descents_2021}, and so we get $$|\B_n^k|=\frac{(kn)!}{((k-1)n+1)!}=n!\,\Cat_{n,k},$$
where $$\Cat_{n,k}=\frac{1}{(k-1)n+1}\binom{kn}{n}$$ is called a {\em $k$-Catalan number} \cite[pp.\ 168--173]{stanley_enumerative_1999}.
Given the simple formula in \cref{thm:main} for the $k=2$ case and the results in~\cite{elizalde_descents_2021} on $k$-quasi-Stirling permutations, it is natural to ask for the distribution of the number of descents and the number of plateaus on $\B_n^{k}$ for $k\ge3$.
Interestingly, unlike in the case $k=2$, the distribution of the number of descents on $\B_n^{k}$ fails to be symmetric for $k=3$ and $n=4$.

\subsection{Canon permutations}

A third possible generalization arises when thinking of $\C^\si_n$ as the set of permutations of $\nn$ 
where both the subsequence of first copies of each entry 
and the subsequence of second copies of each entry equal $\si$.
For $\si\in\S_n$ and $k\ge1$, define $\C^{k,\sigma}_n$ to be the set of permutations $\pi$ of $\nnk$ such that, for each $j\in[k]$, the subsequence of $\pi$ formed by the $j$th copy (from the left) of each entry is $\sigma$. 
Let $\C^{k}_n=\bigsqcup_{\sigma\in\S_n}\C^{k,\sigma}_n$. 
We call elements of $\C^{k}_n$ {\em $k$-canon permutations}.
By construction, $\A^{1}_n=\B^{1}_n=\C^{1}_n=\S_n$ and $\A^{2}_n=\B^{2}_n=\C^{2}_n=\C_n$, so the three definitions generalize the $k=1$ and $k=2$ cases.

It can be shown that $\B^{k}_n\subseteq\C^{k}_n$ in general, but the converse does not hold.
For example, $\C_2^{3}=\B_2^{3}\sqcup\{112212,121122,212211,221121\}$.

In forthcoming work, we will show that this definition provides the right setting to generalize \cref{thm:main,thm:refined}.
We will show that, if we define
$$
\poly^k_n(t,u)=\sum_{\pi\in\C^k_n} t^{\des(\pi)}u^{\plat(\pi)} \quad \text{and} \quad 
\poly^{k,\si}_n(t,u)=\sum_{\pi\in\C^{k,\si}_n} t^{\des(\pi)}u^{\plat(\pi)}
$$
in analogy to Equations~\eqref{eq:polydef} and~\eqref{eq:polysidef}, then
for all $\sigma\in\S_n$ and all $k\ge1$ we have
\begin{equation}\label{eq:conj_refined}\poly_n^{k,\sigma}(t,u)=t^{\des(\sigma)}\poly_n^{k,\id}(t,u).\end{equation}
Thus, summing over all $\sigma\in\S_n$,
$$\poly_n^{k}(t,u)=A_n(t) \poly_n^{k,\id}(t,u).$$

The proof extends some of the ideas in our proofs of \cref{thm:main,thm:refined} from Dyck paths to the more general setting of standard Young tableaux of rectangular shape. In particular, it yields certain generalizations of the notion of descents on such tableaux, as well as bijective proofs of some equidistribution results for these new statistics.


\printbibliography

\end{document}


</pre></body></html>