\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\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,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\usepackage{xspace}
\usepackage{multirow}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\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 Enumeration of Two Particular Sets of  \\
\vskip .12in
Minimal Permutations
}
\vskip 1cm
\large
Stefano Bilotta,
Elisabetta Grazzini,\footnote{ Corresponding author.} and Elisa Pergola\\
Dipartimento di Matematica e Informatica ``Ulisse Dini''\\
Universit\`a di Firenze\\
Viale G. B. Morgagni 65\\
50134 Firenze \\
Italy\\
\href{mailto:egrazzini@unifi.it}{\tt egrazzini@unifi.it} 
\end{center}


\newcommand{\mini}{ minimal permutations with $d$ descents and
size $d+2$ }



\vskip .2in


\begin{abstract}
Minimal permutations with $d$ descents and size $d+2$ have a
unique ascent between two sequences of descents. Our aim is the
enumeration of two particular sets of these permutations. The
first set contains the permutations having $d+2$ as the top
element of the ascent.  The permutations in the latter set have
$1$ as the last element of the first sequence of descents and are
the reverse-complement of those in the other set. The main result
is that these sets are enumerated by the second-order Eulerian
numbers.
\end{abstract}

\section{Introduction}
\subsection{Preliminary definitions}
A permutation of size $n$ is a bijective map from $\{1..n\}$ to
itself. We denote by $S_n$ the set of permutations of size $n$. We
consider a permutation $\sigma \in S_n$ as the word $\sigma_1
\sigma_2 \cdots \sigma_n$ of $n$ letters on the alphabet
$\{1,2,\ldots,n\}$, containing each letter exactly once (we often
use the word \emph{element} or \emph{entry} instead of letter).
For example, $6\,2\,4\,3\,5\,1$ represents the permutation $\sigma
\in S_6$ such that $\sigma_1 = 6, \sigma_2 = 2, \ldots, \sigma_6 =
1$.


\begin{definition} Let $\sigma$ be a permutation
in $S_n$. We say that $\sigma$ has a \emph{descent} in position
$i$ whenever $\sigma_i>\sigma_{i+1}$. In the same way, we say that
$\sigma$ has an \emph{ascent} in position $i$ whenever
$\sigma_i<\sigma_{i+1}$.
\end{definition}
\begin{example}
The permutation $\sigma = 6\,9\,8\,4\,1\,3\,7\,2\,5 \in S_9$ has
$4$ descents, namely in positions $2$, $3$, $4$, $7$, and $4$
ascents in positions $1$, $5$, $6$ and $8$.

\label{ex:descent}
\end{example}

\begin{definition}Let $\sigma$ be a permutation
in $S_n$. The \emph{reverse} of $\sigma$ is the permutation
$\sigma^r=\sigma_n \sigma_{n-1} \cdots \sigma_1$. The
\emph{complement} of $\sigma$ is the permutation $\sigma^c=
(n+1-\sigma_1)(n+1-\sigma_2) \cdots
(n+1-\sigma_n)$.\label{def:revcompl}
\end{definition}
\begin{example}
If $\sigma = 4\,2\,6\,5\,3\,1$, then $\sigma^r =
1\,3\,5\,6\,2\,4$,  $\sigma^c= 3\,5\,1\,2\,4\,6$ and $\sigma^{rc}
= \sigma^{cr} = 6\,4\,2\,1\,5\,3$. \label{ex:revcompl}
\end{example}
\begin{definition}
A permutation $\pi \in S_k$ is a \emph{pattern} of a permutation
$\sigma \in S_n$ if there is a subsequence of $\sigma$ which is
order-isomorphic to $\pi$, i.e., if there is a subsequence
$\sigma_{i_1} \sigma_{i_2} \cdots \sigma_{i_k}$ of $\sigma$, $1
\leq i_1 < i_2 <\cdots<i_k \leq n$,
such that $\sigma_{i_{\ell}} < \sigma_{i_m}$ whenever $\pi_{\ell} < \pi_{m}$. \\
We also say that $\pi$ is \emph{contained} in $\sigma$ and call
$\sigma_{i_1} \sigma_{i_2} \cdots \sigma_{i_k}$ an
\emph{occurrence} of $\pi$ in $\sigma$.  \label{def:pattern}
\end{definition}

\begin{example}
The permutation $\sigma = 3\,1\,2\,8\,5\,4\,7\,9\,6$ contains the
pattern $1\,2\,3\,4$ since $\sigma_2 \, \sigma_3\,
\sigma_5\,\sigma_7$ is an increasing subsequence of size $4$.
\end{example}

We write $\pi \prec \sigma$ to denote that $\pi$ is a pattern of
$\sigma$. A permutation $\sigma$ that does not contain $\pi$ as a
pattern is said to \emph{avoid} $\pi$. The class of all
permutations avoiding the patterns $\pi1, \pi2, \ldots, \pi k$ is
denoted $S(\pi1, \pi2, \ldots, \pi k)$. We say that $S(\pi1, \pi2,
\ldots, \pi k)$ is a class of pattern-avoiding permutations of
\emph{basis} $\{\pi1, \pi2, \ldots, \pi k\}$.

\subsection{Minimal permutations with $d$ descents}
Minimal permutations with $d$ descents arise from biological
motivations \cite{BV10, BR09, SODA06}. Among the many models for
genome evolution, the \emph{whole genome duplication - random loss
model} represents genomes with permutations, that can evolve
through \emph{duplication-loss steps} representing the biological
phenomenon that duplicates fragments of genomes, and then loses
one copy of every duplicated gene \cite{math.CO}. Bouvel and
Rossin \cite{BR09} showed that the class of permutations obtained
in this model after a given number $p$ of steps is a class of
pattern-avoiding permutations of finite basis, and proved the
following theorem.
\begin{theorem}\label{thm:p-steps}
The class of permutations obtainable by at most $p$ steps in the
whole genome duplication - random loss model is a class of
pattern-avoiding permutations whose basis $\mathcal{B}_d$ is
finite and is composed of the minimal permutations with $d=2^p$
descents, minimal being intended in the sense of $\prec$.

\end{theorem}


In this paper, we focus on the basis $\mathcal{B}_d$ of excluded
patterns appearing in Theorem \ref{thm:p-steps}. More generally,
we do not assume that $d$ is a power of $2$. From here on, by
minimal permutation with $d$ descents, we mean a permutation that
is minimal with respect to the pattern-involvement relation
$\prec$ for the property of having $d$ descents.
\begin{example}
Let  $\sigma = 7\,4\,1\,3\,2\,5\,8\,6\,9$ be a permutation with
$4$ descents; $\sigma$ is not minimal with $4$ descents. Indeed,
the elements $1$ and $5$ can be removed from $\sigma$ without
changing the number of descents. Doing this, we obtain permutation
$\pi = 5\,3\,2\,1\,6\,4\,7$ which is minimal with $4$ descents: it
is impossible to remove an element from it while preserving the
number of descents equal to $4$. However, $\pi$ is not of minimal
\emph{size} among the permutation with $4$ descents: $\pi$ has
size $7$ whereas permutation $5\,4\,3\,1\,2$ has $4$ descents but
size $5$. \label{ex:d-desc}
\end{example}


A characterization of minimal permutations with $d$ descents is
given in Proposition~\ref{prop:neces}, whose proof is given in
\cite{math.CO}.

\begin{proposition}\label{prop:neces}
Let $\sigma$ be a minimal permutation with $d$ descents. Then
every ascent of $\sigma$ is immediately preceded and immediately
followed by a descent, and the size $n$ of $\sigma$ satisfies $d+1
\leq n\leq2d$.
\end{proposition}

The condition provided by Proposition~\ref{prop:neces} is not
sufficient to give a characterization of minimal permutations with
$d$ descents.
\begin{example}\label{ex:necess} The permutation $\sigma =
7\,5\,1\,3\,2\,10\,8\,4\,9\,6$, with $6$ descents, does not
contain consecutive ascents. However, $\sigma$ is not minimal as
it contains the pattern $\pi = 6\,4\,2\,1\,9\,7\,3\,8\,5$, which
is minimal with $6$ descents.
\end{example}

An exhaustive characterization of minimal permutations, as given
in \cite{math.CO}, can be summarized in the following theorem,
giving a local characterization of minimal permutations with $d$
descents.

\begin{theorem}
A permutation $\sigma$ of size $n$ is minimal with $d$ descents if
and only if it has exactly $d$ descents and its ascents $\sigma_i
\sigma_{i+1}$ are such that $2 \leq i \leq n-2$ and $\sigma_{i-1}
\sigma_i \sigma_{i+1} \sigma_{i+2}$ forms an occurrence of either
the pattern $2143$ or the pattern $3142$.
\label{thm:characterization}
\end{theorem}

The characterization of minimal permutations with $d$ descents in
Theorem~\ref{thm:characterization} directly leads to a
\emph{partially ordered set} (or \emph{poset}) representation of
permutations.

Consider the set of all minimal permutations of size $n$ with $d$
descents, and having their descents and ascents in the same
positions. In all these permutations, the elements are locally
ordered in the same way, even around the ascents, because of
Theorem~\ref{thm:characterization}. This whole set of permutations
can be represented by a partially ordered set indicating the
necessary conditions on the relative order of the elements between
them. For a descent, there is a link from the first and greatest
element to the second and smallest one. For any ascent
$\sigma_i\sigma_{i+1}$, the elements
$\sigma_{i-1}\sigma_i\sigma_{i+1}\sigma_{i+2}$ form a
diamond-shaped structure with $\sigma_{i+1}$ at the top,
$\sigma_i$ at the bottom, $\sigma_{i-1}$ on the left and
$\sigma_{i+2}$ on the right. By
Theorem~\ref{thm:characterization}, any labelling of the elements
of the poset respecting its ordering constraints is a minimal
permutation with $d$ descents. See Figure~\ref{fig:labelling} for
an example.


\begin{figure}[ht]
\begin{center}

\centerline{\hbox{\includegraphics[height=5cm]{fig3.eps}}}
\end{center}
 \caption{Permutations and
authorized labelling of the posets}\label{fig:labelling}
\end{figure}

We will say that a permutation $\sigma$ satisfies the diamond
property when each of its ascents $\sigma_i\sigma_{i+1}$ is such
that $\sigma_{i-1}\sigma_i\sigma_{i+1}\sigma_{i+2}$ forms a
diamond, that is to say is an occurrence of either $2143$ or
$3142$.

\subsection{Outline of the paper} As claimed in
Proposition~\ref{prop:neces}, the size of minimal permutations
with $d$ descents is at least $d+1$ and at most $2d$. Obviously
there is only one minimal permutation with $d$ descents and size
$d+1$, that is the reverse identity permutation $(d+1)d(d-1)\cdots
321$.

Bouvel and Pergola \cite{math.CO} found that the number of minimal
permutations with $d$ descents and maximal size $2d$ is given by
the $d$-th Catalan number $c_d=\frac{1}{d+1}{2d \choose d}$.

Mansour and Yan \cite{MY10} showed that the number of minimal
permutations with $d$ descents and size $2d-1$ is
$2^{d-3}(d-1)c_d$. They also obtained (i) a recurrence relation on
the multivariate generating function for the minimal permutations
of length $n$, for fixed $n$, counted by the number of descents,
and the values of the first and second elements of the
permutation, (ii) a recurrence relation on the multivariate
generating function for the minimal permutations of length $n$
with $n-d$ descents, for fixed $d$, counted by the length, and the
values of the first and second elements of the permutation.

In this paper we are interested in minimal permutations with $d$
descents and size $d+2$ (minimal non trivial case). Let us recall
that a minimal permutation with $d$ descents and size $d+2$ has a
unique ascent, between two sequences of descents, and that the
elements surrounding the ascent are organized in a diamond in the
poset representation of the permutation. Therefore, the greatest
element $d+2$ is either the first entry of the permutation or the
top element of the diamond.


Our aim is the enumeration of two particular sets of minimal
permutations with $d$ descents and size $d+2$.  The first set
$\mathcal{M}_1$ we deal with contains the permutations such that
$d+2$ is the top element of the diamond. The other set
$\mathcal{M}_2$ contains the permutations in which the first
sequence of descents ends with the entry $1$.

The main result is that both these sets are enumerated by the
second-order Eulerian numbers.

Bouvel and Pergola \cite{math.CO} obtained a closed formula for
the enumeration of minimal permutations with $d$ descents and size
$d+2$ as reported in the following theorem.
\begin{theorem}\label{thm:enum} The minimal permutations  with $d$
descents and size $d+2$ are enumerated by the sequence $(s_d)$
defined as follows: $s_d=2^{d+2}-(d+1)(d+2)-2$. \end{theorem}

In particular, they give a proof of Theorem~\ref{thm:enum}
defining two  bijections $\Phi^1$ and $\Phi^2$ between the set of
minimal permutations with $d$ descents and size $d+2$ and the
non-interval subsets of $\{1,2, \ldots,d+1\}$.

We will use these bijections to enumerate the sets $\mathcal{M}_1$
and $\mathcal{M}_2$. Therefore, in Section~\ref{sec:bij} we recall
the definition of the bijections $\Phi^1$ and $\Phi^2$.

The enumeration of the sets $\mathcal{M}_1$ and $\mathcal{M}_2$ is
obtained in Sections \ref{sec:m1} and \ref{sec:m2}, respectively.
As corollaries of this main result, we obtain the enumeration of
other subsets of minimal permutations with $d$ descents and size
$d+2$. See table~\ref{tab:listcount}  at the end of the paper,
where we list the counting sequences connected to our results.


\section{The bijections $\Phi^1$ and $\Phi^2$}\label{sec:bij}

We need to recall the bijections between  the non-interval subsets
of $\{1,2,\ldots,d+1\}$ and the set of minimal permutation with
$d$ descents and size $d+2$ to proceed.

A \emph{non-interval subset} of $\{1,2,\ldots,d+1\}$  is a
non-empty subset of $\{1,2,\ldots,d+1\}$   that is not an
interval. The number of non-interval subsets of
$\{1,2,\ldots,d+1\}$ is $2^{d+1}-\frac{(d+1)(d+2)}{2}-1$
\cite{math.CO}. To prove Theorem~\ref{thm:enum} Bouvel and Pergola
\cite{math.CO} showed that there are twice as many permutations
with $d$ descents and size $d+2$ as non-interval subsets of
$\{1,2,\ldots,d+1\}$ . For this purpose they partitioned  the set
of minimal permutations with $d$ descents and size $d+2$ into two
subset $S^1$ and $S^2$, and defined two bijections between $S^1$
and $S^2$, respectively, and the set of non-interval subsets of
$\{1,2,\ldots,d+1\}$ , denoted as $\mathcal{N}\ell$.

The set $S^1$ contains the\mini such that (i) $d+2$ is the top
element of the diamond and (ii) the elements in the first sequence
of descents are not consecutive. The set $S^2$ contains all the
other minimal permutations with $d$ descents and size $d+2$.

Let $s$ be a non-interval subset of $\{1,2,\ldots,d+1\}$, and let
$w=\{1,2,\ldots,d+1\}\setminus s$ be the set of ``wholes''
associated with s.

The bijection $\Phi^1$ between $\mathcal{N}\ell$ and $S^1$ is
defined as follows: the permutation $\Phi^1(s)$ consists of the
elements of $s$ in decreasing order, followed by $d+2$ and then by
the elements of $w$ in decreasing order.

\begin{example}In this example and in the following ones we consider $d=5$.
Given $s=\{3,5,6\}$, and $w=\{1,2,4\}$, $\Phi^1(s)$ is the minimal
permutation $6\,5\,3\,7\,4\,2\,1$ with $5$ descents and size $7$.
\end{example}

In order to define the bijection between $\mathcal{N}\ell$ and
$S^2$, Bouvel and Pergola \cite{math.CO} divided the permutations
in $S^2$ into five types, from \texttt{A} to \texttt{E} in the
following way.

Let $\sigma$ be a permutation of $S^2$. Then $\sigma$  is of one
of the five types:

\begin{itemize}
\item[\texttt{A)}] (i) $d+2$ is the top element of the diamond,
                (ii) the first sequence of descents contains only two consecutive elements;
\item[\texttt{B)}] (i) $d+2$ is the top element of the diamond,
                (ii) the first sequence of descents contains at least three consecutive elements,
               (iii) the second sequence of descents has the form $(d+2)(d+1)r$,
                       where $r = \emptyset$  or $r = k(k-1)(k-2)\ldots 1$, for some
                       $k \geq 1$;

\item[\texttt{C)}] (i) $d+2$ is the top element of the diamond,
(ii) the first sequence of descents contains at least three
consecutive elements, (iii) the second sequence of descents of has
the form $(d+2)(d+1)r_1r_2$, were $r_1= d  \ldots (d-\ell)$, for
some $\ell \geq 0$, $r_2 =\emptyset$  or $r_2 = k(k-1)(k-2)\ldots
1$, for some $k \geq 1$. Notice that $r_1$ cannot be empty;

\item[\texttt{D)}](i) $d+2$ is the first element, (ii) the second
sequence of descents contains consecutive elements;

\item[\texttt{E)}] (i) $d+2$ is the first element, (ii) the second
sequence of descents contains not consecutive elements.
\end{itemize}


Now we can describe the application $\Phi^2$ from
$\mathcal{N}\ell$ to $S^2$. Let $s$ be a non-interval subset of
$\{1,2,\ldots,d+1\}$, and let $w$ be the associate set of wholes.
\begin{description}
\item[\texttt{A)}] If $w$ contains only one element $x$, then
necessarily $x\neq 1$ and $x\neq d+1$. In this case, $\Phi^2(s)$
is the permutation of type \texttt{A} whose first sequence of
descents is $x(x-1)$.
\begin{example} Given $s=\{1,2,3,5,6\}$, and $w=\{4\}$, $\Phi^2(s)$ is the
permutation  $4\,3\,7\,6\,5\,2\,1$ of type \texttt{A}.
\end{example}
\end{description}
If $w$ contains at least two elements, let $n$ be the cardinality
of the non-interval subset $s$, and let $m$ be the cardinality of
the associated set $w$ increased by $1$. Moreover, let $w_1$ and
$w_2$ be the smallest and the second-smallest elements of $w$, and
let $s_{n-1}$ and $s_n$ be the greatest and the second-greatest
elements of $s$. The permutation $\Phi^2(s)$ will contain $m$
elements on its first sequence of descents and $n$ on its second,
according to the relative order of $w_1$, $w_2$, $s_{n-1}$, and
$s_n$. Notice that $m \geq 3$, $n \geq 2$, and $w_1 < s_n$.

\begin{description}
\item[\texttt{B)}] If $s_{n-1} < w_1<s_n<w_2$ , then $s=\{1,
\ldots,n-1,n+1\}$ and consequently $w=\{n,n+2, \ldots, d+1\}$. The
permutation $\Phi^2(s)$ is of type \texttt{B} and it is such that
(i) the second sequence of descents starts with $(d+2)(d+1)$ and
then contains $n-2$ consecutive elements from $n-2$ to $1$, (ii)
the first sequence of descents contains $m$ consecutive elements
starting with $d$.

\begin{example} Given $s=\{1,2,4\}$, and $w=\{3,5,6\}$, $\Phi^2(s)$ is the
permutation $5\,4\,3\,2\,7\,6\,1$ of type \texttt{B}.
\end{example}

\item[\texttt{C)}] If $w_1< s_{n-1} <s_n<w_2$, then $s=\{1,
\ldots, w_1-1, w_1+1, \ldots, n+1\}$ and $w=\{w_1, n+2, \ldots,
d+1\}$, i.e., $w_2=n+2$. To determine the non-interval set $s$ it
is sufficient to know its cardinality $n$ and the number
$p=n+1-w_1$ of elements between $w_1$ and $w_2$. Since $s_{n-1}$
and $s_n$ are between $w_1$ and $w_2$ and $s$ is non-interval, $p$
satisfies the conditions $2\leq p \leq n-1$. The permutation
$\Phi^2(s)$ of type \texttt{C} is obtained as follows. The second
sequence of descents splits into two parts (the second one
possibly empty). The first part contains $p+1$ consecutive
elements in decreasing order starting with $d+2$; the second part
is composed of $n-p-1$ consecutive elements from $n-p-1$ to $1$.
The remaining $m$ elements, written in decreasing order,
constitute the first sequence of descents.

\begin{example} Given $s=\{1,2,4,5\}$, $w=\{3,6\}$, then $p=2$ and
the type \texttt{C} permutation $\Phi^2(s)$ is
$5\,4\,3\,2\,7\,6\,1$.
\end{example}

\item[\texttt{D)}] If $s_{n-1} <w_1<w_2 < s_n$, then
$s=\{1,2,\ldots,n-1,s_n\}$. The permutation $\Phi^2(s)$ is of type
\texttt{D} and its is such that (i) the second sequence of
descents contains $n$ consecutive elements in decreasing order
starting with $s_n$, (ii) the first sequence of descents starts
with $d+2$ and then contains the remaining $m$ elements in
decreasing order.

\begin{example} Given $s=\{1,2,6\}$, $w=\{3,4,5\}$,
the type \texttt{D} permutation $\Phi^2(s)$ is
$7\,3\,2\,1\,6\,5\,4$.
\end{example}

\item[\texttt{E)}] If $w_1<w_2 < s_{n-1} <s_n$ or $w_1<s_{n-1}
<w_2 < s_n$, then $\Phi^2(s)$ is the permutation of type
\texttt{E} obtained as follows. The first sequence of descents of
$\Phi^2(s)$ starts with $d+2$ and then contains the elements of
$w$ in decreasing order; the second sequence of descents contains
the element of $s$ in decreasing order.

\begin{example} Given $s=\{3,5,6\}$, $w=\{1,2,4\}$,
the type \texttt{E} permutation $\Phi^2(s)$ is
$7\,4\,2\,1\,6\,5\,3$.
\end{example}
\end{description}
The $32$ minimal permutations with $4$ descents and size $6$
($d=4$) associated with the $16$ non-interval subsets of
$\{1,2,3,4,5\}$ by the bijections $\Phi^1$ and $\Phi^2$,
respectively, are shown in table~\ref{tab:d4}.

\begin{table}[ht]
\begin{center}
\begin{tabular}{|l|l|l|lc|}
\hline \multicolumn{1}{|c|}{$s$}&\multicolumn{1}{c|}{$w$}& $\Phi^1(s)$&$\Phi^2(s)$&Type\\
\hline$\{1,2,4,5\}$&$\{3\}$&542163&326541&\texttt{A}\\
$\{1,2,3,5\}$&$\{4\}$&532164&436521&\texttt{A}\\
$\{1,3,4,5\}$&$\{2\}$&543162&216543&\texttt{A}\\
$\{1,2,4\}$&$\{3,5\}$&421653&432651&\texttt{B}\\
$\{1,2,5\}$&$\{3,4\}$&521643&621543&\texttt{D}\\
$\{1,3,4\}$&$\{2,5\}$&431652&321654&\texttt{C}\\
$\{1,3,5\}$&$\{2,4\}$&531642&642531&\texttt{E}\\
$\{1,4,5\}$&$\{2,3\}$&541632&632541&\texttt{E}\\
$\{2,4,5\}$&$\{1,3\}$&542631&631542&\texttt{E}\\
$\{2,3,5\}$&$\{1,4\}$&532641&641532&\texttt{E}\\
$\{1,3\}$&$\{2,4,5\}$&316542&432165&\texttt{B}\\
$\{1,4\}$&$\{2,3,5\}$&416532&652143&\texttt{D}\\
$\{1,5\}$&$\{2,3,4\}$&516432&632154&\texttt{D}\\
$\{2,4\}$&$\{1,3,5\}$&426531&653142&\texttt{E}\\
$\{2,5\}$&$\{1,3,4\}$&526431&643152&\texttt{E}\\
$\{3,5\}$&$\{1,2,4\}$&536421&642153&\texttt{E}\\
\hline
\end{tabular}
\end{center}
\caption{Minimal permutations with $4$ descents and size $6$
($d=4$)} \label{tab:d4}
\end{table}


\section{The enumeration of $\mathcal{M}_1$}\label{sec:m1} In this section we will count the
permutations in the set $\mathcal{M}_1$, that is, the\mini which
have $d+2$ as the second element of the unique ascent.

Referring to the definitions given in Section~\ref{sec:bij}, the
set $\mathcal{M}_1$ contains all the permutations in $S^1$ and the
permutations of type \texttt{A}, \texttt{B}, and \texttt{C}.

Owing to the bijection $\Phi^1$ between the set $S^1$ and the set
$\mathcal{N}\ell$, the number $N_{S^1}$ of\mini in $S^1$ is
\begin{equation}\label{eq:numnl}
N_{S^1}=2^{d+1}-\frac{(d+1)(d+2)}{2}-1.
\end{equation}

The\mini of type \texttt{A} are associated by the bijection
$\Phi^2$ with the sets $s$ such that the corresponding sets $w$
contain only one element $x$ with $x\neq 1$ and $x\neq d+1$.
Therefore, there exists one permutation of type \texttt{A} for
each possible value of $x$. Consequently, the number $N_A$ of
permutations of type \texttt{A} is
\begin{equation}\label{eq:tipoa}
N_A= d-1.
\end{equation}

If $\sigma =\Phi^2(s)$ is a permutation of type \texttt{B}, then
$s$ is completely determined by its cardinality $n$. Thus, there
exists only one permutation of type \texttt{B} for each possible
value of $n$. Since $n$ ranges from $2$ to $d-1$, the number $N_B$
of permutations of type \texttt{B} is
\begin{equation}\label{eq:tipob}
N_B=d-2.
\end{equation}

Because of the definition of $\Phi^2$, the permutations of type
\texttt{C} depend on the cardinality $n$ of $s$ and on the
smallest element $w_1$ of $w$. Since $w_1$ satisfies the
conditions $2 \leq w_1 \leq n-1$,  there are $n-2$ possible values
of $w_1$ for each value of $n$. Moreover, for the permutations of
type \texttt{C}, $n$ satisfies the conditions $3 \leq n\leq d-1$.
Therefore, the number $N_C$ of permutations of type \texttt{C} is
\begin{eqnarray}\label{eq:tipoc}
N_C&=&\sum_{n=3}^{d-1}(n-2)=\sum_{n=1}^{d-3}n\nonumber\\
&=&\frac{(d-3)(d-2)}{2}.
\end{eqnarray}

\begin{theorem}\label{thm:m1} The\mini having $d+2$ as the top element of the
diamond are enumerated by the sequence $(m_1)_d$ defined as
follows: \begin{equation}\label{eq:m1}(m_1)_d=
2^{d+1}-2(d+1).\end{equation}
\end{theorem}
\begin{proof}The total number of\mini in  $\mathcal{M}_1$ is given by
$N_{S^1}+N_A+N_B+N_C$, that is
\begin{eqnarray*}\label{eq:tot}
N_{S^1}+N_A+N_B+N_C&=&2^{d+1}-\frac{(d+1)(d+2)}{2}-1 + (d-1)+
(d-2)
+\frac{(d-3)(d-2)}{2}\\
&=&2^{d+1}-2(d+1).
 \end{eqnarray*}
\end{proof}

 The first terms of the sequence~\eqref{eq:m1} are $2,8,22,52,114,240,494 \ldots$, for $d \geq
 2$.
 They are the \emph{second-order Eulerian numbers } and
 correspond to the sequence \seqnum{A005803} in the On-line Encyclopedia of Integer Sequence
 \cite{OEIS}.


\begin{corollary}\label{cor:first}The\mini whose first entry is $d+2$ are
enumerated by the sequence $(f)_d$ defined as follows:
\begin{equation}\label{eq:tot1} (f)_d=2^{d+1}-d(d+1)-2.\end{equation}
\end{corollary}
\begin{proof} Since\mini start with $d+2$ or have $d+2$ as the
second element of the unique ascent, the number of\mini whose
first entry is $d+2$ is given by the difference between the total
number of these permutations (see Theorem~\ref{thm:enum}) and
$(m_1)_d$. This number is
$$2^{d+2}-(d+1)(d+2)-2-[2^{d+1}-2(d+1)] = 2^{d+1}-d(d+1)-2.$$
\end{proof}

The first terms of the sequence~\eqref{eq:tot1} are $0,2, 10, 32,
84, 198, 438, \ldots$, for $d \geq 2$. This sequence does not
appear in \cite{OEIS}.


\section{The enumeration of $\mathcal{M}_2$}\label{sec:m2}
The set $\mathcal{M}_2$ contains the\mini whose first sequence of
descents ends with $1$, that is having 1 as the bottom element of
the diamond.

Let $\sigma$ be a permutation in $\mathcal{M}_1$ with the ascent
in position $i$ and $\sigma_{i+1}= d+2$. By
Definition~\ref{def:revcompl}, $\sigma^{rc}_1= d+3-\sigma_{d+2}$,
$\sigma^{rc}_2= d+3-\sigma_{d+1}, \ldots$, $\sigma^{rc}_{d+2-i-1}=
d+3-\sigma_{i+2}$, $\sigma^{rc}_{d+2-i}= d+3-\sigma_{i+1}$,
$\sigma^{rc}_{d+2-i+1}= d+3-\sigma_{i}$, $\sigma^{rc}_{d+2-i+2}=
d+3-\sigma_{i-1}, \ldots$,
  $\sigma^{rc}_{d+2}=d+3-\sigma_{1}$, (see
Example~\ref{ex:revcompl}).

Since $$\sigma^{rc}_1 > \sigma^{rc}_2 > \cdots
>\sigma^{rc}_{d+2-i-1} >\sigma^{rc}_{d+2-i}=1
<\sigma^{rc}_{d+2-i+1}<\sigma^{rc}_{d+2-i+2}< \cdots
<\sigma^{rc}_{d+2}$$ $\sigma^{rc}$ is a permutation of size
$(d+2)$ with $d$ descents where the unique ascent is in position
$d+2-i$ and the first sequence of descents ends with $1$.
Moreover,  since
$\sigma^{rc}_{d+2-i-1}\sigma^{rc}_{d+2-i}\sigma^{rc}_{d+2-i+1}\sigma^{rc}_{d+2-i+2}$
forms an occurrence of either the pattern $2143$ or the pattern
$3142$, (depending on $\sigma$), $\sigma^{rc}$ is a minimal
permutation of size $d+2$ with $d$ descents, (see
Theorem~\ref{thm:characterization}).

Therefore the permutations in $\mathcal{M}_2$ are the
reverse-complement of those in $\mathcal{M}_1$ and the following
theorem holds.

\begin{theorem} \label{thm:m2} The\mini having $1$ as the bottom element of the
diamond are enumerated by the sequence $(m_2)_d$ defined as
follows: \begin{equation}\label{eq:m2}(m_2)_d=
2^{d+1}-2(d+1).\end{equation}
\end{theorem}

Since in a minimal permutation $\sigma$ with $d$ descents and size
$d+2$ the entry $1$ is at the end of the first sequence of
descents or it is the last element of $\sigma$, the proof of the
following corollary is straightforward.
\begin{corollary}\label{cor:last}The\mini whose last entry is $1$ are
enumerated by the sequence $(f)_d$ defined in
Corollary~\ref{cor:first}.
\end{corollary}

\begin{corollary}\label{cor1d}The\mini whose unique ascent is $1\,(d+2)$ are
enumerated by the sequence $(g)_d$ defined as follows:
\begin{equation}\label{eq:tot1d} (g)_d=2^{d}-2.\end{equation}
\end{corollary}
\begin{proof}
By the definition of the bijection $\Phi^2$, the \emph{unique}
minimal permutation with $d$ descents and size $d+2$ of type
\texttt{A} in which the bottom element of the diamond is $1$ is
the the permutation $2\,1\,(d+2)\,(d+1)\,d \cdots 3$.

Similarly, if a permutation of type \texttt{B} has 1 as the bottom
element of the diamond then the associated non-interval subset has
cardinality $2$. Therefore, there is an \emph{unique} minimal
permutation with $d$ descents and size $d+2$ of type \texttt{B}
whose first sequence of descents ends with 1, and it is the
permutation $\Phi^2(s)$ where $s=\{1,3\}$ and
$w=\{2,4,\ldots,d+1\}$, that is the permutation $d\,(d-1)\cdots
2\,1\,(d+2)\,(d+1)$.

The\mini of type \texttt{C} in $\mathcal{M}_2$ are those in which
the segment $r_2$ of the second sequence of descent is empty.
Recall that the first sequence of descent contains at least three
elements. By the definition of $\Phi^2(s)$ for permutations of
type\texttt{C}, $r_2$ is empty if $n-p-1=0$, that is $w_1=2$, as
$p=n+1-w_1$. Therefore, for each value of the cardinality $n$ of
$s$ there is only one permutation of type \texttt{C} in which 1 is
the bottom element of the diamond. Since $n$ ranges from $3$ to
$d-1$, the number of\mini of type \texttt{C} in $\mathcal{M}_2$ is
$d-3$.

To sum up,  the total number $M_{ABC}$ of\mini of type \texttt{A},
\texttt{B}, and \texttt{C} with unique ascent $1\,(d+2)$ is
\begin{equation}\label{eq:totABC}
M_{ABC} = 1+1+ (d-3) = d-1.
\end{equation}


Now we have just to count the permutations in $S^1$ having $1$ at
the end of the first sequence of descents. The first sequence of
descents in a permutations $\Phi^1(s)$ contains the elements of
$s$ in descending order. Therefore, it is sufficient to count the
non-interval sets $s$ containing the entry $1$. Given the
cardinality $n$, if $s$ contains $1$ then the other $n-1$ elements
are
\begin{itemize}
\item a non-interval set of cardinality $n-1$. As we have seen
before, the intervals of length $n-1$ are $d+1-(n-1)$, so the
non-interval sets of cardinality $n-1$ are ${d \choose n-1}-
(d+1)+(n-1)$,

\item or an interval of length $n-1$ without the entry $2$. As
before, it is simple to see that the intervals of length $n-1$
starting with $3$ are $d+1-n$.
\end{itemize}

Thus, the non-interval sets $s$ of cardinality $n$ containing the
entry $1$ are
\begin{equation}\label{eq:totsn}
{d \choose n-1}- (d+1)+(n-1)+d+1-n = {d \choose n-1}-1.
\end{equation}

Hence, the permutations in $S^1$ having $1$ at the end of the
first sequence of descents are
\begin{eqnarray}\label{eq:totS1}
M_{S^1}&=& \sum_{n=2}^d[{d \choose n-1}-1]\nonumber\\ &=&
\sum_{n=2}^d{d \choose n-1} -
\sum_{n=2}^d 1\nonumber\\
&=& 2^d- {d \choose 0}-{d \choose d}-(d-1)\nonumber\\
&=&2^d-d-1.
\end{eqnarray}
The number of\mini having the pair $1\,(d+2)$ as unique ascent is
$$M_{S^1}+M_{ABC}= 2^d-d-1+d-1 = 2^d-2.$$
\end{proof}





The first terms of the sequence~\eqref{eq:tot1d} are
$2,6,14,30,62,126,254 \ldots$, for $d \geq
 2$.
 They correspond to the sequence \seqnum{A000918} in the On-line Encyclopedia of Integer Sequence
 \cite{OEIS}. This sequence is the first differences of \seqnum{A005803},
 as noted in \cite{OEIS}. Then the\mini whose unique ascent is $1\,(d+2)$
are a combinatorial interpretation of the first differences of
\seqnum{A005803}.

\begin{corollary}\label{cord1}The\mini having the first or the
second sequence of descents starting with $d+2$ and ending with
$1$ are enumerated by the sequence $(h)_d$ defined as follows:
\begin{equation}\label{eq:totd1} (h)_d=2^{d}-2d.\end{equation}
\end{corollary}
\begin{proof}The number of\mini whose first sequence of descents
is $(d+2) \cdots 1$ is given by the difference between the number
of\mini having $1$ as the bottom element of the diamond (see
Theorem~\ref{thm:m2}) and the number of those having the pair
$1\,(d+2)$ as unique ascent (see Corollary~\ref{cor1d}), that is
$$2^{d+1}-2(d+1)-(2^{d}-2) = 2^d-2d.$$
The number of\mini whose second sequence of descents is $(d+2)
\cdots 1$ is obtained in a similar way from Theorem~\ref{thm:m1}
and Corollary~\ref{cor1d}.
\end{proof}

\begin{corollary}\label{cord21} The\mini having $d+2$ as the first
entry and $1$ as the last one are enumerated by the sequence
$(k)_d$ defined as follows:
\begin{equation}\label{eq:totd21} (k)_d=2^{d}-d(d-1)-2.\end{equation}
\end{corollary}
\begin{proof}The number of\mini having $1$ as the last entry is $2^{d+1}-d(d+1)-2$ (see
Corollary~\ref{cor:last}). If from this set we cancel those
permutation having $d+2$ as the top element of the diamond (see
Corollary~\ref{cord1}) we obtain the set of\mini having $d+2$ as
the first entry and $1$ as the last one, whose cardinality  is
given by
$$2^{d+1}-d(d+1)-2-(2^d-2d)= 2^d-d(d-1)-2.$$
\end{proof}
The first terms of the sequence~\eqref{eq:totd21} are
$0,0,2,10,32,84,198 \ldots$, for $d \geq
 2$.


\begin{table}[H]
\begin{center}
\resizebox{\columnwidth}{!}{%
\begin{tabular}{|l|l|l|l|l|}
\hline \multicolumn{1}{|c|}{\small{Shape of the
permutation}}&\multicolumn{1}{|c|}{\small{Number of}}
&\multicolumn{1}{|c|}{\small{Formula}}&\multicolumn{1}{|c|}{\small{OEIS}}&\multicolumn{1}{|c|}{\small{Reference}}\\
&\multicolumn{1}{|c|}{\small{permutations}}&&&\\ \hline \hline
\multirow{7}*{\includegraphics[height=3cm]{riga1.eps}}&&&&\\
&&&&\\
&\small{$2,8,22,52,$}&\small{$2^{d+1}-2(d+1)$}&\small{\seqnum{A005803}}&\small{Theorems \ref{thm:m1}, \ref{thm:m2} }\\
&\small{$114,240,494, \ldots$}&&&\\
&&&&\\
&&&&\\
&&&&\\
\hline
\multirow{7}*{\includegraphics[height=3cm]{riga2.eps}}&&&&\\
&&&&\\
&\small{$0,2,10,32,$} &\small{$2^{d+1}-d(d+1)-2$}&&\small{Corollaries \ref{cor:first}, \ref{cor:last}}\\
&\small{$84, 198, 438, \ldots$}&&&\\
&&&&\\
&&&&\\
&&&&\\
\hline
\multirow{7}*{\includegraphics[height=3cm]{riga3.eps}}&&&&\\
&&&&\\
&\small{$2,6,14,30,$} &\small{$2^{d}-2$}&\small{\seqnum{A000918}}&\small{Corollary \ref{cor1d}}\\
&\small{$62, 126, 254, \ldots$}&&&\\
&&&&\\
&&&&\\
&&&&\\
\hline
\multirow{7}*{\includegraphics[height=3cm]{riga4.eps}}&&&&\\
&&&&\\
&\small{$0,2,8,22,$}&\small{$2^{d}-2d$}&\small{\seqnum{A005803}}&\small{Corollary \ref{cord1}}\\
&\small{$52,114,240, \ldots$}&&&\\
&&&&\\
&&&&\\
&&&&\\
\hline
\multirow{7}*{\includegraphics[height=3cm]{riga5.eps}}&&&&\\
&&&&\\
&\small{$0,0,2,10,$} &\small{$2^{d}-d(d-1)-2$}&&\small{Corollary \ref{cord21}}\\
&\small{$32,84, 198,\ldots$}&&&\\
&&&&\\
&&&&\\
&&&&\\
\hline
\end{tabular}
}
\end{center}
\caption{Number sequences for some subsets of minimal permutations
with $d$ descents and size $d+2$, $d \geq 2$. OEIS refers to entry
in \cite{OEIS}.} \label{tab:listcount}
\end{table}






\begin{thebibliography}{9}
\bibitem{BV10} J.-L. Baril and R. Vernay, Whole mirror
duplication-random loss model and pattern avoiding permutations,
\textit{Inform. Process. Lett.} \textbf{110} (2010), 474--480.

\bibitem{math.CO} M. Bouvel and  E. Pergola, Posets and permutations in the
duplication-loss model: Minimal permutations with $d$ descents,
\textit{Theoret. Comput. Sci.} \textbf{411} (2010), 2487--2501.

\bibitem{BR09} M. Bouvel and D. Rossin, A variant of the
tandem duplication-random loss model of genome rearrangement,
\textit{Theoret. Comput. Sci.}, \textbf{410} (2009), 847--858.

\bibitem{SODA06} K. Chaudhuri, K. Chen, R. Mihaescu, and S. Rao, On
the tandem duplication-random loss model of genome rearrangement, in
\textit{Proc. 17th Ann. ACM-SIAM Symposium on Discrete Algorithms (SODA)},
ACM, 2006, pp.~564--570.

\bibitem{MY10}
T. Mansour and S. H. F. Yan, Minimal permutations with $d$ descents,
\textit{European J. Combin.} \textbf{31} (2010), 1445--1460.

\bibitem{OEIS} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, \url{http://oeis.org}.



\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: Primary
05A15; Secondary 05A05.

\noindent \emph{Keywords: } minimal permutation, enumeration.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000918} and
\seqnum{A005803}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received April 29 2015;
revised version received August 25 2015.
Published in {\it Journal of Integer Sequences}, September 8 2015.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}