\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\usepackage{mathtools}
\usepackage{booktabs}
\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}
\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}}}
\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}}
\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
Sets of Flattened Partitions \\
\vskip .1in
with Forbidden Patterns}
\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\\
Antananarivo \\
Madagascar\\
\href{mailto:frakoton@yahoo.fr}{\tt frakoton@yahoo.fr}
\end{center}
\vskip .2 in
\begin{abstract}
The study of pattern avoidance in permutations, and specifically in flattened partitions is an active area of current research. In this paper, we count the number of distinct flattened partitions over $[n]$ avoiding a single pattern, as well as a pair of two patterns. Several counting sequences, namely Catalan numbers, powers of two, Fibonacci numbers and Motzkin numbers arise. We also consider other combinatorial statistics, namely runs and inversions, and establish some bijections in situations where the statistics coincide.
\end{abstract}
\section{Introduction and preliminaries}
Counting permutations based on avoidance of a given pattern has been studied from various perspectives in both enumerative and algebraic combinatorics \cite{bona2016combinatorics, claesson2001generalized, elizalde2003consecutive, kitaev2011patterns, knuth1998art, krattenthaler2001permutations, wilf2002patterns}. It provides an easier way for understanding the properties of different combinatorial objects through bijective proofs.
For a fixed positive integer $n$, we define the set $[n]\coloneqq\{1, 2, \ldots, n\}$.
A permutation $\sigma$ over $[n]$ will be represented as a word $\sigma(1)\sigma(2)\cdots\sigma(n)$, where $\sigma(i)$ is the image of $i$ under $\sigma$. We say that $\sigma$ has an occurrence of a pattern $\tau$, if there exists a subsequence in $\sigma$ which is order-isomorphic to $\tau$, else we say that $\sigma$ is $\tau$-avoiding \cite{mansour2015counting}. The elements of an occurrence $\tau$ may be consecutive or non consecutive in $\sigma$. For example, $\sigma = 7345612$ contains several $231$ occurrences among which include: $561, 352, 362, 452, 461$ and $463$, and is $213$-avoiding. A \textit{run} in $\sigma$ is a subsequence of the form $\sigma(i)\sigma(i+1)\cdots \sigma(i+p)\sigma(i+p+1)$ where $i, i+1, \ldots, i+p$ are consecutive ascents, $i-1$ (if it does exist) and $i+p+1$ are non-ascents, where $i \in [n]$ \cite{nabawanda2020run}. We call $\sigma(i)$ the starting point of the run. A \textit{flattened partition} is a permutation consisting of runs arranged from left to right such that their starting points are in increasing order \cite{nabawanda2020run}. Notice that if $\sigma$ is a flattened partition, then $\sigma(1) = 1$. For example, the permutation $\sigma = 139278456$ is a flattened partition with three runs namely $139, 278, 456$ whose starting points are $1, 2$, and $4$ respectively.
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 ``$\tt Flatten$" from the {\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}. However, different set partitions can have the same resulting flattened partition under the command ``$\tt{Flatten}$" from Mathematica. For example $\mathtt{Flatten}(1|2|3) = 123 = \mathtt{Flatten}(12|3)$. In his work, Callan \cite{callan2009pattern} studied partitions of a set $[n]$, whose flattening avoids a single $3$-letter pattern. Along the same direction, Mansour et al.\ \cite{mansour2015counting} also studied avoidance of a single $3$-letter pattern in set partitions of size $n$. For more details on flattened partitions and pattern avoidance, see \cite{liu2015pattern, mansour2011pattern, mansour2014recurrence}. We study the number of distinct flattened partitions avoiding a pattern $\tau$, using fairly similar methods as those used by Mansour et al.\ \cite{mansour2015counting}, though we work on different sets of permutations.
\begin{definition}
Let $(i_{1}, i_{2}, i_{3}), (j_{1}, j_{2}, j_{3}) \in \mathbb{N}^3$ where $\mathbb{N}$ denotes the set of positive integers. We say that $(i_{1}, i_{2}, i_{3})$ is \emph{lexicographically smaller} than $(j_{1}, j_{2}, j_{3})$, denoted by $(i_{1}, i_{2}, i_{3}) \leq_{lex} (j_{1}, j_{2}, j_{3})$, if we have
\begin{enumerate}
\item [(i)] $i_{1} < j_{1}$ or
\item [(ii)] $i_{1} = j_{1}$ and $i_{2} < j_{2}$ or
\item [(iii)] $i_{1} = j_{1}$, $i_{2} = j_{2}$ and $i_{3} \leq j_{3}$.
\end{enumerate}
\end{definition}
A permutation $\sigma$ over $[n]$ has an \textit{ascent} or \textit{descent} at position $i$ if $\sigma(i) < \sigma(i+1)$ or $\sigma(i) > \sigma(i+1)$, respectively, for $i \in [n-1]$.
A permutation $\sigma$ over $[n]$ has an \emph{inversion} if there exists a pair $(\pi(i), \pi(j))$ for $i < j$ such that $\pi(i) > \pi(j)$.
In this paper, we count the number of \emph{distinct} flattened partitions over $[n]$ avoiding an occurrence of a single pattern $\tau$, as well as a pair of patterns $(\tau_{1}, \tau_{2})$.
Let $\tau \in \{123, 132, 213, 231, 312, 321\}$, $S(n; \tau)$ the set of all permutations over $[n]$ which are $\tau$-avoiding, $\mathcal{F}(n; \tau)$ the set of $\tau$-avoiding flattened partitions over $[n]$, and $\mathcal{F}(n; \tau_{1}, \tau_{2})$ the set of $(\tau_{1}, \tau_{2})$-avoiding flattened partitions over $[n]$. Let $|\mathcal{F}(n; \tau)|$ and $|\mathcal{F}(n; \tau_{1}, \tau_{2})|$ denote the cardinalities of the sets $\mathcal{F}(n; \tau)$ and $\mathcal{F}(n; \tau_{1}, \tau_{2})$ respectively. Let $\mathtt{inv}(\pi) = |\{{ (i, j) : i < j, \pi(i) > \pi(j)}\}|$ denote the number of inversions in a permutation $\pi$ and $\mathtt{runs}(\pi)$ the number of runs in $\pi$. In Table \ref{tab:t1}, we give the first few values of the numbers of $3$-letter pattern avoiding flattened partitions and the On-Line Encyclopedia of Integer Sequences (OEIS) they correspond to (for detailed discussions on these sequences, see Section \ref{nice}).
\begin{table}[H]
\centering
\begin{tabular}{ccc}
Pattern $\tau$ & $|\mathcal{F}(n; \tau)|_{n \geq 1}$& OEIS sequence\\
\toprule
$ 123$ & $1, 1, 1, 0, 0, 0, 0, \ldots.$ & $\cdots$\\
$ 132$ & $1, 1, 1, 1, 1, 1, 1, \ldots.$ & \seqnum{A000012}\\
$213$ & $1, 1, 2, 4, 8, 16, 32, \ldots.$ & \seqnum{A011782}\\
$ 231$ & $1, 1, 2, 4, 9, 21, 51, \ldots.$ & \seqnum{A001006}\\
$ 312$ & $1, 1, 2, 4, 8, 16, 32, \ldots.$ & \seqnum{A011782}\\
$ 321$ & $1, 1, 2, 5, 14, 42, 132, \ldots.$ & \seqnum{A000108}\\
\bottomrule
\end{tabular}
\caption{The numbers of $3$-letter pattern avoiding flattened partitions}
\label{tab:t1}
\end{table}
We say that a flattened partition avoids two patterns $\tau_{1}$ and $\tau_{2}$ if it does not contain an occurrence of either $\tau_{1}$ or $\tau_{2}$ or both. In Section \ref{sec3}, we explain the combinatorics behind the sequences in Table \ref{tab:tab9} by giving their recurrence relations and corresponding combinatorial proofs. The sequences in Table \ref{tab:tab9} were obtained by computing for the first few values of $n$ (for detailed discussions on these sequences, see Section \ref{sec3}).
\begin{table}[H]
\centering
\begin{tabular}{p{4cm}cc}
Pattern $\tau$ & $|\mathcal{F}(n; \tau)|_{n \geq 1}$ & OEIS sequence\\
\toprule
$(213, 231)$, $(231, 312)$ & $1, 1, 2, 3, 5, 8, 13, \ldots$ & \seqnum{A000045}\\
\midrule
$(132, 213)$, $(132, 231)$, $(132, 312)$, $(132, 321)$ &
$1, 1, 1, 1, 1, 1, 1, \ldots$ & \seqnum{A000012}\\
\midrule
$(213, 321)$, $(231, 321)$, $(312, 321)$ & $1, 1, 2, 4, 8, 16, 32, \ldots$ & \seqnum{A011782}\\
\midrule
$(213, 312)$ & $1, 1, 2, 3, 4, 5, 6 \ldots$ & \seqnum{A028310}\\
\midrule
$(123, 132)$ & $1, 1, 0, 0, 0, 0, 0 \ldots$ & $\cdots$\\
\midrule
$(123, 213)$, $(123, 231)$, $(123, 312)$, $(123, 321)$ & $1, 1, 1, 0, 0, 0, 0 \ldots$ & $\cdots$\\
\bottomrule
\end{tabular}
\caption{Summary of $(\tau_{1}, \tau_{2})$-avoiding flattened partitions}
\label{tab:tab9}
\end{table}
In Section \ref{nice}, we explain the combinatorics behind the sequences in Table \ref{tab:t1} by finding recurrence relations, as well as establishing bijections between flattened partitions avoiding certain patterns and other combinatorial structures counted by the same sequences. One such bijection is given in Theorem \ref{fanja}, where we show that the lengths of runs of the permutations in the involved sets are preserved. Another interesting result is Theorem \ref{learn}, where we show, using runs, that $213$-avoiding flattened partitions are counted by powers of two. We also describe the recurrence relation for $312$-avoiding flattened partitions in terms of the number of inversions preserved or created. In Section \ref{sec3}, we find recurrence relations for flattened partitions in the set $\mathcal{F}(n; \tau_{1}, \tau_{2})$ and their corresponding combinatorial proofs.
\section{Three letter pattern-avoiding flattened partitions}\label{nice}
We shall consider avoidance of patterns $\tau \in \{123, 132, 213, 231, 312, 321\}$. The cases of $123$-avoiding and $132$-avoiding flattened partitions are not very interesting: the counting sequences are $(|\mathcal{F}(n; 123)|)_{n \geq 1} = (1, 1, 1, 0, 0, \ldots)$ and $(|\mathcal{F}(n; 132)|)_{n \geq 1} = (1, 1, 1, 1, 1, \ldots)$ respectively.
\subsection{\texorpdfstring{$213$}{Lg}-avoiding}
\begin{lemma}\label{ee}
For any positive integer $n \geq 1$, a $213$-avoiding flattened partition over $[n]$ has the integer $n$ at the end of its first run.
\end{lemma}
\begin{proof}
Let $\sigma \in \mathcal{F}(n; 213)$. Suppose $n$ is not in the first run of $\sigma$. Then $n$ would be the last element in of any of the remaining runs of $\sigma$. For some $j > 2$, let $\sigma(j)$ be the starting point of the second run. Then we would have a $213$-occurrence $\sigma(j-1)\sigma(j)n$, a contradiction.
\end{proof}
\begin{proposition}\label{viot}
Let $p_{1}, p_{2}, \ldots, p_{r}, q_{r-1}, \ldots, q_{1}$ be non-empty words such that the concatenation \begin{equation}\label{happy}
p_{1}p_{2}\cdots p_{r}q_{r-1}q_{r-2}\cdots q_{1} = 123\cdots n.
\end{equation}
Then $\pi = p_{1}q_{1}|p_{2}q_{2}| \cdots |p_{r-1}q_{r-1}|p_{r}$ is an element in $\mathcal{F}(n; 213)$ and all elements in $\mathcal{F}(n; 213)$ are of this form.
\end{proposition}
\begin{proof}
It is obvious from Equation \eqref{happy} that $p_{1}q_{1}, p_{2}q_{2}, \ldots, p_{r-1}q_{r-1}, p_{r}$ are runs. The permutation $\pi$ is flattened because the starting points of the runs from Equation \eqref{happy} appear in increasing order. If we had a $213$-occurrence, then there would exist integers $m < j < k$ such that $\pi(j) < \pi(m) < \pi(k)$. Then $\pi(m)$ and $\pi(j)$ can not be in the same run. Let $\pi(m) \in p_{i}q_{i}$ and $\pi(j) \in p_{i+s}q_{i+s}$. Then $\pi(m)$ belongs to $q_{i}$ (because by Equation \eqref{happy} if it belonged to $p_{i}$, we would have an increasing sequence). Moreover, $\pi(k)$ can belong to $p_{i+t}$ or $q_{i+t}$ for some $t \geq s$. Using Equation \eqref{happy}, we would have $\pi(k)$ appearing to the left of $\pi(m)$ in the identity permutation i.e., $\pi(k) < \pi(m)$, which is against the assumptions. Thus indeed $\pi \in \mathcal{F}(n; 213)$.
Next we prove that all $\mathcal{F}(n; 213)$ have the form $p_{1}q_{1}p_{2}q_{2}\cdots p_{r-1}q_{r-1}p_{r}$ where the sub-words $p_{i}$ and $q_{i}$ are non-empty and have consecutive elements and satisfy Equation \eqref{happy}. Suppose $\sigma \in \mathcal{F}(n; 213)$ and consider its first run $R_{1}$. From Lemma \ref{ee}, $R_{1}$ ends with the integer $n$. Since $\sigma$ is flattened, then it is obvious that $R_{1}$ starts with $1$. If $\sigma$ is the identity permutation, $\mathtt{id}$, then $\mathtt{id} = p_{1}$. If $\sigma \not= \mathtt{id}$, let $R_{1} = c_{1}c_{2}\cdots c_{l}$ where $l \geq 2$ and each $c_{i}$ consists of consecutive numbers which are grouped in non-empty maximal words of $R_{1}$. In particular, $c_{1} = 123\cdots k$, and $c_{l} = m(m+1)\cdots n$ for some $1 \leq k < m \leq n$. We note that $k+1$ is the first element of $R_{2}$ (the second run of $\sigma$). Now suppose $l \geq 3$ and let $k'$ be the last element of $c_{2}$. Then $k'+1$ is not in $R_{1}$. Thus we have $$\sigma = 12\cdots k\cdots k'\cdots n|(k+1)\cdots (k'+1),$$ where $k+1 < k'$. Then $k'(k+1)(k'+1)$ would be a $213$-occurrence, a contradiction. Hence $l = 2$ and $R_{1} = c_{1}c_{2}$ where $c_{1} = 12\cdots k$ and $c_{2} = m(m+1)\cdots n$. Let the remaining runs be denoted as $R_{2}R_{3}\cdots R_{r} = \sigma'$. Then $\sigma'$ is a permutation of the elements $\{k+1, \ldots, m-1\}$. We note that the permutation $\sigma'-k$ is $213$-avoiding and flattened. By an inductive argument, the claim is indeed true.
\end{proof}
\begin{theorem}\label{learn}
For any integer $n \geq 2$, we have \begin{equation*}
\sum_{\pi \in \mathcal{F}(n; 213)} q^{\mathtt{runs}(\pi)} = \sum_{r \geq 1}q^{r}{n-1 \choose 2r-2}. \end{equation*} Consequently, $|\mathcal{F}(n; 213)| = 2^{n-2}$ with $|\mathcal{F}(1; 213)| = 1$.
\end{theorem}
\begin{proof}
Let us construct a flattened partition $\pi$ over $[n]$ having $r$ runs, and with $2r-1$ sub-words $p_{1}, \ldots, p_{r}, q_{r-1}, \ldots, q_{1}$ such that $p_{1}p_{2}\cdots p_{r}q_{r-1}\cdots q_{1} = 123\cdots n$, as in Equation \eqref{happy}. Then $\pi$ is constructed uniquely from $123\cdots n$ by choosing $2r-2$ spaces from the $n-1$ spaces between the numbers, and then use them as demarcations between the $2r-1$ sub-words. There are $\displaystyle n-1 \choose 2r-2$ such choices. Summing over $r \geq 1$ gives the desired result.
\end{proof}
\begin{example}
Let us construct a flattened partition $\pi \in \mathcal{F}(9; 213)$ having $3$ runs. Consider the sequence $1\llcorner\!\lrcorner2\llcorner\!\lrcorner3\llcorner\!\lrcorner4\llcorner\!\lrcorner5\llcorner\!\lrcorner6\llcorner\!\lrcorner7\llcorner\!\lrcorner8\llcorner\!\lrcorner9$, which has $8$ spaces. Then $\pi$ is determined from this sequence by choosing $4$ of them as demarcations. We may for instance choose $12\llcorner\!\lrcorner3\llcorner\!\lrcorner45\llcorner\!\lrcorner67\llcorner\!\lrcorner 89$. Since there are three runs, we then label the first three blocks as $p_{1} = 12$, $p_{2} = 3$, and $p_{3} = 45$. Then the remaining blocks are $q_{2} = 6$ and $q_{1} = 78$. Thus we have $\pi = p_{1}q_{1}p_{2}q_{2}p_{3} = 12783645 \in \mathcal{F}(9, 213)$.
\end{example}
\begin{theorem}\label{fanja}
For any integer $n \geq 3$, \begin{equation*}
\sum_{\pi \in \mathcal{F}(n; 312)}x_{1}^{\alpha_{1}(\pi)}\cdot x_{2}^{\alpha_{2}(\pi)}\cdots x_{r}^{\alpha_{r}(\pi)} = \sum_{\pi' \in \mathcal{F}(n; 213)}x_{1}^{\alpha_{1}(\pi')}\cdot x_{2}^{\alpha_{2}(\pi')}\cdots x_{r}^{\alpha_{r}(\pi')},
\end{equation*} where $\alpha_{i}(\pi)$ is the length of the $i^{th}$ run of $\pi$. Consequently, putting $x_{i} = 1$, we have $|\mathcal{F}(n; 213)| = |\mathcal{F}(n; 312)|$.
\end{theorem}
\begin{remark}
Note that in each $\pi$ or $\pi'$, the number of factors corresponds to the number of runs $r$ in $\pi$.
\end{remark}
\begin{proof}
We shall define a mapping $f(\pi) = \pi' \in \mathcal{F}(n; 213)$ which associates to each first run $R_{1}$ of $\pi \in \mathcal{F}(n; 312)$ a corresponding first run $R_{1}'$ of $\pi'$ of the same length as described below. We shall also provide an inverse $g$ to $f$. If $\pi$ is the identity permutation, then $f(\pi) = \pi = \pi'$, else by the same arguments as in Proposition \ref{viot}, we have that $R_{1}$ consists of two non-empty sub-words: $p_{1} = 123\cdots k$ and $q_{1} = m(m+1)\cdots t$, with one gap between them, for some $t \leq n$ and $k < m$. Hence $m \geq k+2$. Suppose $ m > k+2$, then $k+1$ would be the starting point of the second run and $k+2$ would be anywhere on the right of $k+1$ in $\pi$. Hence we would have a $312$ occurrence $m(k+1)(k+2)$, a contradiction. Hence $m = k+2$. By Proposition \ref{viot}, $R_{1}'$ should consist of two non-empty sub-words $p_{1}'$ and $q_{1}'$ of consecutive elements. We put $p_{1}' \colon= p_{1}$, and the sub-word $q_{1}'$ of $\pi'$ is got by adding a term $(n-t)$ to each element of $q_{1}$ i.e., $q_{1}' = q_{1} + (n-t)= (m+n-t)(m+n+1-t)\cdots n$. Let $\sigma$ be the resulting sub-word obtained from $\pi$ after removing $R_{1}$ and then writing the remaining elements of $\pi$ in standard form. Applying the mapping $f$ on $\sigma$ we obtain $\sigma'$, for which adding $k$ to each element of its elements gives $\pi' = R_{1}'(\sigma' + k)$ which indeed is $213$-avoiding.
The inverse mapping $g$ could be constructed recursively in an analogous manner as for $f$. Note that $p_{1} = p_{1}'$ and that $q_{1}$ and $q_{1}'$ have the same length. It suffices to note that $R_{1}$ and $R_{1}'$ have the same lengths and hence the mapping $f$ preserves the lengths and the number of the runs in $\pi$ and $\pi'$ and is a bijection.
\end{proof}
\begin{example}
Consider $\pi = 13|246|5 \in \mathcal{F}(6; 312)$. Applying the mapping $f$ on the first run $R_{1} = 13$ gives $R_{1}' = 16$ with $k = 1$. The resulting sub-word $246|5$ when standardized gives $\sigma = 124|3 \in \mathcal{F}(4; 312)$. Again applying $f$ on $124|3$ gives $\sigma' = 124|3$ and $\sigma'+1 = 235|4$. Thus $\pi' = R_{1}'(\sigma'+1) = 16|235|4$.
\end{example}
\begin{proposition}\label{vvv}
A $\pi \in \mathcal{F}(n; 213)$ contains at least one $312$ occurrence if and only if $f(\pi) \in \mathcal{F}(n; 312)$ contains at least one $213$ occurrence.
\end{proposition}
\begin{proof}
Let $\mathcal{F}(n; 213, 312)$ be the set consisting of all $\sigma$ which do not contain any $312$ and $213$ occurrences. Then under the mapping $f$, we have that $f(\sigma) = \sigma$. From Theorem \ref{fanja}, the sets $\mathcal{F}(n; 213)$ and $\mathcal{F}(n; 312)$ have the same sizes. Thus the sizes of the sets $A = \mathcal{F}(n; 213)\setminus \mathcal{F}(n; 213, 312)$ and $B = \mathcal{F}(n; 312)\setminus \mathcal{F}(n; 213, 312)$ are also the same. This proves the claim.
\end{proof}
\subsection{\texorpdfstring{$312$}{Lg}-avoiding}\label{ffb}
\begin{proposition}\label{qh}
A $312$-avoiding flattened partition starts with either $12$ or $13$.
\end{proposition}
\begin{proof}
Let $\pi$ be a $312$-avoiding flattened partition. Suppose that $\pi$ starts with $1i$ where $i \geq 4$. Then $2$ is the starting point of the second run. The integer $3$ appears on the right of $2$. Hence $\pi$ would contain a $312$ occurrence $i23$. Hence $i \leq 3$.
\end{proof}
\begin{proposition}\label{ww1}
Interchanging the $2$ and $3$ in a $312$-avoiding flattened partition preserves the avoidance property.
\end{proposition}
\begin{corollary}\label{ww}
For any integer $n \geq 3$, the number of $312$-avoiding flattened partitions over $[n]$ starting with $12$ is equal to the number of $312$-avoiding flattened partitions over $[n]$ starting with $13$.
\end{corollary}
This is because in each $312$-avoiding flattened partitions over $[n]$ starting with $12$, interchanging $2$ and $3$ gives a $312$-avoiding flattened partitions over $[n]$ starting with $13$, and vice versa.
\begin{theorem}\label{qa}
For all $n \geq 1$, \begin{equation*}
\sum_{\pi \in \mathcal{F}(n; 312)} q^{\mathtt{inv}(\pi)} = (1+q)^{n-2}.
\end{equation*}
\end{theorem}
\begin{proof}
It suffices to prove that \begin{equation*}
\sum_{\pi \in \mathcal{F}(n; 312)} q^{\mathtt{inv}(\pi)} = \sum_{\pi \in \mathcal{F}(n-1; 312)} q^{\mathtt{inv}(\pi)}(1+q).
\end{equation*} For $n = 1, 2$, the identity is the only $312$- avoiding flattened partition. From Proposition \ref{qh} and Corollary \ref{ww}, there are only two classes of $312$-avoiding flattened partitions: one class starting with $12$ and another one starting with $13$ and their sizes are equal. To create the first class, we consider a $312$-avoiding flattened partition $\pi$ of length $n-1$ and insert the integer $1$ at the beginning of $\pi$. We then increase by $1$ the remaining terms to get a $312$-avoiding flattened partition $\sigma$ of length $n$. Let $P_{n}(q) = \sum_{\pi \in \mathcal{F}(n; 312)} q^{\mathtt{inv}(\pi)}$. Then the first class contributes $1\cdot P_{n-1}(q)$ inversions. To create the second class, we interchange the integers $2$ and $3$ of the first class. Hence the second class contributes $q \cdot P_{n}(q)$ inversions. Summing the inversions proves the theorem.
\end{proof}
\subsection{\texorpdfstring{$321$}{Lg}-avoiding}
\begin{theorem}\label{ooj}
For any integer $n \geq 1$, we have $|\mathcal{F}(n; 321)| = C_{n-1}$, where $C_{n} = \frac{1}{n+1}{2n \choose n}$ is the $n^{th}$ Catalan number with $C_{0} = 1$.
\end{theorem}
\begin{proof}
As shown by Knuth in \cite{knuth2014art}, we have that $|\mathcal{S}(n-1; 321)| = C_{n-1}$. Thus the proof of Theorem \ref{ooj} follows from Lemma \ref{jorg}.
\begin{lemma}\label{jorg}
For $n \geq 1$, there exists a bijection $h: \mathcal{F}(n; 321) \rightarrow \mathcal{S}(n-1; 321)$ defined by removing integer $1$ from $\pi \in \mathcal{F}(n; 321)$ and reducing the remaining $\pi$ elements by $1$.
\end{lemma}
It is easy to see how to construct the inverse mapping $h' : \mathcal{S}(n-1; 321) \rightarrow \mathcal{F}(n; 321)$, and that both $h$ and $h'$ preserve $321$ avoidance. One observation worth noting is that $h'(\sigma)$ is a flattened partition even if $\sigma \in \mathcal{S}(n-1; 321)$ is not. The only obstruction to this would be if the first entries of the runs (except the first run) of $\sigma$ are not in increasing order. In this case, it would imply that there exists integers $b$ and $a$ both starting points of such runs such that $b > a$, although $a$ occurs later. Then there would exist an integer $c > b > a$ in the first run such that $cba$ is a $321$ occurrence.
\end{proof}
\subsection{\texorpdfstring{$231$}{Lg}-avoiding}
\begin{lemma}\label{ino}
Let $n$ be a positive integer and $\pi$ be a $231$-avoiding flattened partition of length $n$. There exists an integer $2 \leq k \leq n$ such that:
\begin{enumerate}
\item [(i)] $\pi(i) < k$ if $i < k$,
\item [(ii)] $\pi(k) = n$,
\item [(iii)] $\pi(i) \geq k$ if $i > k$.
\end{enumerate}
\end{lemma}
\begin{proof}
Let $k = \pi(n)^{-1}$ and $\pi = 1\pi(2)\cdots\pi(k-1)n\pi(k+1)\cdots \pi(n)$. Let $m = \max \{\pi(j) : 1 \leq j \leq k-1\}$. Necessarily, $\pi(l) > m$ for all $k+1 \leq l \leq n$ since else there would be a $231$ occurrence $mna$ where $a = \pi(l) < m$. Hence $k = m+1$.
\end{proof}
\begin{theorem}\label{ff}
For any positive integer $n \geq 3$, we have
\begin{equation}\label{nik}
|\mathcal{F}(n; 231)| = |\mathcal{F}(n-1; 231)| + \sum_{k=2}^{n-1}|\mathcal{F}(k-1; 231)||\mathcal{F}(n-k; 231)|
\end{equation} with initial values $|\mathcal{F}(1; 231)| = 1, \:|\mathcal{F}(2; 231)| = 1$.
\end{theorem}
Thus $|\mathcal{F}(n; 231)| = M_{n-1}$, where $M_{n}$ is the $n^{th}$ Motzkin number (\seqnum{A001006}) with $M_{0} = 1$ as given by Aigner \cite{manu}.
\begin{proof}
We consider two cases depending on $k$: one case when $k < n$ and another case when $k = n$. In the latter case, inserting $n$ at the end of each $\pi' \in \mathcal{F}(n-1; 231)$ gives $\pi \in \mathcal{F}(n; 231)$. Hence we have $|\mathcal{F}(n-1; 231)|$ unique flattened partitions having $n$ at the end of each $\pi$.
In the case $k < n$, there are two subsequences on the left and right of $n$ for each $\pi \in \mathcal{F}(n; 231)$ i.e., $1\pi(2)\cdots\pi(k-1)$ and $\pi(k+1)\cdots \pi(n)$ of lengths $k-1$ and $n-k$ respectively. Let $\pi_{1} = 1\pi(2)\cdots\pi(k-1)$ and $\pi_{2} = \pi(k+1)\cdots \pi(n)$. We note that subtracting integer $k-1$ from each element of $\pi_{2}$ gives $\pi \in \mathcal{F}(n-k; 231)$. By Lemma \ref{ino}, we have that each $\pi_{1} \in \mathcal{F}(k-1; 231)$. Multiplying and summing over $k$ indeed gives $\sum_{k=2}^{n-1}|\mathcal{F}(k-1; 231)||\mathcal{F}(n-k; 231)|$.
Summing the two cases together proves the claim.
\end{proof}
Alternatively, we also give a bijection between $231$-avoiding flattened partitions and the well known Motzkin paths which are also counted by Motzkin numbers.
First, we introduce the so called \textit{Motzkin permutations} because they are in bijection with Motzkin paths. This was proved by Mansour et al.\ \cite{man4}. A permutation $\sigma$ is said to be Motzkin if it avoids pattern $132$ and there are no integers $i < j$ for which $\pi(i) < \pi(j) < \pi(j+1)$. The latter condition corresponds to avoidance of a kind of generalized patterns introduced by Babson and Steingr\'imsson \cite{man5}. There is a bijection $\alpha: \mathcal{M}_{n-1} \rightarrow \mathcal{F}(n; 231)$ between the set of Motzkin permutations over $[n-1]$ and $231$-avoiding flattened partitions over $[n]$ defined by the following: For each $\sigma \in \mathcal{M}_{n-1}$, increase by $1$ all elements of $\sigma$ and reverse their order to obtain $\pi'$. Then insert integer $1$ at the beginning of $\pi'$ to obtain $\alpha(\sigma) = \pi \in \mathcal{F}(n; 231)$. We remark that avoidance of pattern $132$ in $\sigma \in \mathcal{M}_{n-1}$ corresponds to avoidance of pattern $231$ in $\pi$. On the other hand, avoidance of the generalized pattern corresponds to $\pi \in \mathcal{F}(n)$.
\section{Avoidance of pairs of three letter patterns in flattened partitions}\label{sec3}
We shall consider avoidance of a pair of patterns $(\tau_{1}, \tau_{2})$ of length three. The cases of $(123, 132)$-avoiding and $((123, 213)$-, $(123, 231)$-, $(123, 312)$-, $(123, 321))$-avoiding flattened partitions are not very interesting: the counting sequences for $n \geq 1$ are $(1, 1, 0, 0, 0, \ldots)$ and $(1, 1, 1, 0, 0, \ldots)$ for the latter cases respectively. Similarly, the pairs $((132, 213)$, $(132, 231)$, $(132, 312)$, $(132, 321))$ all have a trivial counting sequence $(1, 1, 1, 1, 1, \ldots)_{n \geq 1}$. In the subsections that follow, we consider avoidance of the remaining pairs of patterns.
\subsection{\texorpdfstring{$(213, 231)$}{Lg}-avoiding}
Here, we consider the problem of avoiding both $213$ and $231$ patterns.
\begin{proposition}\label{zz}
Let $n \geq 1$ be a positive integer. If $\pi$ is a $(213, 231)$-avoiding flattened partition, then there exists an integer $2 \leq k \leq n$ such that
\begin{enumerate}
\item[(i)] $\pi(i) = i$ for $ 1 \leq i \leq k-1$,
\item[(ii)] $\pi(k) = n$,
\item[(iii)] $\pi(i) \geq k$ for $k+1 \leq i \leq n$.
\end{enumerate}
\end{proposition}
\begin{proof}
Let $\pi = 1\pi(2)\cdots \pi(k-1)n\pi(k+1)\cdots \pi(n), x = \max\{\pi(j) : 1 \leq j \leq k-1\}$. By Proposition \ref{ee}, the integer $n$ must be at the end of the first run. By Theorem \ref{ino}, the integers $1, 2, \ldots , k-1$ are also elements of the first run. Hence conditions $(i)$ and $(ii)$ are satisfied. Necessarily, $\pi (y) > x$ for all $k+1 \leq y \leq n$, $\pi(y) \geq x$ since else there would be a $231$ occurrence $xny$ . Hence $k = x+1$.
\end{proof}
\begin{lemma}\label{m}
For any integer $n \geq 1$, all elements of $\mathcal{F}(n; 213, 231)$ start with either $12$ or $1n$.
\end{lemma}
The proof is similar to that of Proposition \ref{qh}, just that in this case, we suppose that $\pi \in \mathcal{F}(n; 213, 231)$ starts with $1i$ where $ 3 \leq i \leq n-1$ and then prove by contradiction that this is not possible.
\begin{proposition}
For any integer $n \geq 1$, we have $|\mathcal{F}(n; 213, 231)| = F_{n}$ where $F_{n}$ is the Fibonacci number with initial conditions $F_{1} = F_{2} = 1$.
\end{proposition}
\begin{proof}
We prove this claim by induction. For $n = 1, 2$, the identity is the only $(213, 231)$-avoiding flattened partition.
For $n \geq 3$, from Lemma \ref{m}, there are two classes of $(213, 231)$-avoiding flattened partition: one class starting with $12$ and another class starting with $1n$. To create the first class, for each $\pi' \in \mathcal{F}(n-1; 213, 231)$, inserting $1$ at the beginning of $\pi'$ and then increasing by $1$ the remaining terms gives $|\mathcal{F}(n-1; 213, 231)|$ unique flattened partitions. To create the second class, for each $\pi' \in \mathcal{F}(n-2; 213, 231)$, inserting the subsequence $1n$ at the beginning of $\pi'$, and then increasing the remaining elements by $1$ gives $|\mathcal{F}(n-2; 213, 231)|$ unique flattened partitions. It is clear that removing $1$ or the subsequence $1n$ from each $\pi \in \mathcal{F}(n; 213, 231)$ that starts with $12$ or $1n$ respectively gives the elements in the sets $\mathcal{F}(n-1; 213, 231)$ or $\mathcal{F}(n-2; 213, 231)$. Thus inductively,
\begin{equation*}
|\mathcal{F}(n; 213, 231)| = |\mathcal{F}(n-1; 213, 231)| + |\mathcal{F}(n-2; 213, 231)| = F_{n-1} + F_{n-2} = F_{n}.
\end{equation*}
\end{proof}
\begin{example}
Let us construct flattened partitions $\pi \in \mathcal{F}(6; 213, 231)$. Inserting $1$ at the beginning of each elements in $\mathcal{F}(5; 213, 231) = \{15234, 15243, 12345, 12354, 12534\}$, and then increasing the remaining elements by $1$ gives $\pi$ in the class starting with $12$. On the other hand, inserting the subsequence $16$ at the beginning of each element in the set $\mathcal{F}(4; 213, 231) = \{1234, 1243, 1423\}$, and then increasing the remaining elements by $1$ gives $\pi$ in the second class.
\end{example}
Let us denote by $F(n, k)$ the number of $(213, 231)$-avoiding flattened partitions with $r$ runs, in which the first run $R_{1}$ has length $k$.
\begin{proposition}\label{v}
For all integers $k, n$ such that $1 \leq k < n$, we have $F(n, k) = F_{n-k},$ where $F_{n-k}$ is the $(n-k)^{th}$ Fibonacci number.
\end{proposition}
\begin{proof}
By Proposition \ref{zz}, $R_{1}$ is unique since given its length $k$, then $R_{1} = 12\cdots (k-2)(k-1)n$. The remaining runs denoted as $R_{2}R_{3}\cdots R_{r}$ thus have length $n-k$. Let $R_{2}R_{3}\cdots R_{r} = \sigma'$. We note that removing integer $k-1$ from each element of $\sigma'$ gives $\pi \in \mathcal{F}(n-k; 213, 231)$ and vice versa. Thus, \begin{equation*}F(n, k) = |\mathcal{F}(n-k; 213, 231)| = F_{n-k} \end{equation*}
\end{proof}
\begin{proposition}
The ordinary generating function $F(u, x)$ for the number of $(213, 231)$-avoiding flattened partitions is given by \begin{equation*} F(u, x) = \frac{1-u-u^2 + u^3 x^2}{(1-ux)(1-u-u^2)}.\end{equation*}
\end{proposition}
\begin{proof}
Letting \begin{equation*}F(u, x) = \sum_{n\geq 0}\sum_{k\geq 0} F(n, k)x^k u^n\end{equation*} and using Proposition \ref{v} gives the required result.\end{proof}
\subsection{\texorpdfstring{$(312, 231)$}{Lg}-avoiding}
\begin{proposition}
For any integer $n \geq 1$, we have $|\mathcal{F}(n; 312, 231)| = F_{n}$ where $F_{n}$ is the Fibonacci number with initial conditions $F_{1} = F_{2} = 1$.
\end{proposition}
\begin{proof}
We prove the claim by induction. For $n = 1, 2$, the identity permutation is the only $(312, 231)$-avoiding flattened partition.
For $n \geq 3$, from Proposition \ref{qh}, there are two classes of $(312, 231)$-avoiding flattened partition: one class starting with $12$ and another class starting with $13$. To create the first class, for each $\pi' \in \mathcal{F}(n-1, 312, 231)$, inserting $1$ at the beginning of $\pi'$ and then increasing by $1$ the remaining terms gives $|\mathcal{F}(n-1, 312, 231)|$ unique flattened partitions. To create the second class, for each $\pi' \in \mathcal{F}(n-2, 312, 231)$, inserting the subsequence $13$ at the beginning of $\pi'$, and then increasing the first element of $\pi'$ by $1$, and the remaining elements by $2$ gives $|\mathcal{F}(n-2, 312, 231)|$ unique flattened partitions. It is clear that removing $1$ or the subsequence $13$ from each $\pi \in \mathcal{F}(n, 312, 231)$ that starts with $12$ or $13$ respectively gives elements in the sets $\mathcal{F}(n-1, 312, 231)$ or $\mathcal{F}(n-2, 312, 231)$. Thus inductively, \begin{equation*}
|\mathcal{F}(n, 312, 231)| = |\mathcal{F}(n-1, 312, 231)| + |\mathcal{F}(n-2, 312, 231)| = F_{n-1}+ F_{n-2} = F_{n}.
\end{equation*}
\end{proof}
\begin{example}
Let us construct flattened partitions $\pi \in \mathcal{F}(6, 312, 231)$. Inserting $1$ at the beginning of each elements in $\mathcal{F}(5, 312, 231) = \{13245, 13254, 12345, 12354, 12435\}$, and then increasing the remaining elements by $1$ gives $\pi$ in the class starting with $12$. On the other hand, inserting the subsequence $13$ at the beginning of each element in the set $\mathcal{F}(4, 312, 231) = \{1234, 1243, 1324\}$, and then increasing the first element in this set by $1$ and the remaining elements by $2$ gives $\pi$ in the second class.
\end{example}
\subsection{\texorpdfstring{$(213, 312)$}{Lg}-avoiding}
From Proposition \ref{qh}, we have already seen that $312$-avoiding flattened partitions either start with $12$ or $13$. Hence $(213, 312)$-avoiding flattened partitions also have the same classes. However, there is only one flattened partition in this class that starts with $13$.
\begin{lemma}\label{luck}
For $n \geq 3$, the only $\pi \in \mathcal{F}(n; 213, 312)$ that starts with $13$ has $2$ as a singleton second run.
\end{lemma}
\begin{proof}
Since $\pi$ starts with $13$, then $2$ is the starting point of the second run and $3 \in R_{1}$. Suppose $\pi$ has at least two runs and that the second run is not singleton. Then there would exist an integer $c > 3 > 2$ to the right of $2$ such that we have a $213$ occurrence $32c$. Since the position of $1, 2$ and $3$ are are known, then the remaining $n-3$ elements can be arranged in $R_{1}$ as an increasing sequence in $R_{1}$ after $3$ and there is only one way this can be done.
\end{proof}
\begin{proposition}
For any integer $n \geq 3$, the number of $(213, 312)$-avoiding flattened partitions satisfies the recurrence relation $|\mathcal{F}(n; 213, 312)| = |\mathcal{F}(n-1; 213, 312)| + 1$ with initial condition $|\mathcal{F}(2; 213, 312)| = 1$.
\end{proposition}
\begin{proof}
From Lemma \ref{luck}, there is exactly one $\pi' \in \mathcal{F}(n-1; 213, 312)$ that starts with $13$. Inserting $n$ at the end of the first run of $\pi'$ gives $1$ unique flattened partition $\pi \in \mathcal{F}(n; 213, 312)$ that starts with $13$. By Proposition \ref{qh}, the second class of $(213, 312)$-avoiding flattened partitions starts with $12$. To create this class, we insert $1$ at the beginning of each $\pi' \in \mathcal{F}(n-1; 213, 312)$, and then increase the remaining elements of $\pi'$ by $1$. This gives $|\mathcal{F}(n-1; 213, 312)|$ unique flattened partitions. It is clear that removing $1$ or $n$ from each $\pi \in \mathcal{F}(n; 213, 312)$ that starts with $12$ or $13$ respectively gives the elements in the set $\mathcal{F}(n-1; 213, 312)$ or the only element in $\mathcal{F}(n-1; 213, 312)$ that starts with $13$.
\end{proof}
\subsection{\texorpdfstring{$(213, 321)$}{Lg}-avoiding}
\begin{proposition}
For any positive integer $n \geq 2$, \begin{equation}\label{gl}
|\mathcal{F}(n; 213, 321)| = |\mathcal{F}(n-1; 213, 321)| + n-2
\end{equation} with initial conditions $|\mathcal{F}(1; 213, 321)| = 1$. Consequently, \begin{equation}\label{gb}
|\mathcal{F}(n; 213, 321)| = {n-1 \choose 2} + 1.
\end{equation}
\end{proposition}
\begin{proof}
For each $\sigma \in \mathcal{F}(n-1; 213, 321)$ and using Lemma \ref{ee}, inserting $n$ at the end of the first run preserves the number of runs and gives $\pi \in \mathcal{F}(n; 213, 321)$ with the subsequence $(n-1)n$ at the end of the first run. This gives $|\mathcal{F}(n-1; 213, 321)|$ unique flattened partitions. For the identity flattened partition $\textit{id} \in \mathcal{F}(n-1; 213, 321)$, there are $(n-2)$ more choices of inserting $n$ into positions $n-1, n-2, \ldots, 2$ respectively in $\textit{id}$ to create an element $\pi \in \mathcal{F}(n; 213, 321)$. If $\sigma \in \mathcal{F}(n-1; 213, 321)$ is not the identity and we suppose that $n$ appears in the first run before $n-1$, then there exists an integer $a < n-1$, a starting point of the second run such that $\textit{n(n-1)a}$ is a $321$ occurrence. Thus such cases can not exist. Summing up gives Equation \eqref{gl}, and solving this easy recursion gives Equation \eqref{gb}.
\end{proof}
\subsection{\texorpdfstring{$(231, 321)$}{Lg}-avoiding}
\begin{proposition}
For any $n \geq 2$, $|\mathcal{F}(n; 231, 321)| = 2^{n-2}$.
\end{proposition}
\begin{proof}
For $n \geq 3$, there are two classes of $(231, 321)$-avoiding flattened partitions: one class that starts with $12$ and another class that starts with $1i$ for $3 \leq i \leq n$. Necessarily, in the latter class, $2$ is the starting point of the second run, and the first run has exactly two elements. Otherwise there exists integers $i, j$ in the first run, for $1 < i < j$, for which we would have a $231$-occurrence $ij2$.
To create the first class, we insert $1$ at the beginning of each $\pi' \in \mathcal{F}(n-1; 231, 321)$ and then increase the remaining elements of $\pi'$ by $1$. This gives $|\mathcal{F}(n-1; 231, 321)|$ unique flattened partitions. To create the second class, we increase all elements in $\pi' \in \mathcal{F}(n-1; 231, 321)$ that start with $1i$ except the first element by $1$ and then insert $2$ in the third position. This gives $|\mathcal{F}(n-1; 231, 321)|$ unique flattened partitions. It is clear how to invert these constructions. Thus we have \begin{equation*}
|\mathcal{F}(n; 231, 321)| = 2|\mathcal{F}(n-1; 231, 321)|,
\end{equation*} with initial condition $|\mathcal{F}(2; 231, 321)| = 1$. Solving this recursion proves the claim.
\end{proof}
\begin{remark}
All $(312, 321)$-avoiding flattened partitions have similar properties and structure as $312$-avoiding flattened partitions studied in Subsection \ref{ffb}.
\end{remark}
\begin{remark}
There are many subsequent follow-up questions one can ask about flattened partitions avoiding some patterns, but these will be addressed separately.
\end{remark}
\section{Acknowledgment}
The first author acknowledges the financial support extended by the
Swedish Sida Phase-IV bilateral program with Makerere University. Special
thanks go to Prof.\ J\"orgen Backelin, Prof.\ Paul Vaderlind, and Dr.\
Per Alexandersson of Stockholm University, Department of Mathematics,
and Dr.\ Alex Samuel Bamunoba of Makerere University, Department of
Mathematics, for their valuable input and suggestions. Many thanks
to my colleagues from CoRS---Combinatorial Research Studio,
for lively discussions and comments.
\begin{thebibliography}{99}
\bibitem{manu}
M. Aigner, Motzkin numbers, \textit{European J. Combin.} {\bf 19} (1998), 663–-675.
\bibitem{man5}
E. Babson and E. Steingr\'imsson, Generalized permutation patterns and a classification of the Mahonian statistics, \textit{S\'em. Lothar. Combin.} {\bf 44} (2000), \#B44b.
\bibitem{bona2016combinatorics}
M. B{\'o}na, {\it Combinatorics of Permutations}, CRC Press, 2016.
\bibitem{callan2009pattern}
D. Callan, Pattern avoidance in ``flattened" partitions, {\it Discrete Math.} {\bf 309} (2009), 4187--4191.
\bibitem{claesson2001generalized}
A. Claesson, Generalized pattern avoidance, \textit{European J. Combin.} {\bf 22} (2001), 961--971.
\bibitem{man4}
S. Elizalde and T. Mansour, Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polynomials, {\it Discrete Math.} {\bf 305} (2005), 170--189.
\bibitem{elizalde2003consecutive}
S. Elizalde and M. Noy, Consecutive patterns in permutations, {\it Adv. Appl. Math.} {\bf 30} (2003), 110--125.
\bibitem{kitaev2011patterns}
S. Kitaev, {\it Patterns in Permutations and Words}, Springer Science \& Business Media, 2011.
\bibitem{knuth1998art}
D. E. Knuth, {\it The Art of Computer Programming, Volume 3: Sorting and Searching}, Addison-Wesley Professional, 1998.
\bibitem{knuth2014art}
D. E. Knuth, {\it Art of Computer Programming, Volume 2: Seminumerical Algorithms}, Addison-Wesley Professional, 2014.
\bibitem{krattenthaler2001permutations}
C. Krattenthaler, Permutations with restricted patterns and Dyck paths, \textit{Adv. Appl. Math.} {\bf 27} (2001), 510--530.
\bibitem{liu2015pattern}
T. Y. H. Liu and A. Zhang, On pattern avoiding flattened set partitions, \textit{Acta Math. Sin. (Engl. Ser.)} {\bf 31} (2015), 1923--1928.
\bibitem{mansour2012combinatoric}
T. Mansour, {\it Combinatorics of Set Partitions}, CRC Press, 2012.
\bibitem{mansour2011pattern}
T. Mansour and M. Shattuck, Pattern avoidance in flattened permutations, {\it Pure Math. Appl. (PU.M.A.)} {\bf 22} (2011), 75--86.
\bibitem{mansour2015counting}
T. Mansour, M. Shattuck, and S. Wagner, Counting subwords in flattened partitions of sets, {\it Discrete Math.} {\bf 338} (2015), 1989--2005.
\bibitem{mansour2014recurrence}
T. Mansour, M. Shattuck, and D. G. L. Wang, Recurrence relations for patterns of type $(2, 1)$ in flattened permutations, {\it J. Difference Equ. Appl.} {\bf 20} (2014), 58--83.
\bibitem{nabawanda2020run}
O. Nabawanda, F. Rakotondrajao, and A. S. Bamunoba, Run distribution over flattened partitions, {\it J. Integer Sequences} {\bf 23} (2020), Article 20.9.6.
\bibitem{rota1964number}
G. Rota, The number of partitions of a set, \textit{Amer. Math. Monthly} {\bf 71} (1964), 498--504.
\bibitem{wilf2002patterns}
H.S. Wilf, The patterns of permutations, {\it Discrete Math.} {\bf 257} (2002), 575--583.
\bibitem{stephen1999mathematica}
S. Wolfram, {\it The Mathematica Book}, Cambridge University Press, 2000.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 05A05; Secondary 05A10, 05A15, 05A18.
\noindent \emph{Keywords:} Catalan number, Fibonacci number, flattened partition, Motzkin number, pattern, run, inversion.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A000012},
\seqnum{A000045},
\seqnum{A000108},
\seqnum{A001006},
\seqnum{A011782}, and
\seqnum{A028310}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received December 5 2020;
revised version received January 1 2021.
Published in {\it Journal of Integer Sequences}, January 2 2021.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}