\documentclass[12pt]{amsart}
\usepackage{graphicx}
\usepackage{epstopdf}
\usepackage{url}
\usepackage{latexsym}
\usepackage{amsfonts,amsmath,amssymb}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{question}[theorem]{Question}
\newtheorem{example}[theorem]{Example}
\newtheorem{require}[theorem]{Requirement}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{fact}[theorem]{Fact}
%\newcommand{\qed}{\mbox{$\Diamond$}\vspace{\baselineskip}}
\def\sym{\operatorname{sym}}
%\newcommand{\sym}{\hbox{sym}}
%\newenvironment{proof}{\noindent{\bf Proof:}}{\qed}
\newcommand{\Var}{\operatorname{\mathbb{V}}}
\newcommand{\E}{\operatorname{\mathbb{E}}}
\def\ds{\displaystyle}
%\usepackage{lineno}
%\linenumbers*[1]
\def\pr{\text{P}}
\def\ex{\text{E}}
\def\eps{\varepsilon}
\def\wh{\widehat}
\def\cal{\mathcal}
\def\R{\mathbb{R}}
\def\Z{\mathbb{Z}}
\def\Pr{\operatorname{\mathbb{P}}}

\date{\today}
\begin{document}


\title[Alternating runs]{Generating functions of permutations with respect to their alternating runs}

\author{Mikl\'os B\'ona}
\address{Department of Mathematics, University of Florida, $358$ Little Hall, P.O. Box $118105$,
Gainesville, FL, $32611-8105$, USA.}
\email{bona@ufl.edu}

\begin{abstract} We present a short, direct proof of the fact that the generating function of all permutations of a fixed length $n\geq 4$ with respect to the number of their alternating runs
is divisible by $(1+z)^m$, where $m=\lfloor (n-2)/2 \rfloor$. \end{abstract}

\maketitle

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

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 85 \rms (2021), Article~B85b\hfill}
\def\thepage{}

\section{Introduction}

Let $p=p_1p_2\cdots p_n$ be a permutation. For an index $i\in [2,n-1]$,  we say that $p$ changes directions at $i$ if $p_{i-1}<p_i>p_{i+1}$ or $p_{i-1}>p_i<p_{i+1}$. Furthermore, we say that $p$ has $k$ alternating runs if $p$ changes directions a total of $k-1$ times. 

Let $\hbox{run(p)}$ be the number of alternating runs of $p$, and let 
\[R_n(z) =\sum_{p} z^{\text{run}(p)},\]
where the sum is taken over all permutations of length $n$.
In this note, we prove that, for $n\geq 4$, the polynomial  $R_n(z)$ is divisible by a high power of $(1+z)$, namely by $(1+z)^m$, where
$m=\lfloor (n-2)/2 \rfloor$. 

This result was known before, by an analytic proof given by Herbert Wilf \cite{wilf} (which can also be found  as Theorem~1.42  in \cite{combperm} on page~31) that was based on 
the relation between the Eulerian polynomials and $R_n(z)$, and also by an induction proof by Richard Ehrenborg and the present author 
\cite{bona-ehr} that  touched upon Eulerian polynomials. However, in this paper, we provide a direct, non-inductive proof. This proof differs from the previous ones in that it is
{\em algebraic} (it uses enumeration under group action), and it shows a clear reason for the high multiplicity of $-1$ as a root of $R_n(z)$. 

\section{A group action on permutations}

Let $p=p_1p_2\cdots p_n$ be a permutation. The {\em complement} of $p$ is the permutation $\overline{p}=n+1-p_1 \ n+1 -p_2 \ \cdots n+1-p_n $. For instance, 
the complement of 425613 is 352164. It is clear that $p$ and $\overline{p}$ have the same number of alternating runs, since the diagram of $\overline{p}$ is just the diagram of $p$
reflected through a horizontal line. In what follows, we will say {\em flipped} instead of {\em reflected through a horizontal line}. 
Note that this symmetry implies that all coefficients of $R_n(z)$ are even for $n\geq 2$. 

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL MIKL\'OS B\'ONA}
{\SMALL ALTERNATING RUNS}

Let $s$ be a string of entries in $p$ that are in consecutive positions. Let $S$ be set of entries that occur in $s$, in other words, 
the {\em underlying set} of~$s$. Then the {\em complement of $s$ relative to  $S$} 
is the string obtained from $s$ so that, for each $j$, the $j$th smallest entry of $S$ is replaced by the $j$th largest entry of $S$.   For example, if $s=24783$, then the complement of $s$
relative to its underlying set $S$  is 84327.

We will use a similar notion for sets. Let $T\subseteq U $ be finite sets.  Let $T=\{t_1,t_2,\dots ,t_j\}$, where the $t_i$ are listed in increasing order. 
Let us assume that $t_i$ is the $a_i$th smallest element of $U$. 
Then the {\em vertical complement} of $T$ with respect to $U$ is the set consisting of the $a_i$th largest elements of $U$, for all $i$. For instance, if $T=\{1,4,6\}$, and $U=\{1,2,3,4,6,8,9\}$, then the vertical complement of $T$ with respect to $U$ is $\{ 3,4,9\}$. Indeed, 
$T$ consists of the first, fourth, and fifth smallest elements of $U$, so its vertical complement with respect to $U$ consists of the first, fourth, 
and fifth largest elements of $U$. 

\begin{definition}
For $1\leq i\leq n$, let $c_i$ be the transformation on the set of all permutations $p=p_1p_2\cdots p_n$ that leaves the string $p_1p_2\cdots p_{i-1}$ unchanged, and replaces the string $p_ip_{i+1}\cdots  p_n$ by its complement relative to its 
underlying set.
\end{definition}

  Note that $c_1(p)=\overline{p}$ and $c_n(p)=p$ for all $p$. 

\begin{example} \label{first}  Let $p=315462$. Then $c_3(p)=314526$, while $c_5(p)=315426$.
\end{example}

\begin{proposition} \label{easysym} Let $n\geq 4$, and let $3\leq i\leq n-1$. Let $p$ be any permutation of length $n$. 
Then one of\/ $p$ and $c_i(p)$ has exactly one more alternating run than the other. 
\end{proposition}

\begin{proof} As $c_i$ does not change the number of runs of the string\break $p_1p_2\cdots p_{i-1}$ or the number of runs of 
the string $p_ip_{i+1}\cdots p_n$ and its image, all changes occur within the four-element string $p_{i-2}p_{i-1}p_ip_{i+1}$. 
There are only 24 possibilities for the pattern of these four entries, and it is routine to verify the statement for each of the possible 12 pairs.
In fact, checking the six pairs in which $p_{i-2}<p_{i-1}$ is sufficient, for symmetry reasons. 
\end{proof}

It follows immediately from the proposition that 
$z^{\text{run}(p)}+z^{\text{run}(c_i(p))}$ is divisible by $1+z$.

The following lemma is crucial for our purposes. 

\begin{lemma} \label{commutative}  Let $1\leq i\leq j-2\leq n-2$. Then, for all permutations $p$ of length $n$, the identity $c_i(c_j(p))=c_j(c_i(p))$ holds. 
\end{lemma}

\begin{proof}
Neither $c_i$ nor $c_j$ acts on any part of the initial segment\break $p_1p_2\cdots p_{i-1}$, so that segment, unchanged, will start both  $c_i(c_j(p))$ and $c_j(c_i(p))$.
The ending segment $p_jp_{j+1}\cdots p_n$ gets flipped twice by both $c_ic_j$ and $c_jc_i$, so in the end, the pattern of the last $n-j+1$ entries will be the same in  $c_i(c_j(p))$ and
 $c_j(c_i(p))$, because in both permutations it will be the same pattern as it was in $p$. The middle segment $p_ip_{i+1}\cdots p_j$ will get flipped once by both $c_ic_j$ and $c_jc_i$,
so on both sides the pattern of entries in positions $i,i+1,\dots ,j$ will be the complement of the pattern of $p_ip_{i+1}\cdots p_j$.  

Finally, the {\em set} of entries in the last $n-j+1$ positions is the same in both  $c_i(c_j(p))$ and $c_j(c_i(p))$, since both sets are equal to the vertical complement of the set
 $\{p_j,p_{j+1},\dots ,p_n\}$ with respect to the set $\{p_i,p_{j+1},\dots ,p_n\}$. 
\end{proof}

Note that $c_i(c_j(p))\neq p$, since the segment $p_i\cdots p_{j-1}$ is of length at least two, and gets flipped at least once. 


\begin{example} {\em  Continuing Example \ref{first}, we get that $c_3(c_5(315462))=c_5(c_3(315462))=314562$. } \end{example}

Now let $n\geq 4$ be any integer. If $n$ is even, 
let  \[\mathcal C_n=\{c_3, c_5,c_7,\dots ,c_{n-1}\} .\] 
If $n$ is odd, let  \[\mathcal C_n=\{c_3, c_5,c_7,\dots ,c_{n-2}\} .\] 
 In both cases, $\mathcal C_n$ consists of $m=\lfloor (n-2)/2 \rfloor$ operators. Each of these operators are involutions, and, 
by Lemma~\ref{commutative}, they pairwise commute. No  element of $\mathcal C_n$ can be generated by the other elements of 
$\mathcal C_n$. Therefore, the elements of $\mathcal C_n$  define a group $G_m \cong \Z_2^m$ that acts on the set of all permutations of length $n$. 
 Note that the action of the individual $c_i$ on the set of all permutations of length $n$ is independent in the following sense. 
If $p$ is a permutation and $c_i(p)$ has one more alternating run than $p$, then $c_j(c_i(p))$ also has one more alternating run than 
$c_j(p)$.


The action of $G_m$ on the set of all permutations of length $n$ creates orbits of size $2^m$. 

\begin{lemma} \label{orbits}
Let $A$ be any orbit of $G_m$ on the set of all permutations of length $n$. Then the equality
\[\sum_{p \in A} z^{\text{run}(p)} = z^a(1+z)^m \]
holds, where $a$ is a nonnegative integer. 
\end{lemma}

\begin{proof} Let $p\in A$. Going through $p$ from left to right, let us apply or not apply each element of $\mathcal C_n$ so as to minimize the
number of alternating runs of the obtained permutation. That is, if application of $c_i$ increases the number of alternating runs, then do not apply it,
if it decreases the number of alternating runs, then apply it. Let $q$ be the obtained permutation. Then we call $q$ the {\em minimal}
permutation in $A$, since, among all permutations in $A$, it is $q$ that has the smallest number of alternating runs. Now elements of $A$ 
with $i$ more alternating runs than $q$ can be obtained from $q$ by applying exactly $i$ elements of $\mathcal C_n$ to $q$. As there are
${\binom m  i}$ ways to choose $i$ such elements, our statement is proved by summing over $i$. 
\end{proof} 

\begin{theorem} \label{main} 
For $n\geq 4$, the equality \[R_n(z) = (1+z)^m \sum_{q} z^{\text{run}(q)} \]
holds, where the summation is over permutations $q$ that are minimal in their orbit under the action of $G_m$. Here
 $m=\lfloor (n-2)/2 \rfloor $.
\end{theorem}

\begin{proof} This follows from Lemma~\ref{orbits} by summing over all orbits. \end{proof}

\section{Longest alternating subsequences}
Following Richard Stanley \cite{stanley-m,stanley}, we say that an {\em alternating subsequence} in a permutation is a subsequence $a_1a_2 \cdots $ of entries,
not necessarily in consecutive positions, so that $a_1 > a_2 < a_3> \cdots $. Let $\text{as}(p)$ denote the length of the longest 
alternating subsequence of $p$. It is easy to see that, if $p=p_1p_2\cdots p_n$ is a permutation, and $p_1>p_2$, then $1+\text{run}(p) =
\text{as}(p)$, while, if $p_1<p_2$, then $\text{run}(p) =
\text{as}(p)$. In other words, if $AS_n(z)=\sum_{p \in S_n} z^{\text{as}(p)}$, then the equality 
\[AS_n(z) = \frac{(1+z)R_n(z)}{2} \] holds. Comparing this with Theorem~\ref{main}, it follows that $AS_n(z)$ is divisible by $(1+z)^{m+1}=
(1+z)^{\lfloor n/2 \rfloor}$ for all $n\geq 4$. We would like to point out that it is possible to prove this statement directly, by 
defining 
\[\mathcal C_n' =\mathcal C_n \cup \{c_1\},\]
and then repeating the argument that was used to prove Lemma~\ref{orbits}.  

\section{Numerical Data and Further directions} \label{numerical}
%
The first few polynomials $R_n(z)$ are the following. 
\begin{itemize}
\item $R_1(z)=z$,
\item $R_2(z)=2z$,
\item $R_3(z)=4z^2+2z$,
\item $R_4(z)=2z(5z+1)(z+1)$,
\item $R_5(z)=2z(16 z^2+ 13 z + 1)(z + 1)$,
\item $R_6(z)=2z(61 z^2+ 28 z + 1)(z+1)^2$,
\item $R_7(z)=2z(272z^3+297z^2+60z+1)(z+1)^2$,
\item $R_8(z)=2z(1385z^3+1011z^2+123z+1)(z+1)^3$,
\item $R_9(z)=2z(7936z^4+10841z^3+3651z^2+251z+1)(z+1)^3$,
\item $R_{10}(z)=2z(50521z^4+50666z^3+11706z^2+506z+1)(z+1)^4$.
\end{itemize}

\medskip
It would be interesting to find other applications for this group action in counting permutations according to various statistics. It would also be interesting to find another example for the significance of 
the $n!/2^m$ minimal permutations defined in the proof of Lemma~\ref{orbits}. 

\section*{Acknowledgment}

I am indebted to my anonymous referees for a careful reading of the manuscript, interesting suggestions, and providing the numerical data for Section~\ref{numerical}. 
 My research is partially supported by Simons Collaboration Grant  421967.

\begin{thebibliography}{99}
\bibitem{bona-ehr} M. B\'ona, R. Ehrenborg, A combinatorial proof of the log-concavity of the numbers of permutations with $k$ runs.
{\em J. Combin. Theory Ser.~A} {\bf 90} (2000), 293--303.
\bibitem{combperm} M. B\'ona, Combinatorics of Permutations, Second Edition, CRC Press, 2012. 
\bibitem{stanley-m} R. P. Stanley, 
Longest alternating subsequences of permutations, 
{\em Michigan Math. J.} {\bf 57} (2008), 675--687.
\bibitem{stanley} R. P. Stanley, A survey of alternating permutations,
{\em Contemporary Mathematics} {\bf 531} (2010), 165--196.
\bibitem{wilf} H.\ Wilf, 
              Real zeroes of polynomials that count runs and
               descending runs, unpublished manuscript, 1999.
\end{thebibliography}

\end{document}