\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P3.63}{24(3)}{2017}
\usepackage{amsmath, amssymb, amsfonts, amsthm, array, enumerate, float, lineno, mathrsfs, subcaption, tikz}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
\newcolumntype{r}[1]{>{\raggedright\arraybackslash}m{#1}}
\DeclareMathOperator{\av}{Av}
\renewcommand{\S}{\mathcal{S}}
\newcommand{\C}{\mathcal{C}}
\newcommand{\A}{\mathcal{A}}
\newcommand{\W}{\mathcal{W}}
\newcommand{\U}{\mathcal{U}}
\newcommand{\CU}{\mathcal{CU}}
\newcommand{\CA}{\mathcal{A}^{\mathcal{C}}}
\newcommand{\ds}{\displaystyle}
\DeclareMathOperator{\Mod}{mod}
\DeclareMathOperator{\inv}{inv}
\DeclareMathOperator{\peaks}{peaks}
\DeclareMathOperator{\ipeaks}{ipeaks}
\DeclareMathOperator{\ides}{ides}
\DeclareMathOperator{\lni}{lni}
\DeclareMathOperator{\exc}{exc}
\DeclareMathOperator{\iexc}{iexc}
\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\Des}{Des}
\DeclareMathOperator{\rlmax}{rlmax}
\DeclareMathOperator{\rlmin}{rlmin}
\DeclareMathOperator{\lrmax}{lrmax}
\DeclareMathOperator{\st}{st}
\usepackage{array,float,bm,subcaption,tikz}
%\def\arraystretch{1.5}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{cor}[theorem]{Corollary}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{defn}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}
\newtheorem{remark}[theorem]{Remark}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\newcommand{\todo}[1]{\vspace{2 mm}\par\noindent
% \marginpar[\flushright\textsc{ToDo}]{\textsc{ToDo}}\framebox{\begin{minipage}[c]{\textwidth}
%\tt #1 \end{minipage}}\vspace{2 mm}\par}
\title{Unimodal Permutations and\\ Almost-Increasing Cycles}
\author{Kassie Archer \qquad L.-K. Lauderdale\\
\small Department of Mathematics\\[-0.8ex]
\small University of Texas at Tyler\\[-0.8ex]
\small Tyler, TX, U.S.A.\\
\small\tt \{karcher,llauderdale\}@uttyler.edu}
\date{\dateline{Apr 6, 2017}{Sep 8, 2017}{Sep 22, 2017}\\
\small Mathematics Subject Classifications: 05A05, 05A15, 05A19}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\maketitle
\begin{abstract}
In this paper, we establish a natural bijection between the almost-increasing cyclic permutations of length $n$ and unimodal permutations of length $n-1$. This map is used to give a new characterization, in terms of pattern avoidance, of almost-increasing cycles. Additionally, we use this bijection to enumerate several statistics on almost-increasing cycles. Such statistics include descents, inversions, peaks and excedances, as well as the newly defined statistic called low non-inversions. Furthermore, we refine the enumeration of unimodal permutations by descents, inversions and inverse valleys. We conclude this paper with a theorem that characterizes the standard cycle notation of almost-increasing permutations.
\bigskip\noindent \textbf{Keywords:} permutation statistics, cyclic permutations, unimodal permutations, almost-increasing permutations
\end{abstract}
\section{Introduction}
So-called \textit{almost-increasing} permutations were the subject of prior research, and in Section~\ref{SECTION:PATTERN AVOIDANCE} below we define them in a precise sense. These permutations were introduced by Knuth \cite{KNUTH73} in the context of sorting algorithms and were enumerated using generating functions. Elizalde \cite{ELIZALDE11B} showed that these permutations have a characterization in terms of pattern avoidance and presented a bijective proof for the enumeration for almost-increasing permutations. This bijection was constructed between the set of almost-increasing permutations and the set of colored Motzkin paths (a generalization of Dyck paths). Elizalde further used this bijection to refine the enumeration with respect to several permutation statistics, including number of cycles, number of excedances, number of fixed points and number of inversions. Our focus in this paper, is on almost-increasing cyclic permutations, i.e., those almost-increasing permutations comprised of a single cycle. Recently, cyclic permutations received a great deal of attention in connection with pattern avoidance and permutation statistics; we discuss such connections in Section~\ref{SECTION:CYCLES}.
%; these authors enumerate specific types of permutations in certain grid classes.
In this paper, we establish a natural bijection between the almost-increasing cyclic permutations of length $n$ and unimodal permutations of length $n-1$. This map is used to give a new characterization of almost-increasing cycles in terms of pattern avoidance for the standard cycle notation. Furthermore, this bijection allows us to enumerate several statistics on almost-increasing cycles, including descents, peaks, excedances, inversions, and the newly defined statistic called low non-inversions. Table~\ref{table:SUMMARY TABLE} summarizes the results obtained In this paper, on the refinement of the enumeration for almost-increasing cycles with respect to these statistics; the proofs of such results can be found in Sections~\ref{sec:STATISTICS ON UP} and~\ref{sec:STATISTICS ON AIC}. Let $p_{\leq n}(k)$ denote the number of partitions of the integer $k$ into parts of size at most $n$. We note that the number of almost-increasing cycles with $k$ excedances can also be recovered from Theorem 6.1 in \cite{ELIZALDE11B}.
\begin{table}[H]
\centering
\begin{tabular}{|m{3.7cm}|m{4.2cm}|m{4cm}|r{2.2cm}|}\hline
{\bf Unimodal Permutations on} \bm{$[n-1]$} & {\bf Almost-Increasing Cycles on} $\bm{[n]}$ & {\bf Enumeration} & {\bf Results} \\ \hline\hline
$k-1$ inverse valleys & $k$ descents & $\displaystyle\binom{n-1}{2k-1}$ & Theorem~\ref{thm:uni inv val} Theorem~\ref{thm:AI DESCENTS} \\ \hline
& $k$ peaks & \vspace{.1cm} $\displaystyle\binom{n-1}{2k}$\vspace{.1cm} & Corollary~\ref{cor: AI PEAKS} \\ \hline
$k$ inversions & $k$ low non-inversions & $p_{\leq n-2} (k)$ & Theorem~\ref{thm: UNI PARTITIONS} Theorem~\ref{thm: AI PARTITIONS} \\ \hline
$k-1$ ascents & $k$ excedances & \vspace{.1cm}$\displaystyle\binom{n-2}{k-1}$\vspace{.1cm} & Theorem~\ref{thm:AI EXCEDANCES} \\ \hline
& $k$ inversions & \vspace{.1cm}$\begin{cases} 2^{n-2}, & \text{if } k=n-1 \\ 0, &\text{otherwise} \end{cases} $ \vspace{.1cm}& Theorem~\ref{thm: AI INVERSIONS} \\ \hline
\end{tabular}
\caption{Statistics on unimodal permutations and almost-increasing cycles}
\label{table:SUMMARY TABLE}
\end{table}
Pattern avoidance in terms of a permutation's one-line notation is well-studied; there are numerous articles that explored statistics on permutations avoiding a prescribed pattern or a set of patterns, including descents in \cite{BARNABEI2012,BARNABEI14,REIFEGERSTE2003}, excedances in \cite{BLOOM2009,ELIZALDE2012}, inversions in \cite{DDJSS2012, SAGANSAVAGE2012, CHENMEIWANG2015} and peaks in \cite{BAXTER2014}. Additionally, permutation statistics on permutations with a prescribed cycle type were studied, as discussed in Section \ref{SECTION:CYCLES}. There are also some results regarding occurrences of patterns in the cycle notation of a permutation, see for example \cite{DEUTSCHELIZALDE2011}, among others. However, analyzing how patterns avoided in a permutation's one-line can determine patterns avoided in the permutation's standard cycle notation is relatively unexplored, and little is known about this cycle structure. We conclude this paper with a discussion of the relationship between a permutation's one-line notation and its standard cycle notation. These results, seen in Theorem~\ref{thm: AI STANDARD FORM}, completely characterize almost-increasing permutations written in standard cycle notation.
\section{Background}\label{BACKGROUND}
Let $\S_n$ be the set of permutations on $[n] = \{1,2,\ldots, n\}$. A permutation $\pi\in\S_n$ can be written in its one-line notation as $\pi =\pi_1\pi_2\ldots\pi_n$, where $\pi_i=\pi(i)$; we make use of both the notations $\pi_i$ and $\pi(i)$ throughout the remainder of this paper. Alternatively, a permutation $\pi\in\S_n$ can be written in cycle notation as a product of disjoint cycles of the form $(i, \pi(i), \pi^2(i), \ldots, \pi^{k-1}(i))$, where $\pi^k(i) = i$. A permutation is in \textit{standard cycle notation} if each cycle is written with its smallest element first and the cycles appear in increasing order with respect to their smallest element. For instance, the standard cycle notation of the permutation $\pi = 4361527 \in \S_7$ is $(14)(236)(7)$. A permutation composed of a single $n$-cycle is \textit{cyclic}, and we let $\C_n$ denote the set of cyclic permutations (or \textit{cycles} for short).
\subsection{Pattern avoidance} \label{SECTION:PATTERN AVOIDANCE}
For $mi$. Elizalde \cite{ELIZALDE11B} characterized these permutations as avoiding the patterns $3412,\ 3421,\ 4321$ and $4312$. The set of almost-increasing permutations in $\S_n$ is denoted by $\A_n$, and the set of almost-increasing cyclic permutations in $\C_n$ is denoted by $\CA_n$.
\subsection{Statistics on permutations}\label{SUBSEC: STATS}
Let $\pi \in \S_n$. The permutation $\pi$ has a \textit{descent} at position $i$ if $\pi_i>\pi_{i+1}$. The \textit{descent set} of $\pi$ is
\[\Des(\pi)=\{ i \in [n-1]: \pi_i > \pi_{i+1}\},\]
and the \textit{descent number}, denoted by $\des(\pi)$, is $|\Des(\pi)|$. An \textit{inversion} of $\pi$ is a pair $(i,j)$ such that $i\pi_j$, and a \textit{non-inversion} of $\pi$ is a pair $(i,j)$ such that $ii$; the excedances of the permutation $134569782$ are 2, 3, 4, 5 and 6, and the values of these excedances are 3, 4, 5, 6 and 9, repsectively. On the other hand, a \textit{non-excedance} of $\pi$ is a position $i \in[n]$ such that $\pi_i\leq i$. The permutation $\pi$ has a \textit{peak} at position $i$ if $\pi_{i-1}<\pi_i$ and $\pi_{i+1}<\pi_i$. A permutation $\pi$ has a \textit{valley} at position $i$ if $\pi_i<\pi_{i-1}$ and $\pi_i<\pi_{i+1}$, and \textit{inverse valley} at position $i$ if $\pi_i$ is a valley of the inverse of $\pi$. The permutation $134569782$ has peaks at positions $5$ and $7$, a valley at position $7$, and an inverse valley at position $2$. A \textit{consecutive run} of a permutation is a maximal increasing contiguous subsequence $\pi_i\pi_{i+1}\ldots\pi_{i+k}$ of consecutive integers. For example, the consecutive runs of $134569782$ are $1$, $3456$, $9$, $78$ and $2$. If $\pi_i\pi_{i+1}\ldots\pi_{i+k}$ is a consecutive run, then the position $i$ is the \textit{start} of the run and the position $i+k$ is the \textit{end} of the run.
We conclude this subsection by establishing a new statistic on permutations; define a \textit{low non-inversion} of a permutation $\pi\in \S_n$ to be a pair $(i,j)$ such that $\pi_i*1$ and $\hat\pi(n)\hat\pi(i)>1$, then $\hat\pi(i)>\hat\pi^2(i)$. Set $j= \hat\pi(i)$, and towards a contradiction assume that $i\hat\pi(j)$. By definition of an almost-increasing function, there is exactly one $k\leq j-1$ such that $\hat\pi(k)>j-1$, namely $\hat\pi(i) = j$. Our assumption $j>\hat\pi(j)$ implies there is no element $k\leq j$ for which $\hat\pi(k)>j$. Therefore, $[j]$ maps to itself under the permutation $\hat\pi$. Since $jj>n$ and $j<\hat\pi(j)$. Because $\hat\pi$ is almost-increasing there is exactly one $k\leq j$ such that $\hat\pi(k)>j$, namely $j$ itself. This, along with the fact that $\hat\pi^{-1}(j) = i>j$, imply there is no element $k\leq j-1$ with $\hat\pi(k)>j-1$. Therefore, $[j-1]$ maps to itself under $\hat\pi$, implying the permutation is not cyclic, a contradiction. Thus $\varphi(\CA_n) \subseteq \U_{n-1}$.
It remains to show that all of $\U_{n-1}$ is obtained in the image of $\varphi$. For each $\sigma \in \U_{n-1}$, $\hat\pi=\varphi^{-1}(\sigma)$ is a cyclic permutation, and thus each element of $\hat\pi$ is of the form $\hat\pi^j(1)$ with $0\leq j \leq n-1$. If $\hat\pi^k(1) = n$, then $\hat\pi^j(1)<\hat\pi^{j+1}(1)$ when $0\leq j\hat\pi^{j+1}(1)$ when $k\leq ji$, the value of any previous excedance is less than or equal to $i$. It follows that for any $i \in [n]$, there is at most one element less than or equal to $i$ whose image is larger than $i$, and so $\hat\pi$ is almost-increasing. Hence $\varphi$ is a bijection between $\CA_n$ and $\U_{n-1}$, as desired.
\end{proof}
\begin{remark}
The proof of Theorem~\ref{thm:main} relies on the following geometric intuition. For any almost-increasing cycle, tracing the cycle structure clockwise yields a path that crosses the diagonal once. This crossing corresponds to the peak of the unimodal permutation obtained via $\varphi$. Notice that on the right in Figure~\ref{fig: PICS OF PERMS}, we can observe this phenomenon illustrated by the green line.
\end{remark}
The bijection $\varphi$ given in Theorem~\ref{thm:main} provides the following enumeration for almost-increasing cyclic permutations.
\begin{cor}
For $n\geq 2$, the number of almost-increasing cycles on $[n]$ is equal to $2^{n-2}$.
\end{cor}
This corollary also follows from Theorem 6.1 in \cite{ELIZALDE11B}, which gives a generating function for the number of almost-increasing permutations on $[n]$ with $k$ cycles, $i$ fixed points and $j$ excedances.
We conclude this section with a proposition that gives a new, simpler characterization of almost-increasing cyclic permutations in terms of pattern avoidance. It is well-known that 321-avoiding permutations are composed of two increasing, interleaved sequences. As a result the forthcoming proposition follows from the last paragraph of the proof of Theorem~\ref{thm:main}.
\begin{prop}
For $n\geq 1$, $\C_n(3412, 3421, 4312, 4321) = \C_n(321, 3412)$.
\end{prop}
We continue by proving some statistics on unimodal permutations.
\section{Statistics on unimodal permutations}\label{sec:STATISTICS ON UP}
%\todo{Rewrite in terms of ``consecutive number patterns''?}
In this section, we enumerate unimodal permutations according to the number of inverse valleys, number of inversions and number of descents.
\begin{theorem}\label{thm:uni inv val}
The number of unimodal permutations on $[n]$ with $k$ inverse valleys is equal to $\binom{n}{2k+1}$.
\end{theorem}
\begin{proof}
We establish a bijection between unimodal permutations with $k$ inverse valleys and subsets of $[n]$ of size $2k+1$. Suppose $\sigma$ is a unimodal permutation with $k$ inverse valleys, and let $\sigma=\sigma_In\sigma_D$, where $\sigma_I$ is the increasing leg of $\sigma$ and $\sigma_D$ is the decreasing leg of $\sigma$, neither of which include the peak $n$. Notice that if there is an $2\leq i\leq n$ so that $\sigma^{-1}(i-1)>\sigma^{-1}(i)<\sigma^{-1}(i+1)$, then $i$ appears before $i+1$ in $\sigma$, and thus $i$ must appear in $\sigma_I$. Since $i-1$ also appears after $i$ in $\sigma$, $i-1$ must appear in $\sigma_D$. In fact, whenever an element $\sigma_j=i$ appears in $\sigma_I$, with $i-1$ appearing in $\sigma_D$, the position $j$ is a position of an inverse valley.
Notice that if $\sigma_1 = 1$, then there are $k+1$ consecutive runs of the segment $\sigma_I$ and if $\sigma_1 \neq 1$, there are $k$ consecutive runs of $\sigma_I$. Similarly, there are $k$ consecutive (decreasing) runs of $\sigma_D$.
Construct a set $S_\sigma$ by appending the following elements to $S_\sigma$:
\begin{enumerate}
\item $\ell:=\sigma^{-1}(n)$;
\item the first $k$ elements $j<\ell$ such that $\sigma_j<\sigma_{j+1}-1$ or $\sigma_{j+1}=n$ (by the previous paragraph there are either $k$ or $k+1$ such elements); and%are the ends of the first $k$ consecutive runs of the permutation $\sigma_1\sigma_2\ldots \sigma_{\ell-1}$; and % (noting that having $k$ inverse valleys implies that there are exactly $k$ or $k+1$ consecutive runs in the increasing part of the permutation), and
\item the $k$ elements $j>\ell$ such that $\sigma_j<\sigma_{j-1}-1$.
\end{enumerate} %Since there are $k$ inverse valleys, there are $k$ or $k+1$ such consecutive runs of $\pi_1\pi_2\ldots \pi_{\ell-1}$ and exactly $k$ elements $j>\ell$ satisfying $\sigma_j<\sigma_{j-1}-1$.%(because of the run that might contain $n-1$)
We claim this set $S$ uniquely determines the permutation $\sigma$. Specifically, order $S$ in increasing order and take the $(k+1)$st element of $S$, say $\ell$, to be the position of the peak. Construct the permutation $\sigma$ as follows. Start with $n$ at position $i$, decrease by one each time, and place a new label in each position starting from the position of $n$ and working away, switching sides exactly when a position in $S$ is to be encountered. If $\ell+1$ is an element of $S$, start with $n-1$ on the left of $n$, and place it to the right otherwise. This clearly returns the permutation $\sigma$.
\end{proof}
Below we give two examples of the bijection given in the proof of Theorem~\ref{thm:uni inv val}.
\begin{example}
The permutation $\sigma=345789621 \in \U_9$ has two inverse valleys at positions $1$ and $4$ because $\sigma^{-1}$ has valleys at positions $3$ and $7$. Since $\sigma^{-1}(9)=6$, we have $6 \in S$. The positions $3$ and $5$ are the ends of the first two consecutive runs of $34578$; as a result, we have $3, 5 \in S$. Finally, $\sigma_7<\sigma_6-1$ and $\sigma_8<\sigma_7-1$ so that $7,8 \in S$. Therefore $S=\{3,5,6,7,8\}$ is the set associated to the permutation $\sigma=345789621$.
We can recover $\sigma$ by noting that the 3rd element of the set, namely 6, is the position of the peak and thus $\sigma_6=9$. Since $7 \in S$, the value $n-1=8$ will appear to the left of $9$ and thus $\sigma_5 = 8$, since $4 \not \in S$, we keep going and label $\sigma_4 = 7$. However, $3\in S$ and so we switch to the other side of the peak and label $\sigma_7 = 6$. Since $8\in S$, we switch to the other side and label $\sigma_1\sigma_2\sigma_3 = 345$. Since we have reached the end, we switch back to the other side and label $\sigma_8\sigma_9=21$.\end{example}
\begin{example}
The permutation $145679832 \in \U_9$ has one inverse valley at position 2 and is associated to the set $S=\{1,6,8\}$.
\end{example}
%\begin{theorem}
%The number of unimodal permutations with $k$ occurrences of the ``consecutive number pattern'' $1243$ is equal to $\frac{n-1}{2k}$.
%\end{theorem}
\begin{theorem}\label{thm: UNI PARTITIONS}
The number of unimodal permutations on $[n]$ with $k$ inversions is equal to the number of partitions of $k$ into distinct parts of size at most $n-1$.
\end{theorem}
\begin{proof}
We establish a bijection between unimodal permutations on $[n]$ with $k$ inversions and the number of partitions of $k$ into distinct parts of size at most $n-1$. Suppose $\sigma\in\U_n$ has $k$ inversions. Define $D = \{i \in [n] : i>\sigma^{-1}(n)\}$, that is, $D$ is the set of consecutive integers $\{j, j+1, j+2, \ldots, n\}$ where $\sigma_{j-1}=n$. Since the permutation $\sigma$ is unimodal, $D$ is the set of indices associated to the decreasing leg of $\sigma$. Notice that if $(m,i)$ is an inversion, that is, $m**\sigma_i$, then $i \in D$. Moreover, for every $i \in D$, there is some inversion of this form; for example, $(m,i)=(\sigma^{-1}(n),i)$ is such and inversion.
Let $\inv_\sigma(i)$ be the number of inversions of $\sigma$ that are of the form $(m,i)$ for some $m$. Consider the partition $\lambda$ of the the number of inversions $k$ with parts $\inv_\sigma(i)$ for $i \in D$. Notice that for two elements of $i_1, i_2 \in D$, if $i_1\sigma_{i_2}$. Therefore the elements of $\lambda$ are increasing and thus distinct. As a result the partition obtained is a partition of $k$ into distinct elements of size at most $n-1$.
We can see that this map is invertible as follows. Let $\lambda$ be a partition of $k$ into distinct parts of size at most $n$ listed in increasing order. The number of parts of $\lambda$ determines the length of the decreasing leg of $\sigma$. The elements of the decreasing leg, which uniquely determines the permutation $\sigma$, are given by $\sigma_j = n-\lambda_1, \sigma_{j+1} = n-\lambda_2, \ldots, \sigma_n = n-\lambda_{n-j+1}$.
\end{proof}
We continue by giving an example of the bijection detailed in the proof of Theorem~\ref{thm: UNI PARTITIONS}.
\begin{example}
Consider the permutation $\sigma= 345789621\in \U_9$, which has 18 inversions. Since $\sigma^{-1}(9) = 6$, $D =\{7,8,9\}$. Notice that $\inv_\sigma(7) = 3, \inv_\sigma(8) = 7$ and $\inv_\sigma(9)=8$. Therefore this permutation is associated to the partition of 18 into distinct parts of size at most 8: $\lambda = 3+7+8$. Reversing this process, we see that the decreasing leg of $\sigma$ is $\sigma_D =\sigma_7,\sigma_8,\sigma_9 = (9-3), (9-7), (9-8) = 6,2,1$.
\end{example}
The next proposition is immediate because all descents of a permutation in $\U_n$ occur in the decreasing leg of the permutation, and thus the unimodal permutations with $k$ descents are exactly those with $\sigma_{n-k} = n$.
\begin{prop}\label{thm: UNI DESCENTS}
The number of unimodal permutations on $[n]$ with $k$ descents is equal to $\binom{n-1}{k}$.
\end{prop}
In the next section, we consider statistics on almost-increasing cyclic permutations.
\section{Statistics on almost-increasing cycles}\label{sec:STATISTICS ON AIC}
In this section, we establish a refinement of the bijection $\varphi$, given in Section~\ref{SEC: VARPHI}, in order to enumerate almost-increasing cycles with respect to certain statistics.
\begin{theorem}\label{thm:AI DESCENTS}
For $n\geq 2$, the number of almost-increasing cyclic permutations on $[n]$ with $k$ descents is equal to $\binom{n-1}{2k-1}$.
\end{theorem}
\begin{proof}
We will show that if $\sigma \in \U_{n-1}$ has $k-1$ inverse valleys, then $\varphi^{-1}(\sigma)$ is an almost-increasing cycle on $[n]$ with $k$ descents. Let $\sigma \in \U_{n-1}$ with $k-1$ inverse valleys, and suppose $\pi=1 \oplus \sigma$. Notice that $\sigma$ and $\pi$ have the same number of inverse valleys because appending $1$ to $\sigma$ does not introduce a new inverse valley. Let $\pi = \pi_In\pi_{D}$, where $\pi_I$ is the increasing leg of $\pi$ and $\pi_D$ is the decreasing leg of $\pi$, neither of which include the peak $n$. The positions of the valleys in $\pi^{-1}$ are exactly the values at the start of consecutive runs in $\pi_I$, with the exception of $\pi_1=1$ (as detailed in the proof of Theorem \ref{thm:uni inv val}).
If $i$ is in $\pi_I$ and $i+1$ is in $\pi_D$, then $\hat\pi_i> i$ and $\hat\pi_{i+1}*