\documentclass[12pt]{amsart}

\textheight22.8cm \textwidth15.6cm \hoffset-1.7cm \voffset-.5cm

\usepackage{tikz}
\usepackage{hyperref}
%\usepackage[backend=bibtex]{biblatex}
%\addbibresource{AdinBagnoRoichman.bib}%
\newlength{\unit}
\setlength{\unit}{0.3cm} % TWEAK THIS TO MAKE THE FIGURES THE RIGHT SIZE

\tikzset{%
  dots/.style args={#1per #2}{%
    line cap=round,
    dash pattern=on 0 off #2/#1
  }
}
\newcommand{\Dfn}[1]{\emph{#1}}%
\newcommand{\fS}{\mathfrak{S}}%
\newcommand{\fD}{\mathfrak{D}}%
\DeclareMathOperator{\lrmax}{LRMAX}%
\DeclareMathOperator{\ldes}{ldes}%
\DeclareMathOperator{\blocks}{bl}%
\DeclareMathOperator{\returns}{ret}%
\DeclareMathOperator{\rises}{RISES}%
\DeclareMathOperator{\ldr}{ldr}%
\title[An involution on Dyck paths]%
{An involution on Dyck paths that preserves the rise composition and
  interchanges the number of returns and the position of the first
  double fall}%
\author{Martin Rubey}%
\email{\url{Martin.Rubey@tuwien.ac.at}}%
\address{Fakult\"at f\"ur Mathematik und Geoinformation, TU Wien,
  Austria}%
\thanks{Supported by the Austrian Science Fund (FWF): P 29275}
\begin{document}
\begin{abstract}
  Motivated by a recent paper of Adin, Bagno and Roichman, we present
  an involution on Dyck paths that preserves the rise composition and
  interchanges the number of returns and the position of the first
  double fall.
\end{abstract}
\maketitle

\thispagestyle{myheadings}
\font\Rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 77 \Rms (2018), Article~B77f\hfill}
\def\thepage{}


\section{Introduction}
Let $\fS_n(321)$ be the set of $321$-avoiding permutations on $n$
letters.  In a recent paper of Adin, Bagno and
Roichman~\cite{arXiv:1611.06979} a new equidistribution result of two
statistics on $\fS_n(321)$ is used to demonstrate the Schur
positivity of quasi-symmetric functions associated with certain
subsets of $\fS_n(321)$.  Using a recursively defined
bijection\footnote{\url{http://www.findstat.org/Mp00124}} the authors
establish
\[
\sum_{\pi\in\fS_n(321)} \mathbf x^{\lrmax(\pi)} q^{\blocks(\pi)}%
=\sum_{\pi\in\fS_n(321)} \mathbf x^{\lrmax(\pi)}
q^{n-\ldes(\pi^{-1})}\text{, where}
\]
\begin{itemize}
\item $\lrmax(\pi)$ is the \emph{set} of positions of the
  left-to-right maxima of $\pi$ and
  $\mathbf x^L = \prod_{i\in L} x_i$,
\item $\blocks(\pi)=\lvert\{i: \forall j\leq i:\pi(j)\leq i\}\rvert$
  is the number of blocks of $\pi$ and
\item $\ldes(\pi)=\max\left(\{0\}\cup\{i: \pi(i)>\pi(i+1)\}\right)$
  is the position of the last descent of $\pi$.
\end{itemize}
We exhibit an involution which proves the stronger result that,
fixing $\lrmax$, the joint distribution of $\pi\mapsto \blocks(\pi)$
and $\pi\mapsto n-\ldes(\pi^{-1})$ is in fact symmetric.

Let us first transform the statistics involved into statistics on
Dyck paths, using a bijection due to
Krattenthaler~\cite{MR1868978}\footnote{\url{http://www.findstat.org/Mp00119}}.
To do so, it is convenient to define a Dyck path as a path in
$\mathbb N^2$ consisting of $(1,0)$- and $(0,1)$-steps beginning at
the origin, ending at $(n,n)$, and never going below the diagonal
$y=x$.  We refer to $(1,0)$-steps also as \Dfn{east steps} or
\Dfn{falls}, and to $(0,1)$-steps also as \Dfn{north steps} or
\Dfn{rises}, and the number $n$ as the \Dfn{semilength} of the path.
Krattenthaler's bijection maps
\begin{itemize}
\item $\fS_n(321)$ to the set of Dyck paths $\fD_n$ of semilength
  $n$,
\item $\lrmax(\pi)$ to $\rises(D)$, the set of $x$-coordinates
  (plus~1) of the north steps of the Dyck path,
\item $\blocks(\pi)$ to $\returns(D)$, the number of \Dfn{returns} of
  the path, that is, the number of east steps that end on the main
  diagonal,
\item $\ldes(\pi^{-1})$ to $\ldr(D)$, the $y$-coordinate of the
  midpoint of the last double rise, that is, the last pair of two
  consecutive north steps.  For the path without double rises, we set
  $\ldr(D)=0$.
\end{itemize}

The purpose of this note is to provide an involution $\Phi$\footnote{\url{http://www.findstat.org/Mp00132}} that
implies
\begin{equation*}
  \sum_{\pi\in\fD_n} \mathbf x^{\rises(\pi)} p^{\returns(D)}
  q^{n-\ldr(D)}%
  =\sum_{\pi\in\fD_n} \mathbf x^{\rises(\pi)} p^{n-\ldr(D)}
  q^{\returns(D)}.
\end{equation*}

\section{An involution on Dyck paths}

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL MARTIN RUBEY}{\SMALL AN INVOLUTION ON DYCK PATHS}

In the spirit
of~\cite{MR3422679}\footnote{\url{http://www.findstat.org/Mp00118}},
we first introduce an invertible map $\phi$ taking a Dyck path $D$
that ends with two east steps and satisfies $\ldr(D) < n-1$ (that is,
not maximal) to a Dyck path $\phi(D)$ that ends with two east steps
and has at least two returns.  The crucial properties of this map are
as follows:
\begin{itemize}
\item $\rises(\phi(D)) = \rises(D)$
\item $\returns(\phi(D)) = \returns(D)+1$
\item $\ldr(\phi(D)) = \ldr(D)+1$
\end{itemize}
The desired involution $\Phi$ then maps an arbitrary path
$D(NE)^\ell$ (of semilength $n+\ell$) to
$\phi^{(n-\ldr(D)-\returns(D))}(D)\;(NE)^\ell$.

To define $\phi$, write $D$ as the concatenation of three paths $P$,
$Q$ and $R$ where
\begin{itemize}
\item $R$ is maximal such that it has no double rises, begins with a
  rise and the path $Q$ before $R$ ends with an east step, and
\item $Q\,R$ is a prime Dyck path, that is, its only return is the
  final east step.
\end{itemize}
Let $N_0\, Q_0\, N_1\, Q_1\,\dots\, N_k\, Q_k$ be the prime decomposition
of $Q$, that is, all the $Q_i$ are prime Dyck paths and the $N_i$ are
sequences of north steps.  Note that $N_0$ is non-empty, because $Q$
does not return to the diagonal.  We distinguish three cases,
illustrated in Figure~\ref{fig:examples}:
\begin{enumerate}
\item If $k=0$ or $N_1\neq\emptyset$ define
  $\phi(D)=P\,Q_0\, N_1\, \dots\, N_k\, Q_k\, N_0\, R$.
\end{enumerate}
In the remaining two cases let $N$ be all but one of the north steps
of the final rise in $Q$, and let $Q'$ be $Q$ with $N_0$, $Q_0$ and
$N$ erased.
\begin{enumerate}
\item[$(2)$] If $N_1=\dots=N_k=\emptyset$ define
  $\phi(D)=P\, N\, Q_0\, Q'\, N_0\, R$.
\item[$(3)$] Otherwise define $\phi(D)=P\, Q_0\, N\, Q'\, N_0\, R$.
\end{enumerate}

We now provide an inverse for $\phi$.  Let $\tilde D$ be a Dyck path
that ends with two east steps and has at least two returns.  Write
$\tilde D$ as the concatenation of paths $P$, $\tilde Q$, $\tilde E$,
$\tilde N$ and $R$ where
\begin{itemize}
\item $R$ is maximal such that it has no double rises and begins with
  a rise, and
\item $\tilde Q\,\tilde E\,\tilde N\,R$ is a Dyck path with precisely
  two returns, $\tilde N$ is a maximal sequence of north steps and
  $\tilde E$ is a maximal sequence of east steps.
\end{itemize}

Let
$\tilde N_0\, \tilde Q_1\, \tilde N_1\,\dots\, \tilde Q_\ell\, \tilde
N_\ell$ be the prime decomposition of $\tilde Q$.
\begin{enumerate}
\item[$(\tilde 1)$] If $\tilde Q$ ends with a double rise, we have
  $\phi^{(-1)}(\tilde D)=P\, \tilde N\, \tilde Q\, \tilde E\, R$.
\item[$(\tilde 2)$] Otherwise, if $\tilde Q$ has no returns,
  $\phi^{(-1)}(\tilde D)=P\, \tilde N\, \tilde Q_1\, \tilde
  N_1\,\dots\, \tilde Q_\ell\, \tilde N_\ell\, \tilde N_0\, \tilde
  E\, R$.
\item[$(\tilde 3)$] Otherwise,
  $\phi^{(-1)}(\tilde D)=P\, \tilde N\, \tilde Q_1\, \tilde
  Q_2\,\tilde N_2\,\dots\, \tilde Q_\ell\, \tilde N_\ell\, \tilde
  N_1\, \tilde E\, R$.
\end{enumerate}

To conclude, we show that applying the constructions in Cases~$(1)$,
$(2)$ and~$(3)$ above a path corresponding to Cases~$(\tilde 1)$,
$(\tilde 2)$ and~$(\tilde 3)$, respectively.  Suppose that
$\tilde D = \phi(D)$ is obtained by applying Case $(1)$.  Because
$Q_k$ ends with the last double rise of $D$ followed by east steps,
$\tilde Q$ ends with a double rise.

In Case $(2)$, $N\,Q_0\, Q'$ is a prime Dyck path whose last sequence
of north steps has length $1$ so $\tilde Q$ does not end with a
double rise and has no returns, whereas $\tilde Q\, \tilde E$ is a
prime Dyck path.

Finally, in Case $(3)$, $N\, Q'\, N_0$ has no returns and its last
sequence of north steps has length $1$.  Thus, $\tilde Q$ does not
end with a double rise, but does have a return coming from $Q_0$.

\begin{figure}
  \centering
  {\tiny
  \begin{tikzpicture}[x=\unit, y=\unit]
    \node[left] at (-1,13) {\normalsize Cases $(1)$ and $(\tilde 1)$:};%
    \foreach \x/\y in {10/14,8/13,5/12,5/11,4/10,4/9,4/8,2/7,1/6,0/5,0/4,0/3,0/2,0/1,0/0}%
    \draw[dots = 3 per \unit] (-1,\y) -- (\x,\y);%
    \foreach \x/\y in {9/13,8/13,7/12,6/12,5/12,4/10,3/7,2/7,1/6,0/5}%
    \draw[dots = 3 per \unit] (\x,14) -- (\x,\y);%
    \draw[dotted] (14, 14) -- (0,0);%
    \draw (14,14) circle (0.2);%
    \node[below] at (0,0) {$0$};%
    \node[below] at (1,0) {$1$};%
    \node[below] at (2,0) {$2$};%
    \node[below] at (4,0) {$4$};%
    \node[below] at (5,0) {$5$};%
    \node[below] at (8,0) {$8$};%
    \node[below] at (10,0) {$10$};%
    \draw[rounded corners=1, line width=1.5]%
    (0,0)--(0,5)--%
    (1,5)--(1,6)--%
    (2,6)--(2,7)--%
    (4,7)--(4,10)--%
    (5,10)--(5,12)--%
    (8,12)--(8,13)--%
    (10,13)--(10,14)--%
    (14,14);%
    \draw[line cap=round, line width=2.5] (5,10+0.15)--(5,12-0.15);%
    \draw (6,14)--(11,9);%
    \node[below right] at (12,12) {$R$};%
    \node[below right] at (5,5) {$Q$};%
    \node[right] at (0,2.25) {$N_0$};%
    \node[right] at (4,7.5) {$N_1$};%
    \draw[dotted] (0,3) -- (4,7);%
    \draw[dotted] (4,8) -- (8,12);%
  \end{tikzpicture}
  \begin{tikzpicture}[x=\unit, y=\unit]
    \node[left] at (-1,7) {$\mapsto$}; %
    \foreach \x/\y in {10/14,8/13,8/12,8/11,8/10,5/9,5/8,4/7,4/6,4/5,2/4,1/3,0/2,0/1,0/0}%
    \draw[dots = 3 per \unit] (-1,\y) -- (\x,\y);%
    \foreach \x/\y in {9/13,8/13,7/9,6/9,5/9,4/7,3/4,2/4,1/3,0/2}%
    \draw[dots = 3 per \unit] (\x,14) -- (\x,\y);%
    \draw[dotted] (14, 14) -- (0,0);%
    \draw (14,14) circle (0.2);%
    \draw (4,4) circle (0.2);%
    \node[below] at (0,0) {$0$};%
    \node[below] at (1,0) {$1$};%
    \node[below] at (2,0) {$2$};%
    \node[below] at (4,0) {$4$};%
    \node[below] at (5,0) {$5$};%
    \node[below] at (8,0) {$8$};%
    \node[below] at (10,0) {$10$};%
    \draw[rounded corners=1, line width=1.5]%
    (0,0)--(0,2)--%
    (1,2)--(1,3)--%
    (2,3)--(2,4)--%
    (4,4)--(4,7)--%
    (5,7)--(5,9)--%
    (8,9)--(8,13)--%
    (10,13)--(10,14)--%
    (14,14);%
    \draw[line cap=round, line width=2.5] (8,11+0.15)--(8,13-0.15);%
    \draw (6,14)--(11,9);%
    \draw (3,14)--(9.5,7.5);%
    \draw (0,14)--(8,6);%
    \node[below right] at (9.25,9.25) {$\tilde N$};%
    \node[below right] at (7.75,7.75) {$\tilde E$};%
    \node[below right] at (12,12) {$R$};%
    \node[below right] at (3.5,3.5) {$\tilde Q$};%
  \end{tikzpicture}}
\\\bigskip
\centering
{\tiny
  \begin{tikzpicture}[x=\unit, y=\unit]
    \node[left] at (-1,13) {\normalsize Cases $(2)$ and $(\tilde 2)$:};%
    \foreach \x/\y in  {12/14,11/13,7/12,5/11,5/10,3/9,1/8,0/7,0/6,0/5,0/4,0/3,0/2,0/1,0/0}%
    \draw[dots = 3 per \unit] (-1,\y) -- (\x,\y);%
    \foreach \x/\y in  {11/13,10/12,9/12,8/12,7/12,6/11,5/11,4/9,3/9,2/8,1/8,0/7}%
    \draw[dots = 3 per \unit] (\x,14) -- (\x,\y);%
    \draw[dotted] (14, 14) -- (0,0);%
    \draw (14,14) circle (0.2);%
    \node[below] at (0,0) {$0$};%
    \node[below] at (1,0) {$1$};%
    \node[below] at (3,0) {$3$};%
    \node[below] at (5,0) {$5$};%
    \node[below] at (7,0) {$7$};%
    \node[below] at (11,0) {$11$};%
    \node[below] at (12,0) {$12$};%
    \draw[rounded corners=1, line width=1.5]%
    (0,0)--(0,7)--%
    (1,7)--(1,8)--%
    (3,8)--(3,9)--%
    (5,9)--(5,11)--%
    (7,11)--(7,12)--%
    (11,12)--(11,13)--%
    (12,13)--(12,14)--%
    (14,14);%
    \draw[line cap=round, line width=2.5] (5,9+0.15)--(5,11-0.15);%
    \draw (4,14)--(10,8);%
    \node[below right] at (11,11) {$R$};%
    \node[below right] at (4.5,4.5) {$Q$};%
    \node[right] at (0,2.5) {$N_0$};%
    \draw[dotted] (0,4) -- (7,11);%
  \end{tikzpicture}
  \begin{tikzpicture}[x=\unit, y=\unit]
    \node[left] at (-1,7) {$\mapsto$}; %
    \foreach \x/\y in {12/14,11/13,7/12,7/11,7/10,7/9,7/8,5/7,3/6,1/5,0/4,0/3,0/2,0/1,0/0}%
    \draw[dots = 3 per \unit] (-1,\y) -- (\x,\y);%
    \foreach \x/\y in  {11/13,10/12,9/12,8/12,7/12,6/7,5/7,4/6,3/6,2/5,1/5,0/4}%
    \draw[dots = 3 per \unit] (\x,14) -- (\x,\y);%
    \draw[dotted] (14, 14) -- (0,0);%
    \draw (14,14) circle (0.2);%
    \draw (7,7) circle (0.2);%
    \node[below] at (0,0) {$0$};%
    \node[below] at (1,0) {$1$};%
    \node[below] at (3,0) {$3$};%
    \node[below] at (5,0) {$5$};%
    \node[below] at (7,0) {$7$};%
    \node[below] at (11,0) {$11$};%
    \node[below] at (12,0) {$12$};%
    \draw[rounded corners=1, line width=1.5]%
    (0,0)--(0,4)--%
    (1,4)--(1,5)--%
    (3,5)--(3,6)--%
    (5,6)--(5,7)--%
    (7,7)--(7,12)--%
    (11,12)--(11,13)--%
    (12,13)--(12,14)--%
    (14,14);%
    \draw[line cap=round, line width=2.5] (7,10+0.15)--(7,12-0.15);%
    \draw (4,14)--(10,8);%
    \draw (0,14)--(8,6);%
    \draw (0,12)--(7,5);%
    \node[below right] at (11,11) {$R$};%
    \node[below right] at (3,3) {$\tilde Q$};%
    \node[below right] at (8,8) {$\tilde N$};%
    \node[below right] at (6.5,6.5) {$\tilde E$};%
  \end{tikzpicture}}
\\\bigskip
\centering
{\tiny
  \begin{tikzpicture}[x=\unit, y=\unit]
    \node[left] at (-1,13) {\normalsize Cases $(3)$ and $(\tilde 3)$:};%
    \foreach \x/\y in {9/14,8/13,7/12,5/11,5/10,5/9,4/8,2/7,1/6,0/5,0/4,0/3,0/2,0/1,0/0}%
    \draw[dots = 3 per \unit] (-1,\y) -- (\x,\y);%
    \foreach \x/\y in {8/13,7/12,6/11,5/11,4/8,3/7,2/7,1/6,0/5}%
    \draw[dots = 3 per \unit] (\x,14) -- (\x,\y);%
    \draw[dotted] (14, 14) -- (0,0);%
    \draw (14,14) circle (0.2);%
    \node[below] at (0,0) {$0$};%
    \node[below] at (1,0) {$1$};%
    \node[below] at (2,0) {$2$};%
    \node[below] at (4,0) {$4$};%
    \node[below] at (5,0) {$5$};%
    \node[below] at (7,0) {$7$};%
    \node[below] at (8,0) {$8$};%
    \node[below] at (9,0) {$9$};%
    \draw[rounded corners=1, line width=1.5]%
    (0,0)--(0,5)--%
    (1,5)--(1,6)--%
    (2,6)--(2,7)--%
    (4,7)--(4,8)--%
    (5,8)--(5,11)--%
    (7,11)--(7,12)--%
    (8,12)--(8,13)--%
    (9,13)--(9,14)--%
    (14,14);%
    \draw[line cap=round, line width=2.5] (5,9+0.15)--(5,11-0.15);%
    \draw (4,14)--(10,8);%
    \node[below right] at (11,11) {$R$};%
    \node[below right] at (4.5,4.5) {$Q$};%
    \node[right] at (0,2.25) {$N_0$};%
    \node[right] at (5,8.5) {$N_2$};%
    \draw[dotted] (0,3) -- (5,8);%
    \draw[dotted] (5,9) -- (7,11);%
  \end{tikzpicture}
  \begin{tikzpicture}[x=\unit, y=\unit]
    \node[left] at (-1,7) {$\mapsto$}; %
    \foreach \x/\y in {9/14,8/13,7/12,7/11,7/10,7/9,5/8,4/7,4/6,4/5,2/4,1/3,0/2,0/1,0/0}%
    \draw[dots = 3 per \unit] (-1,\y) -- (\x,\y);%
    \foreach \x/\y in {8/13,7/12,6/8,5/8,4/7,3/4,2/4,1/3,0/2}%
    \draw[dots = 3 per \unit] (\x,14) -- (\x,\y);%
    \draw[dotted] (14, 14) -- (0,0);%
    \draw (14,14) circle (0.2);%
    \draw (4,4) circle (0.2);%
    \node[below] at (0,0) {$0$};%
    \node[below] at (1,0) {$1$};%
    \node[below] at (2,0) {$2$};%
    \node[below] at (4,0) {$4$};%
    \node[below] at (5,0) {$5$};%
    \node[below] at (7,0) {$7$};%
    \node[below] at (8,0) {$8$};%
    \node[below] at (9,0) {$9$};%
    \draw[rounded corners=1, line width=1.5]%
    (0,0)--(0,2)--%
    (1,2)--(1,3)--%
    (2,3)--(2,4)--%
    (4,4)--(4,7)--%
    (5,7)--(5,8)--%
    (7,8)--(7,12)--%
    (8,12)--(8,13)--%
    (9,13)--(9,14)--%
    (14,14);%
    \draw[line cap=round, line width=2.5] (7,10+0.15)--(7,12-0.15);%
    \draw (4,14)--(10,8);%
    \draw (1,14)--(8.5,6.5);%
    \draw (0,13)--(7.5,5.5);%
    \node[below right] at (11,11) {$R$};%
    \node[below right] at (3.25,3.25) {$\tilde Q$};%
    \node[below right] at (8.5,8.5) {$\tilde N$};%
    \node[below right] at (7,7) {$\tilde E$};%
  \end{tikzpicture}}
\caption{Examples for Dyck paths and their images under $\phi$}
\label{fig:examples}
\end{figure}

\begin{thebibliography}{9}


\bibitem{arXiv:1611.06979}
R. M. Adin, E. Bagno and Y. Roichman,
{\em Block decomposition of permutations and Schur-positivity},
J. Algebraic Combin. (to appear); {\tt ar$\chi$iv:1611.06979}.

\bibitem{MR3422679}
S. Elizalde and M. Rubey,
{\em Symmetries of statistics on lattice paths between two
  boundaries}, Adv. Math. {\bf 287} (2016), 347--388.

\bibitem{MR1868978}
C. Krattenthaler,
{\em Permutations with restricted patterns and {D}yck paths},
Adv. Appl. Math. {\bf 27} (2001), 510--530.

\end{thebibliography}


\end{document}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: t
%%% End:
