\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{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \usepackage{slashbox} \usepackage{enumerate,tikz,listings,array,longtable} \usetikzlibrary{shapes,arrows,chains} \usepackage{pgf} \DeclareMathOperator{\OCH}{OCH} \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}}} \begin{document} \begin{center} \epsfxsize=4in \leavevmode\epsffile{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 Run Distribution Over Flattened Partitions} \vskip 1cm \large Olivia Nabawanda\footnote{Corresponding author.}\\ Department of Mathematics\\Makerere University\\ P. O. Box 7062\\ Kampala \\ Uganda\\ \href{mailto:onabawanda@must.ac.ug}{\tt onabawanda@must.ac.ug}\\ \ \\ Fanja Rakotondrajao\\ D\'epartement de Math\'ematiques et Informatique\\ Universit\'e d'Antananarivo\\ Antananarivo \\ Madagascar\\ \href{mailto:frakoton@yahoo.fr}{\tt frakoton@yahoo.fr}\\ \ \\ Alex Samuel Bamunoba\\ Department of Mathematics\\Makerere University\\ P. O. Box 7062\\ Kampala \\ Uganda\\ \href{mailto:bamunoba@cns.mak.ac.ug}{\tt bamunoba@cns.mak.ac.ug} \end{center} \vskip .2 in \begin{abstract} The study of flattened partitions is an active area of current research. In this paper, our study unexpectedly leads us to the OEIS sequence \seqnum{A124324}. We provide a new combinatorial interpretation of these numbers. A combinatorial bijection between flattened partitions over $[n+1]$ and the partitions of $[n]$ is also given in a separate section. We introduce the numbers $f_{n, k}$ which count the number of flattened partitions over $[n]$ having $k$ runs. We give recurrence relations defining them, as well as their exponential generating function in differential form. It should be appreciated if its closed form is established. We extend the results to flattened partitions where the first $s$ integers belong to different runs. Combinatorial proofs are given. \end{abstract} \newcommand{\C}{\mathbb{C}} \newcommand{\PP}{\mathrm{P}} \newcommand{\B}{\mathbb{B}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\R}{\mathbb{R}} \newcommand{\Q}{\mathbb{Q}} \newcommand{\fS}{\mathfrak{S}} \newcommand{\Id}{\mathrm{Id}} \newcommand{\cone}{\mathrm{cone}} \newcommand{\conv}{\mathrm{conv}} \newcommand{\height}{\mathrm{height}} \newcommand{\im}{\mathrm{im}} \newcommand{\HH}{\mathcal{H}} \newcommand{\fpa}{\mathrm{FPA}} \newcommand{\pn}{\mathrm{part}} \newcommand{\RP}{\mathrm{RelPrime}} \newcommand{\rp}{\mathrm{relprime}} \newcommand{\rpac}{\mathrm{rpac}} \newcommand{\relprime}{\mathrm{relprime}} \newcommand{\ptn}{\mathrm{part}} \newcommand{\Rpac}{\mathrm{Rpac}} \newcommand{\Relprime}{\mathrm{Relprime}} \newcommand{\Ptn}{\mathrm{Part}} \def\v{{\boldsymbol v}} \def\t{{\boldsymbol t}} \newcommand{\A}{\mathcal{V}} \newcommand{\m}{\mathfrak{m}} \section{Introduction and preliminaries}\label{sec:intro} The study of the different statistics of permutations such as descents, ascents, excedances and runs has a long history and has been an area of intensive research in the past years. A lot of work is available in the literature \cite{ehrenborg2000excedance, macmahon2001combinatory, mantaci2003exceedingly, sloane2008line, con1}. These statistics play an important role in combinatorics and mathematics as a whole. For a given positive integer $n$, we denote the set $\{1, 2, \ldots, n\}$ by $[n]$. A permutation $\sigma$ over $[n]$ is represented as a word $\sigma(1)\sigma(2)\cdots\sigma(n)$. We say that $\sigma$ has an {\it ascent (descent)} at position $i$ if $\sigma(i) < \sigma(i+1)\,(\sigma(i) > \sigma(i+1))$, where $i \in [n]$. A {\it run} in a permutation $\sigma$ is a subword $\sigma(i)\sigma(i+1)\cdots \sigma(i+p)\sigma(i+p+1)$ where $i, i+1, \ldots, i+p$ are consecutive ascents. In this case, $i-1$ (if it does exist) and $i+p+1$ are non ascents, where $i \in [n]$. For example, in $\sigma = 526134$, we have ascents at positions $2, 4$ and $5$. It also has descents at positions $1$ and $3$. The last element $4$ of $\sigma$ at position $6$ is neither an ascent nor a descent. A {\it right to left minimum} of a permutation $\sigma$ is an element $\sigma(i)$ such that $\sigma(i) < \sigma(j)$ for all $j > i$. For example, in $\sigma = 1246357$, the {\it right to left minima} are $\{1, 2, 3, 5, 7\}$. Counting permutations according to the number of runs has been studied from various perspectives in enumerative combinatorics. Canfield and Wilf \cite{canfield2008counting} considered a run as a subsequence of a permutation $\sigma$, whose values either increase on the interval (run up) or decrease on the interval (run down). More related work on permutation runs can also be found in articles \cite{bona2000combinatorial, ma2012explicit, ma2013enumeration, zhuang2016counting}. A permutation $\pi$ is said to be a {\it flattened partition} if it consists of runs arranged from left to right such that their first entries are in increasing order. It is clear that the first run always starts with $1$, and so all flattened partitions start with the integer $1$. For example, consider a permutation $\sigma = 139278456$. This is a flattened partition with three runs namely: $139, 278, 456$ whose first entries $1, 2, 4$ are in increasing order. However, the permutation $\sigma = 139456287$ is not a flattened partition since the first entries $1, 4, 2, 7$, of the runs $139, 456, 28, 7$ are not in increasing order. Given a non-empty finite subset $S$ of positive integers, a {\it set partition} $P$ of $S$ is a collection of disjoint non-empty subsets $B_{1},B_{2}, \ldots, B_{k}$ of $S$ (called blocks) such that $\displaystyle\cup_{i = 1}^{k}B_{i} = S$ \cite{mansour2012combinatoric, rota1964number}. We shall maintain the name and notion of ``flattened partition" introduced by Callan \cite{callan2009pattern}. Callan borrowed the notion ``{\it flatten}" from {\it Mathematica} programming language, where it acts by taking lists of sets arranged in increasing order, removes their parentheses, and writes them as a single list \cite{stephen1999mathematica}. Mansour et al.\ \cite{mansour2015counting} also used the same notion. To generate flattened partitions, the elements of each block are written as increasing subsequences, and blocks arranged from left to right in increasing order of their first entries. Carlitz \cite{carlitz1968generalized} also applied the notion ``{\it flatten}" to permutations expressed in cycle notation. We let $\mathcal{F}_{n}$ denote the set of all flattened partitions over $[n]$, $\mathcal{F}_{n, k}$ the set consisting of all flattened partitions over $[n]$ having $k$ runs, $f_{n, k}$ the cardinality of the set $\mathcal{F}_{n, k}$. In Table \ref{tab:t1}, we give the first few values of the numbers $f_{n, k}$. \begin{table}[H] \centering \footnotesize \begin{tabular}{|c| c c c c c|} \hline \backslashbox{$n$}{$k$} & $1$ & 2 & 3 & 4 & 5 \\ \hline $1$ & 1 & & & & \\ 2 & 1 & & & & \\ 3 & 1 & 1 & & & \\ 4 & 1 & 4 & 0 & & \\ 5 & 1 & 11 & 3 & 0 & \\ 6 & 1 & 26 & 25 & 0 & 0 \\ \hline \end{tabular} \caption{The numbers $f_{n, k}$} \label{tab:t1} \end{table} We notice that the terms in the column for $k = 2$ of Table \ref{tab:t1} correspond to the Eulerian numbers. Foata and Sch\"{u}tzenberger \cite{olivia} gave the fundamental work on these numbers. Mantaci and Rakotondrajao \cite{mantaci} gave a new combinatorial interpretation to the same. Many other references concerning Eulerian numbers can be found on the OEIS \seqnum{A000295}. In Section \ref{B}, we establish different recurrence relations of the numbers $f_{n, k}$ and give their combinatorial proofs. We also define the exponential generating function $F(x, u)$ of the numbers $f_{n, k}$ which is defined by \begin{equation*} F(x, u) = \sum_{n \geq 0}\sum_{k\geq 0} f_{n, k} x^{k}\frac{u^{n}}{n!} = \sum_{n \geq 0}\sum_{\sigma \in \mathcal{F}_{n}}x^{run(\sigma)}\frac{u^{n}}{n!}, \end{equation*} where $run(\sigma)$ is the number of runs in a flattened partition $\sigma$. In Section \ref{C}, we generalize the results in Section \ref{B} to flattened partitions over $[n]$ whose first $s$ integers belong to different runs . We let $f_{n, k}^{(s)}$ denote the number of flattened partitions over $[n]$ whose first $s$ integers belong to different runs, and $F^{[s]}(x, u)$ the exponential generating function for the numbers $f_{n, k}^{(s)}$. The first few values of $f_{n, k}^{(s)}$ for $s = 2$ and $s = 3$ are shown in Table \ref{tab:t3} and \ref{tab:t4}: \begin{table}[H] \begin{minipage}[b]{0.45\linewidth} \centering \footnotesize \begin{tabular}{|c| c c c c |} \hline \backslashbox{$n$}{$k$} & $2$ & 3 & 4 & 5 \\ \hline $2$ & 0 & & & \\ 3 & 1 & 0 & & \\ 4 & 3 & 0 & & \\ 5 & 7 & 3 & 0 & \\ 6 & 15 & 22 & 0 & \\ 7 & 31 & 105 & 15 & 0 \\ \hline \end{tabular} \caption{The numbers $f_{n, k}^{(2)}$} \label{tab:t3} \end{minipage} \begin{minipage}[b]{0.45\linewidth} \centering \footnotesize \begin{tabular}{|c| c c c |} \hline \backslashbox{$n$}{$k$} & $3$ & 4 & 5 \\ \hline 4 & 0 & & \\ 5 & 2 & 0 & \\ 6 & 12 & 0 & \\ 7 & 50 & 12 & 0 \\ 8 & 180 & 140 & 0 \\ \hline \end{tabular} \caption{The numbers $f_{n, k}^{(3)}$} \label{tab:t4} \end{minipage} \end{table} Mansour et al.\ \cite{mansour2015counting} gave a recursive formula for the number of flattened partitions over $[n]$, and also mention that the number of distinct permutations that can be obtained as flattened partitions over $[n]$ is the Bell number $B_{n-1}$. Let $\mathcal{P}_{n}$ denote the collection of partitions of $[n]$. Our study led us to the OEIS \seqnum{A124324} which counts the number of partitions of $[n]$ having $k$ blocks of size greater than $1$. The authors of the present paper were introduced to the OEIS \seqnum{A124324} by Heinz \cite{fhh} who gave a maple program for computing the terms of this sequence recursively. The first maple program which computes this sequence using the exponential generating function was given by Emeric Deutsch. A combinatorial bijection between elements of $\mathcal{P}_{n}$ having $(k-1)$ blocks of size greater than $1$ and $\mathcal{F}_{n+1, k}$ will be given in Section \ref{A}. \section{Flattened partitions and their behaviours on runs}\label{B} \subsection{Recurrence relations} We have $f_{n, 1} = 1$ for all $n \geq 1$ and $f_{n, k} = 0$ for all $k\geq n\geq 2$. It is not possible to have a flattened partition over $[n]$ whose number of runs $k$ is greater or equal to its length. \begin{theorem} \label{thm4} For all integers $n$ and $k$ such that $2 \leq k < n$, the numbers $f_{n, k}$ of flattened partitions over $[n]$ with $k$ runs satisfy the recurrence relation \begin{equation}\label{mum1} f_{n, k} = \sum_{m = 1}^{n-2}\left({n-1 \choose m} - 1\right)f_{m, k-1}. \end{equation} \end{theorem} \begin{proof} To construct a flattened partition $\pi$ over $[n]$ having $k$ runs, we consider a flattened partition $\tau$ over $[m]$ having $k-1$ runs, for an integer $m < n$. Since all flattened partitions start with element $1$, we insert the word of length $n-m$ starting with $1$, before a flattened partition $\tau$ to obtain $1\underbrace{\dots}_{n-m-1}\underbrace{\tau}_{m}$, and then re-order the elements of $\tau$ making sure the number of runs increase by one. The $n-m-1$ elements between $1$ and $\tau$ can be chosen from the set $\{2, 3, 4, \ldots, n\}$ of $(n-1)$ terms in $\displaystyle n-1 \choose n-m-1$ ways. In order to increase the number of runs by one, we avoid choosing the subset $\{2, 3, \ldots, n-m-1\}$ of consecutive elements. We thus have $\displaystyle \bigg({n-1 \choose n-m-1} - 1\bigg)$ possible subsets to be inserted after $1$. The minimum number of elements in the first run is $2$, implying that the maximum length of $\tau$ is $n-2$. Since $n \geq 3$, then the minimum length of $\tau$ is $1$. Thus we have that $1 \leq m \leq n-2$. Thus summing up over $1 \leq m \leq n-2$ gives the recurrence relation in Equation \eqref{mum1}. \end{proof} \begin{example} Let us construct flattened partitions over $[6]$ having $3$ runs from a flattened partition $\tau$ over $[3]$ having $2$ runs. We have $\tau = 132$. The favorable subsets of two terms from the set $\{2, 3, 4, 5, 6\}$ are: $\{2, 4\}, \{2, 5\}, \{2, 6\}, \{3, 4\}, \{3, 5\}, \{3, 6\}, \{4, 5\}, \{4, 6\}, \{5, 6\}$. Consider the pair $(\{3, 4\}, \tau)$, we get $\pi = 134265$. For the pair $(\{4, 6\}, \tau)$, we get $\pi = 146253$. \end{example} Let $a_{n}$ denote the maximum number of runs $k$ in a flattened partition of $[n]$. From Table \ref{tab:t1} above, we see that the maximum number of runs, $a_{n}$ results into a sequence $1, 1, 2, 2, 3, 3, 4, 4, 5, 5, \ldots,$ for $n \geq 1$. \begin{proposition}\label{pp} The maximal number $a_{n}$ of runs in a flattened partition over $[n]$ satisfies the relation \begin{equation*}\label{ks} a_{n} = a_{n-2} +1, \end{equation*} for all $n\geq 2$, with initial conditions $a_{0} = 0, a_{1} = 1$. \end{proposition} \begin{proof} Let $n$ be an integer such that $n \geq 2$. Consider a flattened partition $\tau$ over $[n-2]$ having maximal number of runs. Using the construction in Theorem \ref{thm4}, inserting two elements $1x$ where $x = \{3, 4, \ldots, n\}$ before $\tau$ and re-ordering the elements of $\tau$ can only add a maximum of $1$ run. Hence we have $a_{n} \geq a_{n-2} + 1$. On the other hand, inserting $n-2$ elements between $1$ and the identity $\tau = 1$ from the construction in the same theorem, we have $1\underbrace{\cdots}_{n-2}1$ and then re-ordering the elements of $\tau$. This means the subsets between $1$ and $\tau$ can be chosen from the set $\{3, 4, \ldots, n\}$ of $n-2$ elements whose maximum number of runs is $a_{n-2}$. Hence we have $a_{n} \leq a_{n-2}+1$. These two inequalities, together with $a_{0} = 0$ and $a_{1} = 1$, yield $a_{n} = a_{n-2}+1$. \end{proof} As an obvious conclusion, we have the following corollary: \begin{corollary} The maximal number of runs $a_{n}$ in a flattened partition over $[n]$ has the closed form $\displaystyle \dfrac{1}{4}\big(2n + (-1)^{n+1} +1\big)$ and its generating function $\displaystyle Y(x) = \sum_{n=0}^{\infty}a_{n}x^{n}$ is given by $\dfrac{x}{(1-x)^{2}(1+x)}$. \end{corollary} If $a$ is a starting point of a run in a flattened partition $\pi$ and $x$ is an integer such that $x < a$, then $\pi^{-1}(x) < \pi^{-1}(a)$. In other words, all integers smaller than $a$ are on its left. By contradiction, suppose there exists an $x < a$ on the right of $a$. Then $x$ is an element of another run. This makes the starting points of the runs of $\pi$ not to be in increasing order, which contradicts $\pi$ being a flattened partition. Hence $x$ should be on the left of $a$. Let $\mathcal{C}_{n, k}$ denote the set of flattened partitions over $[n]$ of the form {\it $1X2\cdots $}, having $k$ runs, where $X \in \{3, 4, 5, \ldots, n\}$. More precisely, each partition in $\mathcal{C}_{n, k}$ has only two elements in the first run. For example, we have $\mathcal{C}_{5, 2} = \{13245, 14235, 15234\}$. From the construction in Theorem \ref{thm4}, we have the following corollary: \begin{corollary}\label{sss} For all integers $n$ and $k$ such that $1 \leq k < n$, the cardinality of the set $\mathcal{C}_{n, k}$ is $(n-2)f_{n-2, k-1}$. \end{corollary} Let $\mathcal{K}_{n, k}$ denote the set of flattened partitions over $[n]$ having $k$ runs and containing either the subword $\mathbf{2n1}$ or the integer $\mathbf{n}$ at the end. In other words, deleting the integer $\textbf{n}$ does not affect the number of runs. Let $\mathcal{L}_{n, k}$ denote the set of flattened partitions over $[n]$ having $k$ runs and containing the subword $\mathbf{1n2}$, the set where deleting the integer $\textbf{n}$ reduces the number of runs by $1$. For example, we have $\mathcal{L}_{5, 2} = \{12354, 12534, 15234\}$ and $\mathcal{K}_{5, 2} = \{14523, 14235, 13524, 13452, 13425, 13245, 12453, 12435\}$. \begin{remark}\label{rmk} The sets $\mathcal{K}_{n, k}$ and $\mathcal{L}_{n, k}$ are mutually exclusive, i.e., $\mathcal{K}_{n, k} \cap \mathcal{L}_{n, k} = \emptyset$ and form a partition of the set $\mathcal{F}_{n, k}$, i.e., $\mathcal{F}_{n, k} = \mathcal{K}_{n, k} \cup \mathcal{L}_{n, k}$. \end{remark} For all integers $n$ and $k$ such that $1 \leq k