\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsthm,amsmath,amssymb}
\usepackage{graphicx}


\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}

\title{\bf Two permutation classes related to the Bubble Sort operator}

% input author, affilliation, address and support information as follows;
% the address should include the country, and does not have to include
% the street address

\author{Marilena Barnabei, Flavio Bonetti, Matteo Silimbani\\
\small Universit\`a di Bologna\\[-0.8ex]
\small Dipartimento di Matematica\\[-0.8ex]
\small Italy\\
\small\tt \{marilena.barnabei,flavio.bonetti,matteo.silimbani4\}@unibo.it
}

% \date{\dateline{submission date}{acceptance date}\\
% \small Mathematics Subject Classifications: comma separated list of
% MSC codes available from http://www.ams.org/mathscinet/freeTools.html}

\date{\dateline{Feb 7, 2012}{}\\
\small Mathematics Subject Classifications: 05A05, 05A15, 68P10} 
\begin{document}
\maketitle

\begin{abstract} We introduce the Dual Bubble Sort
operator $\hat{B}$ (a sorting algorithm such that, if $\sigma=\alpha\,1\,\beta$ is
a permutation, then
$\hat{B}(\sigma)=1\,\alpha\,\hat{B}(\beta)$) and consider the set of permutations sorted by
the composition $\hat{B}B$, where $B$ is the classical Bubble Sort operator.
We show that this set is a permutation class and we determine the
generating function of the descent and fixed point distributions
over this class. Afterwards, we characterize the same distributions over
the set of permutations that are sorted by both $\hat{B}^2$ and
$B^2$.


\bigskip\noindent \textbf{Keywords:} permutation class, sorting
algorithm, permutation statistic.
\end{abstract}



\section{Introduction}

\noindent A permutation $\sigma$ is said to contain a permutation
$\tau$ if there exists a subsequence of $\sigma$ that has the same
relative order as $\tau$, and in this case $\tau$ is said to be a
\emph{pattern} of  $\sigma$. Otherwise, $\sigma$ is said to
\emph{avoid the pattern} $\tau$.

\noindent A \emph{class} of permutations is a downset in the
permutation pattern order defined above. Every class $C$ can be
defined by its basis $B$, namely, the set of minimal permutations
that are not contained in it, and we write $C=Av(B)$. We denote by
$Av_n(B)$ the set $Av(B)\cap S_n$.

\noindent Permutation classes arise naturally when one studies the
behaviour of some well-known sorting algorithms. More precisely, those
algorithms that have the property that, if they are able to sort a
permutation $\sigma$, then they sort any subpermutation of
$\sigma$.

\noindent The first example was given by D.E.Knuth, who proved in
\cite{k1} that the set of permutations sorted by a single
application of the Stack Sort operator is the class $Av(231)$. The
action of the Stack Sort operator has been extensively studied
after the seminal paper by J.West \cite{w}.

\noindent A further example is the Bubble Sort operator $B$
 that can be recursively described as follows:
$B(\epsilon)=\epsilon$, where $\epsilon$ is the empty permutation,
and, if $\sigma=\alpha\, n\, \beta$ is a non-empty permutation,
and $n$ its maximal value, then
$$B(\sigma)=B(\alpha)\,\beta\,n.$$
The Bubble Sort operator has the nice property (not shared by the
Stack Sort operator, see \cite{w}) that the set of permutations
that are sorted by any power of $B$ form a class, as proved in
\cite{ccdg}. Further properties of the Bubble Sort algorithm have
been recently studied in \cite{aabcd}.

\noindent An apparently new trivial variation $\hat{B}$ of the
operator $B$ can be defined as follows:
$\hat{B}(\epsilon)=\epsilon$ and, if $\sigma=\alpha\,1\,\beta$ is
a non-empty permutation, then
$$\hat{B}(\sigma)=1\,\alpha\,\hat{B}(\beta).$$
We call $\hat{B}$ the \emph{Dual Bubble Sort} operator.

\noindent We observe that the Dual Bubble Sort operator $\hat{B}$
is related to the operator $B$ by
$$\hat{B}=\rho\, B\,\rho,$$
where $\rho$ is the usual reverse-complement operator.

\noindent Note that the composition $C=\hat{B}B$ is another
classical sorting operator introduced by Knuth in \cite{k3},
namely, the \emph{Cocktail Shaker Sort operator}, also known as
the Bidirectional Sort operator.
\newline
\noindent In the first part of this paper we consider the set of permutations
that are sorted by a single run of the Cocktail (Shaker) Sort
operator $C$. We show that this set is the class
$Av(3412,3421,4312,4321)$, and enumerate the elements in
$Av_n(3412,3421,4312,4321)$. Furthermore, we study the
distributions of descents and fixed points over this class. In
particular, we show that fixed point free permutations in the class
are enumerated by Pell numbers.

\noindent The second part of the paper is devoted to the study of
the set of permutations that are sorted by both $B^2$ and
$\hat{B}^2$, namely, permutations in
$B^{-2}(id)\cap\hat{B}^{-2}(id)$. This set turns out to be the
class $Av(S)$, where $S$ is the set of patterns of length $4$ of
type either $4xxx$ or $xxx1$. The set
$B^{-2}(id)\cap\hat{B}^{-2}(id)$ can be also characterized as the
set of permutations $\sigma$ satisfying $|\sigma(i)-i|\leq 2$ for
all $i$. The more general problem of studying the set $T_{d,n}$ of
permutations of length $n$ which satisfy $|\sigma(i)-i|\leq d$
(whose motivation comes from coding theory) was first discussed by
R.Lagrange in \cite{lag}, next by D.H.Lehmer in \cite{leh} and lately by
T.Kl\o ve in \cite{klo}.

\noindent We show that the set $T_{2,n}$ has the peculiar property
that, for $n\geq 5$, it contains only two connected permutations.
A permutation $\sigma \in S_n$ is \emph{connected} if it does not
have a prefix $\sigma'$ of length $k<n$ that is a permutation of
the symbols $1,2,\ldots,k$. This property allows us to determine
the joint distribution of descents and fixed points over
$T_{2,d}$. In fact, the property above smoothes the way to the
study of the distribution of several other permutation statistics
over $T_{2,n}$. As an example, we deduce the generating function
of the joint distribution of descents and occurrences of the
pattern $321$ over $T_{2,n}$.

\section{The Cocktail Sort algorithm}

% omogeneizza la notazione circa il rapporto tra connesse e totali

\noindent The purpose of this section is to study the set of
permutations sorted by a single run of the Cocktail Sort algorithm
$C$. First of all we show that this set is indeed a class, whose
basis is finite:

\begin{theorem}\label{haiscritto}
A permutation $\sigma\in C^{-1}(id)$ if and only if $\sigma$ avoids the patterns
$3412$, $3421$, $4312$, and $4321$.
\end{theorem}

\begin{proof} It is well known (\cite{aabcd}, see also \cite{ccdg}) that the Bubble Sort algorithm is such that
$$B(\sigma)=id \iff \sigma\in Av(321,231)$$
and, hence,
$$\hat{B}(\sigma)=id \iff \sigma\in Av(321,312).$$
This implies that
$$C(\sigma)=id \iff B(\sigma)\in Av(321,312) \iff \sigma\in B^{-1}(Av(321,312)).$$
Proposition $8$ in \cite{aabcd} states that if $\pi\in S_{n-1}$ ($n\geq 4$), $\pi=n-1\, \pi'$, then $$B^{-1}(Av(\pi))=Av(n-1\,n\,\pi', n\, n-1\, \pi').$$
This result implies that $$C(\sigma)=id \iff \sigma\in Av(3412,3421,4312,4321).$$
\end{proof}

\noindent The preceding theorem yields immediately the following
result that will be useful in the rest of this section:

\begin{proposition}\label{moltoimpo}
Let $\sigma\in Av(3412,3421,4312,4321)$. If the maximal symbol $n$ appears in $\sigma$ at position $i\leq n-2$,
then the symbol $n-1$ must be placed either at position $n$ or $n-1$.
\end{proposition}

\noindent Denote by $c_n$ the cardinality of the set $Av_n(3412,3421,4312,4321)$. We determine the generating function of the sequence
 $c_n$ by considering first the connected permutations in $Av_n(3412,3421,4312,4321)$.

\begin{proposition}\label{quibisogna}
Denote by $cc_n$ the number of connected permutations in \newline $Av_n(3412,3421,4312,4321)$. Then, for $n\geq 2$,
$$cc_n=3^{n-2}$$
\end{proposition}

\begin{proof} We observe that $21$ is the only connected
permutation in \newline $Av_2(3412,3421,4312,4321)$. Let now $n$ be an
integer, $n\geq 3$. Every connected permutation $\sigma$
in\newline $Av_{n-1}(3412,3421,4312,4321)$ yields exactly $3$
different connected permutations of length $n$ in the same class
either by:
\begin{itemize}
\item[i)] replacing the symbol $n-1$ by $n$, and inserting $n-1$ at the last position, or
\item[ii)] replacing the symbol $n-1$ by $n$, and inserting $n-1$ at the second last position, or
\item[iii)] inserting the symbol $n$ at the second last position.
\end{itemize}

\noindent On the other hand, it is easily seen that the same operations applied to a non-connected permutation yield
longer non-connected permutations.\\

\noindent Now, by Proposition \ref{moltoimpo}, all connected permutations in $Av_n(3412,3421,4312,4321)$ are obtained in this way.
\end{proof}

\begin{theorem}\label{allab}
The generating function of the sequence $c_n$ is
$$\Gamma(x)=\sum_{n\geq 0} c_n x^n=\frac{1-3x}{1-4x+2x^2}.$$
\end{theorem}

\begin{proof} By Proposition \ref{quibisogna}, the
generating function of the sequence $cc_n$ is the
following:
$$C\Gamma(x)=\sum_{n\geq 1} cc_n x^n=x+\frac{x^2}{1-3x}.$$
Recall that every permutation $\sigma$ can be decomposed into a
non-empty connected prefix $\alpha$ and an arbitrary suffix $\beta$ and that $\sigma$ belongs to the class \newline $Av(3412,3421,4312,4321)$
if and only if both $\alpha$ and $\beta$ avoid the same patterns. This implies that
$$\Gamma(x)=\frac{1}{1-C\Gamma(x)}.$$
\end{proof}

\noindent We observe that the sequence $c_n$ appears (shifted by one term) as seq. $A006012$ in \cite{oeis},
 even though the current interpretation is not present.\\

\noindent We now turn our attention to the study of the descent
distribution on \\ $Av(3412,3421,4312,4321)$. We recall that a
permutation $\sigma$ has a \emph{descent} at position $i$ whenever
$\sigma(i)>\sigma(i+1)$.

\noindent We first study the case of connected permutations, which
can be divided into $3$ types, according to the generation rule
described in the proof of Proposition \ref{quibisogna}. More
precisely, we say that a connected permutation $\alpha$ in
$Av_n(3412,3421,4312,4321)$ is:
\begin{itemize}
\item of type $0$ if $\alpha$ is obtained from a permutation $\sigma\in Av_{n-1}(3412,3421,4312,4321)$
by applying the operation i);
\item of type $1$ if $\alpha$ is obtained from a permutation $\sigma\in Av_{n-1}(3412,3421,4312,4321)$
by applying the operation ii);
\item of type $2$ if $\alpha$ is obtained from a permutation $\sigma\in Av_{n-1}(3412,3421,4312,4321)$
by applying the operation iii).
\end{itemize}

\noindent Let $\sigma\in Av_{n-1}(3412,3421,4312,4321)$ be a permutation with $k$ descents. Denote by $\sigma^{(0)}$,
$\sigma^{(1)}$, and $\sigma^{(2)}$ the $3$ permutations of length $n$ generated by $\sigma$. For example, if $\sigma=3\,1\,5\,2\,4$, then
$$\sigma^{(0)}=3\,1\,6\,2\,4\,5 \quad \sigma^{(1)}=3\,1\,6\,2\,5\,4\quad \sigma^{(2)}=3\,1\,5\,2\,6\,4.$$

\noindent Moreover, we have:

\begin{itemize}
\item if $\sigma$ is of type $0$, then $\sigma^{(0)}$ has $k$ descents, while $\sigma^{(1)}$ and $\sigma^{(2)}$ have $k+1$ descents;
\item if $\sigma$ is of type $1$, then also $\sigma^{(0)}$, $\sigma^{(1)}$, and $\sigma^{(2)}$ have $k$ descents;
\item if $\sigma$ is of type $2$ then $\sigma^{(1)}$ has $k+1$ descents, while $\sigma^{(0)}$ and $\sigma^{(2)}$ have $k$ descents.
\end{itemize}

\noindent Let $cc_{n,k}$ denote the number of non-empty connected
elements in \\ $Av_n(3412,3421,4312,4321)$ with $k$ descents. Then,
we have:

\begin{proposition}\label{ciaperi}
The bivariate generating function of the sequence $cc_{n,k}$ is
$$C\Psi(x,y)=\sum_{\tiny{\begin{array}{l}n\geq 1\\k\geq 0\end{array}}} cc_{n,k} x^n y^k=\frac{x-3x^2+x^2y+3x^3-4x^3y+x^3y^2-x^4+2x^4y-x^4y^2}{1-3x+3x^2-3x^2y-x^3+2x^3y-x^3y^2}.$$
\end{proposition}

\begin{proof} \noindent Denote by $a^{(i)}_{n,k}$,
$i=0,1,2$, the number of connected permutations in\\
$Av_n(3412,3421,4312,4321)$ of type $i$ with $k$ descents, hence,
$cc_{n,k}=a^{(0)}_{n,k}+a^{(1)}_{n,k}+a^{(2)}_{n,k}$. The
following recurrences can be easily deduced from previous
considerations:
$$a^{(0)}_{n,k}=a^{(0)}_{n-1,k}+a^{(1)}_{n-1,k}+a^{(2)}_{n-1,k}=cc_{n-1,k}$$
$$a^{(1)}_{n,k}=a^{(0)}_{n-1,k-1}+a^{(1)}_{n-1,k}+a^{(2)}_{n-1,k-1}$$
$$a^{(2)}_{n,k}=a^{(0)}_{n-1,k-1}+a^{(1)}_{n-1,k}+a^{(2)}_{n-1,k}$$

\noindent These three identities yield the following relations,
for $n\geq 4$:

\begin{equation}cc_{n,k}=2cc_{n-1,k}+cc_{n-1,k-1}-cc_{n-2,k}+cc_{n-2,k-1}+a^{(1)}_{n-1,k}-a^{(1)}_{n-1,k-1},\label{tizia}\end{equation}
\begin{equation}a^{(1)}_{n,k}=cc_{n-1,k-1}-a^{(1)}_{n-1,k-1}+a^{(1)}_{n-1,k}.\label{caia}\end{equation}
Let now
$$C\Psi^{(1)}(x,y)=\sum_{\tiny{\begin{array}{l}n\geq 1\\k\geq 0\end{array}}} a^{(1)}_{n,k} x^n y^k$$
be the generating function of the sequence $a^{(1)}_{n,k}$. Identities (\ref{tizia}) and (\ref{caia}) yield
$$C\Psi(x,y)=x-2x^2+x^3-x^3y$$\begin{equation}+(2x+xy-x^2+x^2y)C\Psi(x,y)+(x-xy)C\Psi^{(1)}(x,y),\label{pedante}
\end{equation}
\begin{equation}C\Psi^{(1)}(x,y)=\frac{(C\Psi(x,y)-x)xy}{1-x+xy},\label{iniziare}\end{equation}
where the correction terms of $x$-degree less than $4$ are due to
the fact that Identities (\ref{tizia}) and (\ref{caia}) hold for
$n\geq 4$. Combining Identities (\ref{pedante}) and
(\ref{iniziare}) we get the assertion.
\end{proof}

\noindent We can exploit the above result to deduce the descent distribution over the set\\ $Av(3412,3421,4312,4321)$,
using the same arguments as in the proof of Proposition \ref{allab}:

\begin{theorem}\label{tatata}
The bivariate generating function of the sequence $c_{n,k}$ is
$$\Psi(x,y)=\sum_{n,k\geq 0} c_{n,k} x^n y^k=\frac{1}{1-C\Psi(x,y)}=$$
$$=\frac{1-3x+3x^2-3x^2y-x^3+2x^3y-x^3y^2}{1-4x+6x^2-4x^2y-4x^3+6x^3y-2x^3y^2+x^4-2x^4y+x^4y^2}.$$
\end{theorem}


\noindent The first values of the integers $c_{n,k}$ are shown in
the following table:

$$\begin{array}{l|lllllllll}
n/k&0&1&2&3&4&5&6\\\hline
1&1&&&&&&\\
2&1&1&&&&&\\
3&1&4&1&&&&\\
4&1&10&9&&&&\\
5&1&20&41&6&&&\\
6&1&35&133&61&2&&\\
7&1&56&350&336&49&&\\
8&1&84&798&1336&465&20&\\
9&1&120&1638&4300&2789&380&4\\
\end{array}\vspace{.5cm}$$

\noindent Now we want to study the distribution of fixed points on
the set $Av(3412,3421,4312,4321)$, namely, the sequence $f_{n,h}$
of the number of permutations in $Av_n(3412,3421,4312,4321)$ with
$h$ fixed points. First of all, we have the following result:

\begin{proposition}\label{chiave}
The number of fixed point-free elements in $Av_n(3412,3421,4312,4321)$, $n\geq 1$,
is the $(n-1)$-th Pell number $P_{n-1}$, namely,
$$f_{n,0}=P_{n-1}.$$
\end{proposition}

\begin{proof} It is well known that the Pell numbers (see seq. A000129 in \cite{oeis})
satisfy the following recurrence:
$$P_0=0,\qquad P_1=1,\quad P_n=2P_{n-1}+P_{n-2}\, (n>1).$$
On the other hand, it is easily checked that
$$f_{1,0}=0,\quad f_{2,0}=1.$$
Let $\sigma$ be a fixed point free permutation in $Av_h(3412,3421,4312,4321)$. Then, we can construct three longer
fixed point free permutations in $Av(3412,3421,4312,4321)$ either by
\begin{itemize}
\item[a.] adding the symbols $h+2$ and $h+1$ at the two last positions in this order, or
\item[b.] inserting the symbol $h+1$ at the second last position, or
\item[c.] replacing the symbol $h$ with $h+1$ and inserting $h$ at the end of the permutation.
\end{itemize}
It is an immediate consequence of Proposition \ref{moltoimpo} that
every fixed point free permutation in $Av_n(3412,3421,4312,4321)$,
$n\geq 1$,
 is obtained exactly once in this way. This yields:
 $$f_{n,0}=2f_{n-1,0}+f_{n-2,0},$$
 as wished.
\end{proof}

\noindent The integers $f_{n,h}$, $h>0$, can be determined making use of the following result:

\begin{proposition}\label{chiave}
Let $\sigma$ be a permutation in $Av(3412,3421,4312,4321)$, and $\sigma'$ be the permutation obtained from $\sigma$
by adding a fixed point $p$ and increasing by one all the symbols $e\geq p$. Then $\sigma'\in Av(3412,3421,4312,4321)$.
\end{proposition}

\begin{proof} Suppose that $\sigma'$ contains the pattern
$cdab$, with $l=\max(a,b)<c,d$. Since $\sigma$ avoids $cdab$, the
fixed point $p$ must appear in this pattern. Suppose that $p=c$
and let $j$ be the position of $a$ in $\sigma'$. In this case, the
$j-3$ positions of $\sigma$ preceding $j$ and not containing $c$
and $d$ can be occupied only by symbols less then $l$. We have
$l-2$ of these symbols different from $a$ and $b$. Since $l<c<j$,
we have $l-2\leq j-4$, hence we get a contradiction.
\end{proof}

\noindent The last result implies that every permutation
$\sigma\in Av_n(3412,3421,4312,4321)$ with $h$ fixed points can be
uniquely obtained from a fixed point free permutation in\\
$Av_{n-h}(3412,3421,4312,4321)$. Hence:

\begin{theorem}\label{chiavenji}
We have:
$$f_{n,h}={n\choose h}P_{n-h-1}.$$
\end{theorem}


\noindent The first values of the integers $f_{n,k}$ are shown in
the following table:

$$\begin{array}{l|llllllllll}
n/k&0&1&2&3&4&5&6&7&8&9\\\hline
2&1&0&1&&&&&&&\\
3&2&3&0&1&&&&&&\\
4&5&8&6&0&1&&&&&\\
5&12&25&20&10&0&1&&&&\\
6&29&72&75&40&15&0&1&&&\\
7&70&203&252&175&70&21&0&1&&\\
8&169&560&812&672&350&112&28&0&1&\\
9&408&1521&2520&2436&1512&630&168&36&0&1\\
\end{array}\vspace{.5cm}$$

\section{Permutations sorted by both $B^2$ and $\hat{B}^2$}

\noindent It has been proved in \cite{ccdg} that a permutation
$\sigma$ is sorted by $k$ iterations of the Bubble Sort operator
whenever $i-\sigma(i)\leq k$ for every $i$. It is straightforward
to verify that a permutation has the property above if and only if
it avoids every pattern of length $k+2$ of type $xxx...x1$.

\noindent Recall that
$$\hat{B}=\rho\, B\,\rho,$$
where $\rho$ is the usual reverse-complement operator. This
implies immediately that a permutation $\sigma$ is sorted by $k$
iterations of $\hat{B}$ whenever $\sigma(i)-i\leq k$ for every
$i$, or equivalently, if and only if $\sigma$ avoids every pattern
of length $k+2$ of type $(k+2)xxx...x$. In particular, we have:

\begin{theorem}\label{appartiene}
A permutation $\sigma$ belongs to $B^{-2}(id)\cap
\hat{B}^{-2}(id)$ if and only if
\begin{itemize}
\item $|\sigma(i)-i|\leq 2$ for every $i$, or equivalently
\item $\sigma$ belongs to $Av(S)$, where $S$
is the set of patterns of length $4$ of type either $4xxx$ or
$xxx1$.
\end{itemize}
\end{theorem}

\noindent From now on, we will denote by $T_2$ the set
$B^{-2}(id)\cap \hat{B}^{-2}(id)$. Obviously, $T_2\cap
S_n=T_{2,n}$. The sequence of the cardinalities of the sets
$T_{2,n}$ appears in \cite{oeis} as seq. A002524.

\noindent The set $T_{2,n}$ has the peculiar property that, for
$n\geq5$, it contains only two connected permutations. More
precisely, we have:

\begin{proposition}\label{single}
The only connected elements in $T_2$ are:
\begin{itemize}
\item[a.] the permutations $1$, $21$, $321$, $231$, $312$ and $3412$;
\item[b.] the permutation $\pi_n\in S_n$, $n\geq 4$, defined as follows:
\begin{itemize}
\item if $n=2s$
$$\left\{\begin{array}{ll}\pi_{2s}(1)=2&\\\pi_{2s}(2s)=2s-1&\\\pi_{2s}(2h)=2h+2&1\leq h\leq s-1\\\pi_{2s}(2h+1)=2h-1&1\leq h\leq s-1\end{array}\right.$$
\item if $n=2s+1$
$$\left\{\begin{array}{ll}\pi_{2s+1}(1)=2&\\\pi_{2s+1}(2s)=2s+1&\\\pi_{2s+1}(2h)=2h+2&1\leq h\leq s-1\\\pi_{2s+1}(2h+1)=2h-1&1\leq h\leq s\end{array}\right.$$
\end{itemize}
\item[c.]the permutation $\tau_n:=\pi_n^{-1}$, $n\geq 4$.
\end{itemize}
\end{proposition}

\begin{proof} It is obvious that the listed permutations
are connected elements in $T_2$ and that, for $n\leq 4$, these are
the only ones. Let now $\sigma$ be a connected permutation in
$T_{2,n}$, $n\geq 5$. It is evident that $\sigma(1)$ is either $2$
or $3$. In the first case, $\sigma(2)\neq 1$, otherwise $\sigma$
is not connected. Furthermore, $\sigma(2)\neq 3$, otherwise
$\sigma(3)$ would be forced to be equal to $1$, contradicting the
connectedness condition. Iterating these arguments, we deduce
that, if $\sigma(1)=2$, then $\sigma=\pi_n$.

\noindent The case $\sigma(1)=3$ can be treated similarly, getting
$\sigma=\tau_n$.
\end{proof}

\noindent For example, we have
$$\pi_6=2\,4\,1\,6\,3\,5$$
$$\tau_6=3\,1\,5\,2\,6\,4,$$
and
$$\pi_7=2\,4\,1\,6\,3\,7\,5$$
$$\tau_7=3\,1\,5\,2\,7\,4\,6.$$

\noindent We examine the generating function
$$A(x,y,z)=\sum_{n}\sum_{\sigma\in
T_{2,n}}x^ny^{des(\sigma)}z^{fix(\sigma)}=\sum_{n,d,r}t_{n,d,r}x^ny^dz^r$$
of the joint distribution of descents and fixed points on the set
$T_2$. Here the integer $t_{n,d,r}$ denotes the number of
permutations in $T_{2,n}$ with $d$ descents and $r$ fixed points.
To this aim, we first study the generating function of the same
distribution on the set $CT_2=\bigcup_{n\geq 0}CT_{2,n}$ of
non-empty connected permutations in $T_2$.


\noindent Denote by $ct_{n,d,r}$ the number of elements in
$CT_{2,n}$ with $d$ descents and $r$ fixed points. As an immediate
consequence of Proposition \ref{single}, we have:


\begin{proposition}\label{then}
The only non-zero coefficients $ct_{n,d,r}$ are the following:
\begin{itemize}
\item[a.] $ct_{1,0,1}=ct_{2,1,0}=ct_{3,2,1}=ct_{4,2,0}=1$;
\item[b.] $ct_{3,1,0}=ct_{4,1,0}=2$;
\item[c.] if $n\geq 5$, $n=2s$, $ct_{2s,s-1,0}=ct_{2s,s,0}=1$;
\item[d.] if $n\geq 5$, $n=2s+1$, $ct_{2s+1,s,0}=2$.
\end{itemize}
\end{proposition}

\noindent Denote by
$$CA(x,y,z)=\sum_{n}\sum_{\sigma\in CT_{2,n}}x^ny^{des(\sigma)}z^{fix(\sigma)}=\sum_{n,d,r}ct_{n,d,r}x^ny^dz^r.$$
Proposition \ref{then} allows us to find an expression for
$CA(x,y,z)$. In fact, we have:

$$CA(x,y,z)=xz+x^2y+2x^3y+x^3y^2z+2x^4y+x^4y^2+\sum_{s\geq 3}(x^{2s}y^{s-1}+x^{2s}y^s) +\sum_{s\geq 2}2 x^{2s+1}y^s=$$
$$xz+x^2y+2x^3y+x^3y^2z+2x^4y+x^4y^2+\frac{x^5y^2(2+x+xy)}{1-x^2y}.$$

\noindent This gives the following result:

\begin{proposition}\label{cana}
$$CA(x,y,z)=\frac{xz+x^2y+2x^3y-x^3yz+x^3y^2z+2x^4y-x^5y^3z-x^6y^2}{1-x^2y}.$$
\end{proposition}


\noindent Every $\sigma\in T_2$ can be represented
 as the juxtaposition of a connected non-empty prefix $\bar{\sigma}$ and a suffix $\sigma'$.
 Needless to say, both $\bar{\sigma}$ and $\sigma'$ (up to renormalization) belong to $T_2$,
  $des(\sigma)=des(\bar{\sigma})+des(\sigma')$, and $fix(\sigma)=fix(\bar{\sigma})+fix(\sigma')$.
  This allows us to determine an expression for the generating function
$A(x,y,z)$:

\begin{theorem}\label{quelche}
We have:
$$A(x,y,z)=\frac{1}{1-CA(x,y,z)}=$$$$=\frac{1-x^2y}{1-xz-2x^2y-2x^3y+x^3yz-x^3y^2z-2x^4y+x^5y^3z+x^6y^2}.$$
\end{theorem}


\noindent As a final observation, we point out that every
connected permutation in $T_2$ except $321$ avoids the pattern
$321$. Hence, the joint distribution of descents and occurrences
of the pattern $321$ can be easily obtained by similar arguments:
$$B(x,y,t)=\sum_n\sum_{\sigma\in T_{2,n}} x^ny^{des(\sigma)}t^{occ_{321}(\sigma)}=$$
$$=\frac{1-x^2y}{1-x-2x^2y-x^3y-x^3y^2t-2x^4y+x^5y^3t+x^6y^2} $$ where $occ_{321}(\sigma)$
denotes the number of occurrences of the pattern $321$ in
$\sigma$.

\section*{Acknowledgments}

\noindent We thank the referee for many precious suggestions.



\begin{thebibliography}{99}

\bibitem{aabcd} M.H.Albert, M.D.Atkinson, M.Bouvel, A.Claesson, M.Dukes. \newblock
On the inverse image of pattern classes under bubble sort. \newblock
\emph{Journal of Combinatorics} 2 (2):231--243, 2011.

\bibitem{ccdg} F.Chung, A.Claesson, M.Dukes, R.Graham. \newblock Descent polynomials for permutations with bounded drop size.
\newblock \emph{European J. Combin.} 31:1853--1867, 2010.

\bibitem{klo} T.Kl\o ve. \newblock Generating functions for the number of permutations with limited displacement. \newblock
\emph{Electron. J. Combin.} 16:$\#$R104 2009.

\bibitem{k1} D.E.Knuth. \newblock {\em The art of computer programming, Vol. 1: ``Fundamental algorithms''.} \newblock
 Addison-Wesley, Reading
MA, 1975.

\bibitem{k3} D.E.Knuth. \newblock \emph{The art of computer programming, Vol. 3: ``Sorting and searching''.}. \newblock
 Addison-Wesley, Reading
MA, 1973.

\bibitem{lag} R.Lagrange. \newblock Quelques r\'esultats dans la m\'etrique des permutations. \newblock
\emph{Annales Scientifiques de l'\'{E}cole Normale Sup\'erieure} 79:199--241, 1962.

\bibitem{leh} D.H.Lehmer. \newblock \emph{Permutations with strongly restricted displacements}. \newblock
Combinatorial theory and its applications, II (Proc. Colloq., Balatonfured, 1969), pp. 755--770.
 North-Holland, Amsterdam, 1970.

\bibitem{oeis} N.J.A.Sloane. \newblock The On-Line Encyclopedia of Integer
Sequences. \newblock http://www.research.att.com/~njas/sequences/.

\bibitem{w} J.West. \newblock Sorting twice through a stack. \newblock \emph{Theoretical Comput. Sci.} 
117:303--313, 1993.

\end{thebibliography}

\end{document}