\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}
\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}
\usepackage{color}
\usepackage{fullpage}
\usepackage{float}
\usepackage{graphics}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}}
\usepackage{algorithm}
\usepackage{algorithmic}
\usepackage{enumerate,tikz,listings,array,longtable}
\usetikzlibrary{shapes,arrows,chains}
\usepackage{pgf}
\DeclareMathOperator{\Flatten}{Flatten}
\DeclareMathOperator{\LrMax}{LrMax}
\DeclareMathOperator{\LrMl}{LrMl}
\DeclareMathOperator{\lrmax}{lrmax}
\DeclareMathOperator{\LwMp}{WLrMax}
\DeclareMathOperator{\RsP}{RsP}
\DeclareMathOperator{\SP}{SP}
\DeclareMathOperator{\LwM}{LwM}
\DeclareMathOperator{\lwmp}{wlrmax}
\DeclareMathOperator{\Rlmin}{RlMin}
\DeclareMathOperator{\RGF}{RGF}
\DeclareMathOperator{\blocks}{bl}
\DeclareMathOperator{\run}{run}
\DeclareMathOperator{\rlmin}{rlmin}
\begin{document}
\begin{center}
\includegraphics[width=4in]{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Merging-Free Partitions and\\
\vskip .1in
Run-Sorted Permutations
}
\vskip 1cm
\large
Fufa Beyene\\
Department of Mathematics\\ Addis Ababa University\\
Addis Ababa 1176\\ Ethiopia\\
\href{mailto: fufa.beyene@aau.edu.et}{\tt fufa.beyene@aau.edu.et}\\
\ \\
Roberto Mantaci \\
IRIF \\
Universit\'e de Paris \\
8, Place Aur\'elie \\
Nemours 75013\\ France\\
\href{mailto: mantaci@irif.fr}{\tt mantaci@irif.fr}
\end{center}
\vskip .2in
\begin{abstract}
In this paper, we study merging-free partitions and run-sorted permutations. We give a combinatorial proof of a conjecture of
Nabawanda, Rakotondrajao, and Bamunoba.
We describe the distribution of the statistics of runs and right-to-left minima over the set of run-sorted permutations, and we give the exponential generating function for their joint distribution. We show that the distribution of right-to-left minima is the shifted distribution of the Stirling numbers of the second kind. We also prove that the number of non-crossing merging-free partitions is a power of 2. We use one of the constructive proofs given in the paper to implement an algorithm for
the exhaustive generation of run-sorted permutations by the number of runs.
\end{abstract}
\section{Introduction}
Given a non-empty finite subset $A$ of positive integers, a \emph{set partition} $P$ of $A$ is a collection of disjoint, non-empty subsets of $A$, called \emph{blocks} of $A$, such that every element of $A$ belongs to exactly one subset \cite{Bo,Ma}. We shall use the notation $[n]:=\{1, 2, \ldots, n\}$, where $n$ is a fixed positive integer.
It is well known that the set partitions over $[n]$ and set partitions over $[n]$ having $k$ blocks are counted by the Bell numbers, $b_n$, and Stirling numbers of the second kind, $S(n,k)$, respectively \cite{Bo,Ro,St1}.
Mansour \cite{Ma} defined the \emph{block representation} of a set partition where the elements in a block are arranged in increasing order, and the blocks are arranged in increasing order of their first elements. Mansour also gave a way to encode a set partition (in its block representation) by its \emph{canonical form}, i.e., every integer is encoded by the number of the block it belongs to. We note that canonical forms of set partitions coincide with the so-called \emph{restricted growth functions} ($\RGF$).
Callan \cite{Ca} introduced the ``flattening'' operation ($\Flatten$) on set partitions, which acts in such a way that a permutation $\sigma$ is obtained from a set partition $P$ by removing the separators enclosing the different blocks of $P$ in its block representation.
For example, the block representation of the set partition $P=\{1, 2, 6\}, \{3\}, \{4, 8\}, \{5, 7\}$ is $P=126/3/48/57$, and so we remove the separators ``/'' and obtain the permutation $\sigma=12634857$. As a result of Callan's work, such objects have been receiving attention from different researchers, and several new findings are emerging \cite{Al-Na,Ma-Sh-Wa,Na-Ra}.
In the literature, permutations obtained this way are sometimes called ``flattened partitions''. We found this term somewhat confusing because these objects are permutations and not partitions; consequently, since the runs of the resulting permutations are sorted by the increasing values of their respective minima, we chose to adopt the term {\em run-sorted permutations} already used by Alexandersson and Nabawanda \cite{Al-Na}. Run-sorted permutations are counted by the shifted Bell numbers \cite{Na-Ra}.
The same permutation can be obtained by flattening several set partitions. For instance, the permutation $\sigma=12634857$ can also be obtained by flattening the set partition $P'=126/348/57$. Among all the set partitions having the same $\Flatten$, we distinguish the only one whose number of blocks is the same as the number of runs of the permutation obtained by flattening it (this is the set partition $P'$ for the permutation $\sigma$). For obvious reasons we named these objects {\em merging-free partitions}. The $\Flatten$ operation clearly becomes injective and hence is a bijection if restricted to the set of merging-free partitions.
In this article, we study some properties of run-sorted permutations as well as of merging-free partitions and their canonical forms, we compute the distribution of the number of runs and the number of right-to-left minima on these sets, we relate these classes to the class of separated partitions, we study non-crossing merging-free partitions, and we provide an exhaustive generation algorithm for the run-sorted permutations partitioned by the number of runs. In particular, in Section \ref{secflatrun}, we give a characterization of the canonical forms of merging-free partitions, and we show that they can be bijectively related to $\RGF$s of one size smaller.
In Section \ref{sec3}, we give a combinatorial bijective proof of a recurrence relation in Theorem \ref{rrNaRa} satisfied by run-sorted permutations over $[n]$ having $k$ runs, a recurrence relation that was conjectured by Nabawanda et al.\ \cite{Na-Ra}. We also give the interpretation of the proof of the same result by working on the canonical forms of merging-free partitions.
In Section \ref{secrlmin}, we prove that the distribution of right-to-left minima over run-sorted permutations is the same as the distribution of the number of blocks over set partitions of one size smaller (and also given by the shifted Stirling number of the second kind). We refine the recurrence relation satisfied by the number of run-sorted permutations over $[n]$ having $k$ runs by counting these permutations by the number of runs and by the number of right-to-left minima simultaneously, and we obtain an exponential generating function for the associated three-variables formal series. Munagi \cite{Mu} proved that the set partitions over $[n]$ having $k$ blocks such that no two consecutive integers are in the same block are also counted by the shifted Stirling numbers of the second kind. So, in this section, we also show that these partitions bijectively correspond to run-sorted permutations over $[n]$ having $k$ right-to-left minima.
The set of non-crossing partitions is a Catalan enumerated object introduced in the founding work of Becker \cite{Be} and later deeply studied by different eminent scholars, such as Kreweras and Simion \cite{Kr, Si}. In Section \ref{secNoncross}, we present the non-crossing merging-free partitions. We enumerate them according to their number of blocks, and we show that the total number of such partitions is a power of $2$.
Finally, Section \ref{secalgo} presents an exhaustive generation algorithm for the run-sorted permutations partitioned by the number of runs, based on the recurrence relation proved in Theorem \ref{rrNaRa} and using the classical dynamic programming techniques.
\subsection{Definitions, notation, and preliminaries}
\begin{definition}
A \textit{set partition} $P$ of $[n]$ is defined as a collection $B_1, \ldots, B_k$ of nonempty disjoint subsets $[n]$ such that $\cup_{i=1}^kB_i=[n]$. The subsets $B_i$ are referred to as ``blocks''.
\end{definition}
\begin{definition}
The \emph{block representation} of a set partition $P$ is $P=B_1/\cdots/B_k$, where the blocks $B_1, \ldots, B_k$ are sorted in such way that $\min (B_1) < \min (B_2) <\cdots < \min (B_k)$ and the elements of every block are arranged in increasing order.
\label{def1}
\end{definition}
We always write set partitions in their block representations. We let $\SP(n)$ denote the set of all set partitions over $[n]$ and $b_n=|\SP(n)|$, the $n$-th Bell number.
\begin{definition}
The \emph{canonical form} of a set partition of $[n]$ is an $n$-tuple indicating the block in which each integer occurs, i.e., $f= f(1)f(2)\cdots f(n)$ such that $j\in B_{f(j)}$ for all $j\in[n]$.
\end{definition}
\begin{example}
If $P=138/2/47/56\in\SP(n)$, then its canonical form is $f=12134431$.
\end{example}
\begin{definition}
A \emph{restricted growth function} $(\RGF)$ over $[n]$ is a function $f~:[n]\mapsto[n]$, where $f=f(1)\cdots f(n)$ such that $f(1)=1$ and $f(i) \leq 1+\max\{f(1),\ldots, f(i{-}1)\}$ for $2\leq i\leq n$, or equivalently, such that the set $\{f(1), f(2), \ldots, f(i)\}$ is an integer interval for all $i\in[n]$.
\end{definition}
The canonical forms of set partitions are exactly the restricted growth functions ($\RGF$). We let $\RGF(n)$ denote the set of all restricted growth functions over $[n]$. We write $f\in \RGF(n)$ as a word $f_1f_2\cdots f_n$ over the alphabet $[n]$, where $f_i=f(i)$. We define the set of
left-to-right maxima of $f$ by
$$\LrMax(f)=\{i~: f_i>f_j,\ 1\leq i \leq n,\ j*i\},$$ and we use the notation $\rlmin(\pi):=|\Rlmin(\pi)|$.
\begin{definition}
A maximal increasing subsequence of consecutive letters of a permutation $\pi$ is called a \emph{run}.
\end{definition}
\begin{definition}\cite{Ca}
A \emph{flattening} of a set partition is an operation by which we obtain a permutation from the set partition $P=B_1/\cdots/B_k$ by concatenating its blocks. We denote the resulting permutation by $\pi=\Flatten(P)$.
\end{definition}
If a permutation is obtained by flattening a set partition, then its runs are ordered in such a way that the minima of the runs are increasing, therefore, we call all permutations in $\Flatten(\SP(n))$ \emph{run-sorted permutations}. We let $\RsP(n):=\Flatten(\SP(n))$ and $r_n:=|\RsP(n)|$.
\begin{definition}
A \emph{merging-free partition} is a set partition $P=B_1/\cdots/B_k$
such that $\max(B_i)>\min(B_{i+1})$
for $1\le i\le k-1$ .
\end{definition}
\begin{remark}
Merging-free partitions over $[n]$ and run-sorted permutations over $[n]$ are in bijection, because the restriction of $\Flatten$ to the merging-free partitions is a bijection.
\end{remark}
\begin{proposition} \cite[Section 4]{Na-Ra}
\label{prop0}
The number of set partitions over $[n]$ and the number of run-sorted permutations over $[n+1]$ (and therefore, the number of merging-free partitions over $[n+1]$) are equal. That is, $r_{n+1}=b_n$ for all $n\geq0$.
\end{proposition}
To prove the above result, the authors provided a bijection $\alpha:\SP(n)\mapsto\RsP(n+1)$, which can be described as follows. Let $P=B_1/\cdots/B_k\in\SP(n)$. Then $\pi=\alpha(P)$ is constructed as follows: move each minimum element of the block to the end of its block, remove the slashes, increase every integer by 1, and finally attach the integer 1 at the front.
Conversely, we construct the set partition over $[n]$ corresponding to a run-sorted permutation $\pi\in \RsP(n+1)$ as follows. Put a slash after each right-to-left minimum of $\pi$, then delete the integer $1$, decrease the remaining integers by 1, and finally arrange the elements of each block in increasing order.
\begin{example}
If $P=14/258/37/6\in\SP(8)$, then we have $\pi=152693847\in \RsP(9)$.
Conversely, for $\pi=152693847\in \RsP(9)$ we have $\Rlmin(\pi)=\{1, 2, 3, 4, 7\}$. So by putting a slash after each right-to-left minimum we obtain $1/52/693/84/7\longrightarrow14/258/37/6=P$.
\end{example}
\section{Canonical forms of merging-free partitions}
\label{secflatrun}
In this section, we characterize the $\RGF$s corresponding to merging-free partitions and we present some results related to these canonical forms.
\begin{remark}
Let $f=f_1\cdots f_n$ be the canonical form of a set partition $P=B_1/\cdots/B_k$ over $[n]$ having $k$ blocks. We have $i\in \LrMax(f)$ if and only if $i=\min(B_{f_i})$.
\end{remark}
If $i\in \LrMax(f)$, then we call $f_i$ the \emph{left-to-right maximum letter}. We let $T_n$ denote the set of all $\RGF$s $f=f_1f_2\cdots f_n$ over $[n]$ satisfying the condition that every left-to-right maximum letter $s>1$ of $f$ has at least one occurrence of $s{-}1$ on its right.
\begin{proposition}
\label{CharSubFlat}
Let $P\in\SP(n)$ and let $f\in\RGF(n)$ be the canonical form of $P$. Then $P$ is merging-free if and only if $f\in T_n$.
\end{proposition}
\begin{proof}
If $P=B_1/B_2/\cdots /B_k$ is a merging-free partition having $k$ blocks, then $\min(B_{s-1})<\min(B_{s})$ and $\max(B_{s-1})>\min(B_s), ~s=2, \ldots, k$. Note that every leftmost occurrence of a letter in $f$ is a left-to-right maximum letter. The positions of the leftmost and rightmost occurrences of the letter $s$ in $f$ correspond to the minimum and the maximum elements of the block $B_s$, respectively. Thus, if $1*~~1$. Then, by definition, there is at least one integer $j>i$ such that $f_j=f_i{-}1$. Let us choose $j$ as the maximum of such integer(s). Thus, $B_{f_j}=B_{f_i-1}$ and $j=\max(B_{f_i-1})$. Since $i=\min(B_{f_i})$, we have $j>i$ and hence the corresponding set partition $P$ is merging-free.
\end{proof}
\begin{definition}
Let $f=f_1f_2\cdots f_n\in \RGF(n)$. If the occurrence of the letter $f_i$ in $f$ has no repetition, then we say that $f_i$ is \emph{unique} in $f$, i.e., $f_i$ is unique if and only if $i$ forms a singleton block in the partition. A weak left-to-right maximum $i$ in $f$ for which there exists $i_0~~*1$ is a left-to-right
maximum letter in $1\cdot f'$, then by Remark \ref{remarknonunique} $f_i$ is a non-unique left-to-right maximum letter in $f$. This implies that there is some $j>i$ such that $f_i=f_j$. Thus
$u_i=u_j$ and $ \delta_j=0$. So $\alpha(f)(i)=f'_i=f_i-u_i+1=f_j'+1$. Therefore, every left-to-right maximum letter $s>1$ of $1\cdot f'$ has some occurrence $s-1$ from its right. Hence $1\cdot f'\in T_{n+1}$.
\end{proof}
We now define a map $\beta~: T_{n+1}\mapsto \RGF(n)$ which associates each $1\cdot g=1\cdot g_1\cdots g_n\in T_{n+1}$ with a function $g'=\beta(1\cdot g)=g'_1g'_2\cdots g'_n$, where $g'$ is obtained from $g$ as follows. For each $i\in [n]$, we let $v_i$ denote the number of non-strict left-to-right maximum letters in $g$ that are less than or equal to $g_i$ in the positions $1, \ldots, i-1$. We let $v=(v_1, \ldots, v_n)$. Further, let $\delta'=(\delta'_1, \ldots, \delta'_n)$, where
\begin{displaymath} \delta'_i=
\begin{cases}
1, &\text{ if $g_i$ is a left-to-right maximum of $g$};\\
0, &\text{ otherwise}.
\end{cases}\end{displaymath}
Then
$$ g'=g+v-\delta'.$$
For instance, if $1\cdot g=122134321\in T_9$, then $g=22134321, v=(0, 0, 0, 1, 1, 1, 1, 0)$, and $\delta'=(1, 0, 0, 1, 1, 0, 0, 0)$. Thus, $g'=12134431\in\RGF(8)$. Note that $\beta=\alpha^{-1}$. As a result, we have the following proposition.
\begin{proposition}
The mapping $\alpha$ from the set $\RGF(n)$ to the set $T_{n+1}$ is a bijection. \qed
\end{proposition}
\begin{corollary}\label{corltmax}
If $f\in \RGF(n)$ and $\alpha(f)=1\cdot f'$, then $\LrMax(f)=\LwMp(f')$. \qed\end{corollary}
We now evaluate the number $\ell_n$ of $f\in\RGF(n)$ having the sequence $u=0$, i.e., if $f=f_1f_2\cdots f_n$, then for each $i\in[n]$ there is no unique left-to-right maximum letter smaller than $f_i$ on its left. The set partitions corresponding to such functions are exactly those satisfying the condition that their blocks have a size of at least two except for the last block, which may be a singleton. The sequence $(\ell_n)_{n\geq0}$ is the same as the OEIS sequence \seqnum{A346771}.
\begin{theorem}\label{thmzeroU}
For all $n\geq2$ we have
$$\ell_n=\sum_{k=1}^{n-1} \binom{n-1}{k}
\ell_{n-k-1}, ~\ell_0=\ell_1=1.$$
\end{theorem}
\begin{proof}
Let $f\in\RGF(n)$ satisfy the above condition. Since $f_1=1$ is the smallest integer, every such function has at least two $1$'s. Suppose that $f$ has $k+1$ occurrences of $1$'s. If we delete all the $1$'s and decrease each of the remaining integers by $1$, then we obtain an $\RGF$ over $[n{-}k{-}1]$, with the same condition as $f$. So there are $\ell_{n-k-1}$ such functions. We now choose $k$ positions from $\{2, 3, \ldots, n\}$ where to insert $1$, and this is possible in $\displaystyle \binom{n-1}{k}$ ways. Therefore, by applying the product rule and then taking the sum over all possible $k$, we have the right hand side.
\end{proof}
\section{Run distribution in run-sorted permutations}
\label{sec3}
The following table presents the first few values $r_{n, k}$ of the number of run-sorted permutations over $[n]$ having $k$ runs (presented in OEIS entry number \seqnum{A124324}, counting the number of set partitions in $\SP(n{-}1)$ by the number of non-singleton blocks).
\begin{table}[h!]
\centering
\begin{tabular}{c|ccccccc}
$n\backslash k$ & 1 & 2 & 3 & 4 & 5 & 6 & 7\\
\hline 1 & 0 & & & & & &\\
2 & 1 & 0 & & & & &\\
3 & 1 & 1 & 0 & & & &\\
4 & 1 & 4 & 0 & 0 & & &\\
5 & 1 & 11 & 3 & 0 & 0 & &\\
6 & 1& 26 & 25 & 0 & 0 & 0 &\\
7 & 1 & 57 & 130 & 15 & 0& 0 & 0\\
\hline
\end{tabular}
\caption{The values of $r_{n, k}$ for $1\leq k,n\leq 7$.}
\end{table}
\begin{remark}\label{rmruns}
The number $k$ of runs of a run-sorted permutation over $[n]$ satisfies the condition $$1\leq k\leq\lceil n/2 \rceil,~ n\geq1,$$ because each run except the last has length at least $2$.
\end{remark}
\begin{remark}
By Theorem \ref{thmzeroU} and Remark \ref{rmruns}, the set of merging-free partitions is a subset of
those set partitions having canonical forms with sequence $u=0$.
\end{remark}
The following result was conjectured by Nabawanda et al.\ (personal communication), who also gave a justification of the first term of the right-hand side of (\ref{eq1}). We were able to provide a combinatorial bijective proof to justify the second term and thus to prove the conjecture in our preliminary version of this article, entitled `Exhaustive generation algorithm for flattened set partitions'. Nabawanda et al.\ referred to this original proof in \cite{Na-Ra} and provided an alternative full proof of their own. Here we present that original proof, employing our bijection.
\begin{theorem}
\label{rrNaRa}
The number $r_{n, k}$ of run-sorted permutations of $[n]$ having $k$ runs satisfies the recurrence relation
\begin{equation}\label{eq1}
r_{n, k}=kr_{n-1, k}+(n-2)r_{n-2, k-1},~~n\geq2, ~k\geq1,\end{equation}
where $r_{0, 0}=1, ~r_{1, 0}=0, ~r_{1, 1}=1$.
\end{theorem}
To prove this result, we partition the set $\RsP(n,k)$ of run-sorted permutations over $[n]$ having $k$ runs into two subsets:
$\RsP^{ (1)}(n,k)$ and $\RsP^{ (2)}(n,k)$, where $\RsP^{ (1)}(n,k)$ is the set of elements of $\RsP(n,k)$ in which the removal of the integer $n$ does not decrease the number of runs, and $\RsP^{ (2)}(n,k)$ is the set of elements of $\RsP(n,k)$ in which the removal of the integer $n$ decreases the number of runs; this happens when the integer $n$ occurs between two integers $x$ and $y$ with $x1$ be the integer following $n$ in $\pi'$. We exhibit a pair $(i, \pi)\in [n-2]\times \RsP(n-2, k-1)$ such that $\psi(i, \pi)=\pi'$. Define $\pi$ to be the run-sorted permutation obtained from $\pi'$ by deleting the subword $n~j$ and by decreasing by 1 every integer greater than or equal to $j+1$ in the resulting word. Note that if $n$ follows the integer $i$ in $\pi'$, then $ii$, insert $m+1$ at the position $i+1$, and append $m$ at the end. The functions obtained with the second construction are all different from those obtained using the former one. Indeed, by erasing the last integer from $f'$ we do not obtain a function in $T_{n-1,k}$. The reason is that the value $m+1$ in the position $i+1$ is a left-to-right maximum letter because of the choice of $m$. Now, by construction, the only occurrence of $m$ in $f'$ is at position $n$. By erasing this value, the left-to-right maximum letter $m+1$ in the position $i+1$ is left without an occurrence of $m$ on its right. Therefore, $f_1'f_2'\cdots f_{n-1}'$ does not satisfy the property characterizing canonical forms of merging-free partitions. So this contributes $(n-2)r_{n-2, k-1}$ to the number $r_{n,k}$ as there are $n-2$ possibilities for $i$ and the number of image values of $f'$ increases by $1$.
\end{proof}
\begin{example}
Take $f=12132\in T_{5,3}$ and let $i=3$. We construct $(i,f)\mapsto f'$ as follows: we have $m=\max_{1\leq j\leq 3}\{f_j \}=\max_{1\leq j\leq 3}\{1, 2, 1 \}=2$, and $f'_1=f_1=1, f'_2=f_2=2, f'_3=f_3=1, f'_4=m+1=3, f'_5=f_4+1=4, f'_6=f_5+1=3, f'_7=m=2$. Thus, $f'=1213432\in T_{7,4}$.
\end{example}
\section{Right-to-left minima in run-sorted permutations}
\subsection{The distribution of right-to-left minima over the set of run-sorted permutations}
\label{secrlmin}
The following proposition gives us the relation between the statistics of right-to-left minima of run-sorted permutations and the weak left-to-right maxima of the canonical forms of the corresponding merging-free partitions.
\begin{proposition}
\label{rlmin-lrwmax}
The set of right-to-left minima of a run-sorted permutation over $[n]$ and the set of weak left-to-right maxima of the canonical form of the corresponding merging-free partition are the same.
\end{proposition}
\begin{proof}
Let $\Flatten(P)=\pi=\pi(1)\cdots\pi(n)\in \RsP(n)$, where $P$ is a merging-free partition over $[n]$. Let $f=f_1\cdots f_n$ be the canonical form of $P$ and let $\{i_1, \ldots, i_r\}$ be the set of the positions of the right-to-left minima of $\pi$, then by definition of right-to-left minima $\Rlmin(\pi)=\{1=\pi(i_1)<\pi(i_2)<\cdots<\pi(i_r)=\pi(n)\}$. Furthermore, if $1\leq j_1\pi(s), s>j$. Hence $f_{\pi(s)}>f_{\pi(j)}$ and $\pi(j)\notin \LwMp(f)$. Thus, $\{\pi(i_1), \ldots, \pi(i_k)\}\subseteq \LwMp(f)$.
Conversely, if $\LwMp(f)=\{i_1, \ldots, i_s\}$, then for each $i_j$ we have $f_{i_j}\geq f_t, t\lceil \frac{n}{2}\rceil, r>n, rn-k+1$.
\begin{proposition}
For all integers $n, k, r$ such that $1\leq k, r\leq n$, the numbers $a_{n,k,r}$ of run-sorted permutations over $[n+2]$ having $k$ runs and $r$ right-to-left minima satisfy
\begin{equation*}
a_{n+2,k,r}=a_{n+1,k,r-1}+\sum_{i=1}^n\binom{n}{i}a_{n+1-i,k-1,r-1}.
\end{equation*}
\end{proposition}
\begin{proof}
Let $\pi\in\RsP(n+2)$. Let us suppose that the integers $1$ and $2$ are in the same run of $\pi$. Let $\pi'$ be the permutation obtained from $\pi$ by deleting $1$ and then decreasing each of the remaining integers by $1$, then $\pi'\in \RsP(n+1)$ and $\run(\pi)=\run(\pi')$ and $\rlmin(\pi)=\rlmin(\pi')+1$. This implies that $$|\{\pi\in\RsP(n+2):~\run(\pi)=k, \rlmin(\pi)=r, 1 \text{ and } 2 \text{ are in the same run}\}|=a_{n+1,k,r-1}.$$ Let us suppose now that $1$ and $2$ are in different runs of $\pi$ and that the first run (containing $1$) has length $i+1, i\geq1$. Then we can choose $i$ elements from the set $\{3, 4, \ldots, n+2\}$ to include in the first run. There are $\displaystyle \binom{n}{i}$ ways to do so. The remaining part of $\pi$ is a run-sorted permutation over $n+1-i$ letters and thus there are $a_{n+1-i}$ of them. In this case, the number of runs and the number of right-to-left minima of $\pi$ each increase by $1$. This completes the proof.
\end{proof}
\begin{theorem}
We have \begin{equation}\label{rrrrlmin} a_{n,k,r}=a_{n-1,k,r-1}+(k-1)a_{n-1,k,r}+(n-2)a_{n-2,k-1,r-1}, n\geq2, k,r\geq 1
\end{equation} with the initial conditions $a_{0,0,0}=1, a_{1,1,1}=1$.
\end{theorem}
\begin{proof}
The proof is based on the technique used in the proof of Theorem \ref{rrNaRa}. Let $\pi'$ be a run-sorted permutation over $[n]$ obtained from $\pi\in \RsP(n{-}1)$ by inserting $n$ at the end of any of its runs. This operation preserves the number of runs. It also preserves the number of right-to-left minima except when $n$ is inserted at the end of the last run of $\pi$, in which case the number of right-to-left minima increases by $1$. So we get the first two terms of the right-hand side of (\ref{rrrrlmin}). Again, if $\pi'\in \RsP(n)$ is obtained from $\pi\in \RsP(n{-}2)$ by the operation defined in Lemma \ref{lemmacase2}, i.e., $\pi'=\psi(i,\pi)$, where $i\in[n-2]$, then the number of runs and the number of right-to-left minima each increase by $1$. We showed already that this is true for the number of runs, let us show it for the number of right-to-left minima. The operation increases each integer greater than $i$ in $\pi$ by $1$ and inserts the subword $n~i{+}1$ immediately after the rightmost position of the integers of the set $\{1, 2, \ldots, i\}$. Then the newly created run beginning at $i+1$ contributes one more right-to-left minimum, since the minima of the runs form an increasing subsequence. Thus, we have the last term on the right-hand side of the recurrence.
\end{proof}
\begin{remark}
If we use the interpretation with set partitions, $a_ {n,k,r}$ counts the number of set partitions in $\SP(n{-}1)$ having $r{-}1$ blocks in which $k{-}1$ of them are non-singleton blocks.
\end{remark}
\begin{theorem}
The exponential generating function \begin{displaymath} A(x,y,z)=
\sum_{n,k,r\geq0}a_{n,k,r}\frac{x^n}{n!}y^kz^r\end{displaymath} satisfies the differential equation
\begin{equation}
\frac{\partial A}{\partial x}=yze^{xz-yz(1+x-e^x)}
\label{gfrunrlmin}
\end{equation}
with the initial condition $\frac{\partial A}{\partial x}|_{x=0}=yz$.
\label{thmgfrunrlmin}
\end{theorem}
\begin{proof}
By (\ref{rrrrlmin}) we have \begin{align*}
\sum_{n\geq2,k,r\geq1}a_{n,k,r}\frac{x^n}{n!}y^kz^r&=\sum_{n\geq2,k,r\geq1}a_{n-1,k,r-1}\frac{x^n}{n!}y^kz^r+\sum_{n\geq2,k,r\geq1}(k-1)a_{n-1,k,r}\frac{x^n}{n!}y^kz^r+\notag\\&~~~~\sum_{n\geq2,k,r\geq1}a_{n-2,k-1,r-1}\frac{x^n}{n!}y^kz^r.\end{align*} Using the notation $A_y=\frac{\partial A}{\partial y}$ and expressing the above equation in terms of $A$ we obtain \begin{align}
A&= z\left(\int Adx-x\right)+\int yA_ydx-\left(\int Adx-x\right)+xyz\int Adx-\notag\\&~~~~2yz\int \int Adxdx+1+xyz
\notag\\
&=\int yA_ydx-(1-z-xyz)\int A dx+x-xz-2yz\int \int A dxdx+1+xyz.
\label{gfdoubleint}
\end{align}
By differentiating both sides of (\ref{gfdoubleint}) with respect to $x$ we obtain the following:
\begin{align*}
A_x=yA_y-(1-z-xyz)A+1-z-yz\int Adx+yz.
\end{align*}
Again by differentiating the above equation with respect to $x$ we obtain
\begin{equation}
A_{xx}=yA_{yx}-(1-z-xyz)A_x.
\label{secdiff}
\end{equation}
By letting $B=A_x$ in (\ref{secdiff}) we obtain
\begin{equation}
B_x-yB_y+(1-z-xyz)B=0.
\label{firstdiffsubst}
\end{equation}
Then the characteristic equation is $\frac{dy}{dx}=\frac{-y}{1}$ or $\ln y+x=k$ with $k$ constant. We make the transformation with $\epsilon=x, \mu=\ln y+x, \zeta=z$, and $w(\epsilon,\mu,\zeta)=B(x,y,z)$. Using the substitution we find that (\ref{firstdiffsubst}) transforms to
\begin{align*}
w_\epsilon+\left(1-\zeta-\epsilon\zeta e^{\mu-\epsilon}\right)w=0.
\end{align*}
By the integrating factor method we have
\begin{align*}
\frac{\partial}{\partial\epsilon}\left(e^{\int\left(1-\zeta-\epsilon\zeta e^{\mu-\epsilon}\right)d\epsilon}w\right)=0
\end{align*}
and then integrating the above equation with respect to $\epsilon$ and simplifying
\begin{align*}
w(\epsilon,\mu,\zeta)&=g(\mu,\zeta)e^{\int\left(-1+\zeta+\epsilon\zeta e^{\mu-\epsilon}\right)d\epsilon}\\
&=g(\mu,\zeta)e^{\epsilon(-1+\zeta)-\zeta e^{\mu-\epsilon}(1+\epsilon)+h(\mu,\zeta)},
\end{align*}
where $g$ and $h$ are any differentiable functions of two variables. Using the initial condition $B(0,y,z)=yz$ we have $x=0, \epsilon=0, \mu=\ln y, \zeta=z, w(\epsilon=0,\mu=\ln y,\zeta=z)=yz$, and
\begin{align*}
yz&=g(\ln y,z)e^{-yz+h(\ln y,z)}\\
yze^{yz}&=g(\ln y,z)e^{h(\ln y,z)}.
\end{align*}
Thus, we obtain $g(t,z)=h(t,z)=ze^t$. Therefore, we back the transformation in terms of $x, y,z $ so that
\begin{align*}
B(x,y,z)&=g(\ln y+x,z)e^{-x+xz-yz(1+x)+h(\ln y+x,z)}\\
&=yze^{xz-yz(1+x-e^x)}.
\end{align*}
\end{proof}
By specializing $z=1$ in (\ref{gfrunrlmin}) we obtain the result about the exponential generating function counting run-sorted permutations by the number of runs \cite{Na-Ra}. Recall that $r_{n,k}$ is the number of run-sorted permutations over $[n]$ having $k$ runs.
\begin{corollary}
If $A(x,y)=\sum_{n,k\geq1}r_{n,k}\frac{x^n}{n!}y^k$, then $A$ satisfies \begin{align*} \frac{\partial A}{\partial x}=ye^{x-y(1+x-e^x)}\end{align*}
with the initial condition $\frac{\partial A}{\partial x}|_{x=0}=y$.
\end{corollary}
By specializing $y=z=1$ in (\ref{gfrunrlmin}) we obtain the well-known result about the exponential generating function counting the number of run-sorted permutations (merging-free partitions) \cite{Bo,St1}.
\begin{corollary}
\label{diffgenfun}
The exponential generating function $A(x)$ of the number of run-sorted permutations has the closed differential form
$$A'(x)=e^{e^x-1}.$$
\end{corollary}
\begin{corollary}
For all positive integer $n\geq1$, the number $a_n$ of run-sorted permutations over $[n]$ is given by
$$
a_n=\frac{1}{e}\sum_{m\geq 0}\frac{m^{n-1}}{m!}.$$
\end{corollary}
\subsection{A bijection with separated partitions}
We now consider set partitions with no two consecutive integers in the same block. Such partitions have been studied, for instance, by Munagi \cite{Mu}, who called them ``separated'' partitions and proved that separated partitions over $[n]$ having $k$ blocks are counted by the shifted Stirling numbers of the second kind (\seqnum{A008277}), like the run-sorted permutations over $[n]$ having $k$ right-to-left minima.
It is then natural to provide a bijection between these two equisized classes of objects. Let $\mathcal{P}_n$ denote the set of all separated partitions over $[n]$.
Let $P=B_1/B_2/\cdots/B_k\in\mathcal{P}_n$ with $k$ blocks.
Define a map $\theta~: \mathcal{P}_n\mapsto\RsP(n)$ given by $\pi=\theta(P)$, where $\pi$ is obtained as follows:
\begin{itemize}
\item[-] for $i=2, \ldots, k$:
~~~~~ if $b\in B_i, b\neq \min(B_i)$ and $b-1\in B_j$ such that $j**i$. Since $b-1\geq \min(B_j)$ we have $b>\min(B_j)$, so the procedure moves neither $b$ nor $\min(B_j)$ which implies that $b$ cannot be a right-to-left minimum of $\pi$. Therefore, $b$ is a right-to-left minimum of $\pi$ if and only if $b=\min(B_i), i=1, \ldots, k$. We next prove that $\theta$ is one-to-one. Suppose that $P\neq P'$, where $P, P'\in \mathcal{P}_n$. If the number of blocks of $P$ and the number of blocks of $P'$ are different, then we are done since $\theta(P)$ and $\theta(P')$ have different number of right-to-left minima. Let $P=B_1/\cdots/B_k$ and $P'=B'_1/\cdots/B'_k$, and assume that there exists an element $b\in B_i$ and $b\in B'_j$ such that $B_i$ is the block of $P$ and $B'_j$ is the block of $P'$ with $i\neq j$. We take the minimal of these elements. Up to exchanging of $P$ and $P'$ we can suppose $i1$, then let $a_1=\min(B_{s-1})$, $a_2=\max(B_{s-1})$, and $b=\min(B_s)$. Then $a_1b$ because $P$ is merging-free. Thus $a_1, b, a_2, n$ is a crossing, which is impossible. So $s=1$. Hence $j+1\in B_1$ as well. Since $1\in B_1$, there must be an arc from $j+1$ that points to the left.
\begin{center}
\includegraphics[width=0.5\columnwidth]{CrossFlatPart1}
\end{center}
If $j$ is not the maximum element of its block, then the arc relating it to its successor in the partition creates a crossing. If instead $j$ is the maximum element of its block, then there is an integer $k>i$ such that $k$ is in the same block as an integer $j'f_b$. Let $f$ be the canonical form of a set partition $P$ over $[n]$, then $P$ is non-crossing if and only if $f$ is $212$-avoiding \cite{Li-Fu,Si1}. A function $f=f_1f_2\cdots f_n$ is said to be \textit{weakly uni-modal} if there exists a value $m\leq n$ for which it is weakly increasing for $i\leq m$ and weakly decreasing for $i\geq m$, i.e., $f_1\leq f_2\leq\cdots\leq f_m\geq f_{m+1}\geq\cdots\geq f_n$. Thus, we have the following result.
\begin{proposition}
Let $f$ be the canonical form of a merging-free partition $P$, then $f$ is $212$-avoiding if and only if it is weakly uni-modal.
\end{proposition}
\begin{proof}
Consider the forward implication. Since $f$ is an $\RGF$, if it is not weakly uni-modal, although it is $212$-avoiding, then it contains either a pattern $312$ or $213$. If $f$ contains a $312$, then before the $3$ there is a $2$ and hence it contains $212$. This is a contradiction. Suppose that $f$ contains a pattern $213$ in the positions $ab$ such that $f_c=f_b-1$ because $P$ is merging-free. Since $f$ is an $\RGF$ there exists an integer $d\leq a$ such that $f_d=f_c$ because of the choice of $b$. Thus, $f$ contains the pattern $212$ in $d\pi[t+1]$ }
\STATE $\pi'\longleftarrow \pi.Insert(t+1, n)$
\STATE $L.Append(\pi')$
\ENDIF
\ENDFOR
\STATE $\pi'\longleftarrow\pi.Append(n)$
\STATE $L.Append(\pi')$
\ENDFOR
\RETURN $L$
\end{algorithmic}
\end{algorithm}
\begin{algorithm}[H]
\caption{Generation of a run-sorted permutation in $\RsP^{(2)}(n,k)$ from an element of $[n-2]\times \RsP(n-2,k-1)$.}
\begin{algorithmic}
\STATE\textbf{Procedure:} \texttt{RUN\_SORTED\_PERMUTATION\_SIZE\_INC\_BY\_TWO}($(\pi, p)$)
\ENSURE $\pi$ is a run-sorted permutation in $\RsP(n-2,k-1)$ and $p$ is an integer in $[n-2]$.
\FOR{$t$ \textbf{in} $Range(Length(\pi))$}
\IF {$\pi[t]>p$}
\STATE $\pi[t]\longleftarrow \pi[t]+1$
\ENDIF
\ENDFOR
\STATE $pos=Length(\pi)-1$
\WHILE{$\pi[pos]>p$}
\STATE $pos\longleftarrow pos-1$
\ENDWHILE
\STATE $\pi.Insert(pos+1, Length(\pi)+2)$
\STATE $\pi.Insert(pos+2, p+1)$
\RETURN $(\pi)$
\end{algorithmic}
\end{algorithm}
Algorithm 3 calls Algorithm 2 and gives us the exhaustive generation algorithm for the set of run-sorted permutations in $\RsP^{(2)}(n,k)$.
\begin{algorithm}[H]
\caption{Exhaustive Generation of Run-sorted Permutations in $\RsP^{(2)}(n,k)$.}
\begin{algorithmic}
\STATE\textbf{Procedure:} \texttt{FUNCTION\_TWO}$(\RsP)$
\ENSURE $\RsP$ is a list of lists whose elements represent run-sorted permutations in $\RsP(n-2,k-1)$.
\STATE $L\leftarrow [ ~]$
\FOR{$\pi$ \textbf{in} $\RsP$}
\FOR{$p$ \textbf{in} $Range(1, Length(\pi)+1)$}
\STATE $\pi'\longleftarrow$ \texttt{RUN\_SORTED\_PERMUTATION\_SIZE\_INC\_BY\_TWO}$(\pi,p)$
\STATE $L.Append(\pi')$
\ENDFOR
\ENDFOR
\RETURN $L$
\end{algorithmic}
\end{algorithm}
We now present the main exhaustive generation algorithm that generates all and only those run-sorted permutations in $\RsP(n)$ for all possible $n$. The algorithm returns a list of lists of lists of integers, namely the list $\RsP(n)=[\RsP(n,1), \RsP(n,2), \ldots, \RsP(n,n)]$, where each element $\RsP(n,k)$ is the list of all run-sorted permutations over $[n]$ having $k$ runs.
Since $\RsP(n,k)=\emptyset$ if $k>\lceil{\frac{n}{2}}\rceil$, the algorithm can be optimized by computing only those sets $\RsP(n,k)$ that are not empty.
As we said, the algorithm is based on the dynamic programming. We stock the values of the lists $\RsP(n-1)$ and $\RsP(n-2)$, and use them to compute the list $\RsP(n)$.
To save memory, only the last two lists are kept at any time: the list $\RsP(n-1)$ is stored in a variable called \texttt{LastRow};
the list $\RsP(n-2)$ is stored in a variable called \texttt{RowBeforeLast}; and the list $\RsP(n)$ is stored in a variable called \texttt{CurrentRow}.
At the end of each iteration, the three variables are shifted.
\begin{algorithm}[H]
\caption{Exhaustive Generation of Run-Sorted Permutations.}
\begin{algorithmic}
\STATE\textbf{Procedure:} \texttt{RUN\_SORTED\_PERMUTATIONS}($n$)
\ENSURE $\RsP$ is a list of lists whose elements represent run-sorted permutation in $\RsP(n-2,k-1)$.
\STATE \texttt{RowBeforeLast}$\longleftarrow[[[1]]]$
\STATE \texttt{LastRow}$\longleftarrow[[[1,2]],[~]]$
\FOR{$i$ \textbf{in} $Range(3,n+1)$}
\STATE \texttt{CurrentRow}$\longleftarrow[~]$
\STATE \texttt{CurrentRow}$.Append$(\texttt{FUNCTION\_ONE}(\texttt{LastRow}$[0],i$))
\FOR{$j$ \textbf{in} $Range(1,\lceil\frac{i}{2}\rceil)$}
\STATE \texttt{CurrentRow}$.Append($\texttt{FUNCTION\_ONE}(\texttt{LastRow}$[j],i$)
\STATE \texttt{CurrentRow}$.Append($\texttt{FUNCTION\_TWO}$($\texttt{RowBeforeLast}$[j-1]))$
\ENDFOR
\STATE \texttt{RowBeforeLast}$\longleftarrow$ \texttt{LastRow}
\STATE \texttt{LastRow}$\longleftarrow$ \texttt{CurrentRow}
\ENDFOR
\end{algorithmic}
\end{algorithm}
All these algorithms have been implemented in Python.
\begin{example}
When \texttt{RUN\_SORTED\_PERMUTATIONS}($n$) is executed for $n=5$ we get the list $\RsP(5)$:
\begin{align*}
&[[[1,2,3,4,5]],\\
&[[1,3,4,5,2], [1,3,4,2,5], [1,3,5,2,4], [1,3,2,4,5], [1,4,5,2,3], [1,4,2,3,5], [1,2,4,5,3], \\
&[1,2,4,3,5], [1,5,2,3,4], [1,2,5,3,4], [1,2,3,5,4]],\\
& [[1,5,2,4,3], [1,4,2,5,3], [1,3,2,5,4]], \\
&[~]].\end{align*}
Observe that $a_{5,1}=1, a_{5, 2}=11, a_{5, 3}=3, a_{5,4}=0$, and $a_5=1+11+3+0=15$.
\end{example}
\section{Acknowledgments}
We thank the editor and the anonymous referees for their comments and suggestions. The first author is grateful for the financial support extended by IRIF, the cooperation agreement between International Science Program (ISP) at Uppsala University and Addis Ababa University, and the support by the Wenner-Gren Foundations. We appreciate the hospitality we received from IRIF during the research visits of the first author. We also thank our colleagues from CoRS (Combinatorial Research Studio) for valuable discussions and comments. In particular, we thank Per Alexandersson and J\"orgen Backelin of Stockholm University for their useful discussions and suggestions.
\begin{thebibliography}{99}
\bibitem{Al-Na} P. Alexandersson and O. Nabawanda, Peaks are preserved under run-sorting, \textit{Enumer. Comb. Appl.} \textbf{2} (2022), Article \#S2R2.
\bibitem{Be} H. W. Becker, Planar rhyme schemes, \textit{Bull. Amer. Math. Soc.} \textbf{58} (1952), 39.
\bibitem{Bo} M. Bona, \textit{Introduction to Enumerative Combinatorics}, McGraw-Hill, 2007.
\bibitem{Ca} D. Callan, Pattern avoidance in ``flattened'' partitions. \textit{Discrete Math.} \textbf{309} (2009), 4187--4191.
\bibitem{Kr} G. Kreweras, Sur les partitions non crois\'ees d'un cycle, \textit{Discrete Math.} \textbf{4} (1972), 333--350.
\bibitem{Li-Fu} Z. Lin and Sh. Fu, On 1212-avoiding restricted growth functions, \textit{Electron. J. Combin.} \textbf{24} (2017), $\#$P1.53.
\bibitem{Ma} T. Mansour, \textit{Combinatorics of Set Partitions}, CRC Press, 2013.
\bibitem{Ma-Sh-Wa} T. Mansour, M. Shattuck, and S. Wagner, Counting subwords in flattened partitions of sets, \textit{Discrete Math.} \textbf{338} (2015), 1989--2005.
\bibitem{Mu} A. O. Munagi, Set partitions and separations, \textit{Int. J. Math. Math. Sci.} \textbf{3} (2005), 451--463.
\bibitem{Na-Ra} O. Nabawanda, F. Rakotondrajao, and A. S. Bamunoba, Run distribution over flattened partitions, \textit{J. Integer Sequences}
\textbf{23} (2020), \href{https://cs.uwaterloo.ca/journals/JIS/VOL23/Nabawanda/naba5.html}{Article 20.9.6}.
\bibitem{Or} M. Orlov, Efficient generation of set partitions,
preprint, 2002. Available at \url{https://noexec.org/public/papers/partitions.pdf}.
\bibitem{Ro} G. Rota, The number of partitions of a set, \textit{Amer. Math. Monthly} \textbf{71} (1964), 498--504.
\bibitem{Si1} R. Simion, Combinatorial statistics on non-crossing partitions, \textit{J. Combin. Theory Ser. A} \textbf{66} (1994), 270--301.
\bibitem{Si} R. Simion, Non-crossing partitions, \textit{Discrete Math.} \textbf{217} (2000), 367--409.
\bibitem{Sl} N. J. A. Sloane et al., {\it The On-Line Encyclopedia of Integer Sequences}, 2022. Available at \url{https://oeis.org}.
\bibitem{St1} R. P. Stanley, \textit{Enumerative Combinatorics} \textbf{1}, Cambridge University Press, 2011.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent
2010 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 05A15, 05A19.
\medskip
\noindent
\emph{Keywords:} merging-free partition, canonical form, run-sorted permutation, non-crossing partition, algorithm.
\bigskip
\hrule
\bigskip
\noindent
(Concerned with sequences
\seqnum{A008277},
\seqnum{A124324}, and
\seqnum{A346771}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received January 13 2022;
revised versions received January 14 2022;
July 16 2022; August 30 2022; September 17 2022; September 19 2022.
Published in {\it Journal of Integer Sequences}, September 19 2022.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}
*