\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}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}
\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 Square Involutions
}
\vskip 1cm
\large
Filippo Disanto\\
Dipartimento di Scienze Matematiche e Informatiche\\
Universit\`a di Siena\\
Pian dei Mantellini 44\\
53100 Siena, Italy\\
\ \\
Andrea Frosini\\
Dipartimento di Sistemi e Informatica\\
Universit\`a degli Studi di Firenze\\
Viale Morgagni 65 \\
50134 Firenze, Italy \\
\href{mailto:andrea.frosini@unifi.it}{\tt andrea.frosini@unifi.it} \\
\ \\
Simone Rinaldi \\
Dipartimento di Scienze Matematiche e Informatiche\\
Universit\`a di Siena \\
Pian dei Mantellini 44 \\
53100 Siena, Italy \\
\href{mailto: rinaldi@unisi.it}{\tt rinaldi@unisi.it} \\
\end{center}
\vskip .2 in
\begin{abstract}
A {\em square involution} is a square permutation which is also an
involution. In this paper we give the enumeration of square
involutions, using purely combinatorial methods, by establishing a
bijective correspondence with a class of lattice paths. As a corollary
to our result, we enumerate various subclasses of square involutions,
including the classes of {\em triangular}, {\em decomposable}, and {\em
fat involutions}.
\end{abstract}
\section{Square Permutations}
A permutation $\pi \, = \, (\pi(1) \ldots \pi(n)) \,$ of length $n$ can be suitably represented in the discrete plane
by the set $G_{\pi} \, = \{ \, (i,\pi(i)) \, : \, i=1,\ldots ,n \, \}$.
Following a quite common terminology \cite{perm}, a point $(i,j) \in G_{\pi}$ is respectively said to be:
\begin{itemize}
\item a \emph{left-to-right minimum} if, for any $(i',j') \in G_{\pi}$, $i'*j$; \item a \emph{ right-to-left minimum} if, for any $(i',j') \in G_{\pi}$, $i'>i$ implies $j'>j$; \item a \emph{left-to-right maximum} if, for
any $(i',j') \in G_{\pi}$, $i'**i$ implies $j'>j$; \item an \emph{interior point} if it does not belong to any of the previous
classes.
\end{itemize}
Given a permutation $\pi$ we obtain the {\em faces} of its \emph{convex
envelope} by joining the sequences of \emph{left-to-right maxima},
\emph{right-to-left maxima}, \emph{right-to-left minima}, and
\emph{left-to-right minima} of $\pi$. The convex envelope of a
permutation $\pi$ is sometimes called the {\em grid polygon} of $\pi$
(for instance in \cite{MS}). Figure~\ref{square_r}~(a) depicts the
convex envelope of the permutation $( \, 3 \, 8\, 2\, 5 \, 6 \, 1 \, 9
\, 4 \, 7 \, )$.
\begin{figure}[htb]
\begin{center}
\includegraphics[width=90mm]{square_r.eps} \caption{(a) A permutation and its convex envelope; (b) A square permutation and its convex envelope.}\label{square_r}
\end{center}
\end{figure}
A \emph{square permutation} is a permutation which does not contain interior points, see Fig.~\ref{square_r}~(b). In a square permutation $\pi$ each point $(i,\pi(i))$ belongs to at least one of the {\em faces} of the convex envelope.
In a square permutation, a {\em double point} is any point belonging to two faces. Clearly, a double point must lie on the main diagonal or on the antidiagonal. On the other hand, a fixed point of $\pi$ is not necessarily a double point. Figure~\ref{square_r}~(b) shows the square permutation $( \, 3 \, 1 \, 4 \, 2 \, 5 \, 6 \, 9\, 8 \, 7 \, )$, with exactly four faces. The points $5$ and $6$ are double points, while $8$ is a fixed point but not a double point.
From now on, by abuse of notation, we will say {\em face of a permutation} $\pi$ to mean face of the convex envelope of $\pi$.
\smallskip
\noindent Square permutations can be classified according to the number of faces. By convention, a face of size $1$ is not considered when counting the number of faces:
\begin{description}
\item{i.} {\em parallel permutations} (or $2$-face permutations), i.e. square permutations having exactly two faces (observe that a permutation of length greater than one has at least two faces), see Fig.~\ref{faces_r}~(a);
\item{ii.} {\em triangular permutations} (or $3$-face permutations), i.e. square permutations having at most 3 faces, see Fig.~\ref{faces_r}~(b).
\end{description}
\begin{figure}[htb]
\begin{center}
\includegraphics[width=80mm]{faces_r} \caption{(a) A $2$-face permutation; (b) A $3$-face permutation with exactly three faces.}\label{faces_r}
\end{center}
\end{figure}
\noindent T.~Mansour and S.~Severini introduced square permutations in~\cite{MS}, and among other results, proved that:
\begin{description}
\item{-} the number of square permutations of length $n$ is equal to
\begin{equation}\label{sp}
2(n+2)4^{n-3}-4(2n-5){{2(n-3)}\choose {n-3}} \, \qquad \, n\geq 3;
\end{equation}
\item{-} the number of triangular permutations of length $n$ {\em with a single source} (i.e., $\pi(1)=1$) is
\begin{equation}\label{2f}
{{2(n-2)} \choose {n-2}} \, \qquad \, n\geq 2.
\end{equation}
\end{description}
A bijective proof for the number of triangular permutations of length $n$ with a single source was given in \cite{puma}.
Square permutations have successively been studied by several other authors. E.~Duchi and D.~Poulalhon \cite{D}
re-obtained their enumeration by determining a recursive construction of the class using the ECO method.
Despite these studies, no bijective proof is known for the formula~(\ref{sp}).
M.~Albert et al. \cite{A} also considered this class, under the name of {\em convex permutations}, and proved
that they can be characterized as the permutations avoiding the following sixteen patterns of length five:
$$\begin{array}{cccc}
(5 \,2 \, 3 \, 4 \, 1) &(5 \, 2 \, 3 \, 1 \, 4) &(5 \, 1 \, 3 \, 4\, 2) &(5\,1\,3\,2\,4) \\
(4\,2\,3\,5\,1) &(4\,2\,3\,1\,5) &(4\,1\,3\,5\,2) &(4\,1\,3\,2\,5) \\
(2\,5\,3\,4\,1) &(2\,5\,3\,1\,4) &(1\,5\,3\,4\,2) &(1\,5\,3\,2\,4) \\
(2\,4\,3\,5\,1) &(2\,4\,3\,1\,5) &(1\,4\,3\,5\,2) &(1\,4\,3\,2\,5) \\
\end{array}
$$
Square permutations are also intimately related to {\em convex permutominoes} \cite{jis}. We recall that a {\em permutomino} of size $n$ is a polyomino having $n$ rows and $n$ columns, and having exactly one side of the boundary for each abscissa and ordinate between $1$ and $n+1$ (see Fig.~\ref{permutomino_r}). A permutomino $P$ of size $n$ can be equivalently defined in terms of a pair of permutations of length $n+1$, denoted by $\pi_1(P)$, and $\pi_2(P)$ (briefly, $\pi_1$, $\pi_2$), as graphically explained in Fig.~\ref{permutomino_r}. For more details on permutominoes we refer the reader to \cite{incitti,reure}, while to learn more about the relationship between convex permutominoes and square permutations, we suggest \cite{jis}.
\begin{figure}[htb]
\begin{center}
\includegraphics[width=120mm]{permu_r} \caption{(a) A convex permutomino $P$; (b) The permutation $\pi_1(P)=( \, 3 \, 4 \, 7 \, 2 \, 1 \, 5 \, 6 \, )$; (c) The permutation $\pi_2(P)= ( \, 4 \, 7 \, 6 \, 3 \, 2 \, 1 \, 5\, )$.}\label{permutomino_r}
\end{center}
\end{figure}
In this paper we will study {\em square involutions}, i.e. the square permutations which are also involutions.
We will provide the enumeration of some interesting subclasses, such as {\em parallel} involutions, {\em triangular} involutions, {\em decomposable} square involutions, and {\em fat} involutions.
The main result consists in proving that the number of square involutions of length $n$ is
\begin{equation}\label{sqclform}
\left( n+2 \right) {2}^{n-3}- \left( n-2 \right) {{n-3} \choose {\lfloor \frac{n-3}{2} \rfloor} } \, \qquad n\geq 3.
\end{equation}
Most of the results of the paper will be obtained using bijective arguments: our approach consists in representing involutions in terms of lattice paths, and it seems remarkable, since, until now, no bijective proof for the formula (\ref{sp}) for the number of square permutations has been given.
Finally we will establish a simple connection with symmetric convex permutominoes and list some interesting open problems.
\section{Triangular Involutions}
In this section we will consider and enumerate various classes of square involutions having at most three faces.
Following the terminology of \cite{MS}, a square involution is said to be a {\em parallel} involution if it has exactly two faces, and a {\em triangular} involution if it has at most $3$ faces.
Figure~\ref{triangular_r} shows some examples of parallel and triangular involutions.
\begin{figure}[htb]
\begin{center}
\includegraphics[width=110mm]{sampletri_r} \caption{(a) A triangular involution $\pi$ with $\pi(1)=1$; (b) A triangular involution $\pi$ with $\pi(n)=n$; (c) A parallel involution.}\label{triangular_r}
\end{center}
\end{figure}
Let $T(n)$ be the class of triangular involutions of length $n$. One easily checks that
$\pi \in T(n)$ if and only if $\pi $ is a square involution such that $\pi(1)=1$ or $\pi(n)=n$, or both. Similarly,
$\pi$ is a parallel involution of size $n$ if and only if $\pi $ is a square involution such that $\pi(1)=1$ and $\pi(n)=n$.
Then we consider three subclasses of triangular involutions:
\begin{enumerate}
\item $T_1(n)$ is the class of triangular involutions $\pi$ of length $n$ with $\pi(1)=1$;
\item $T_2(n)$ is the class of triangular involutions $\pi$ of length $n$ with $\pi(n)=n$;
\item $T_3(n)$ is the class of parallel involutions of length $n$, that is $T_3(n)=T_1(n) \cap T_2(n)$.
\end{enumerate}
Let us start with the enumeration of such classes.
\begin{proposition}\label{t3}
For $n\geq 2$, the number of parallel involutions of length $n$ is $\left | T_3(n) \right | \, = \, {{n-2}\choose {\lfloor \frac{n-2}{2} \rfloor}}$.
\end{proposition}
\begin{proof} A parallel involution of length $n$ is simply an involution with $\pi(1)=1$, $\pi(n)=n$ and avoiding $321$.
Now, the number of involutions of length $n$ avoiding $321$ is ${{n}\choose {\lfloor \frac{n}{2} \rfloor}}$ \cite{SS}. Then the assertion follows immediately.
\end{proof}
\begin{proposition}\label{t1}
For $n\geq 2$, the number of triangular involutions $\pi$ of length $n$ with $\pi(1)=1$ is $\left | T_1(n) \right | = 2^{n-2}$.
\end{proposition}
\begin{proof} We can prove the statement by establishing a simple bijection between triangular
involutions of length $n$ and words of length $n-2$ in a two letter alphabet $\{0,1\}$.
Given a $\pi\in T_1(n)$, we can consider the points on the left of $n$ lying not below the diagonal $y=x$, i.e. the left to right maxima of $\pi$. Then we construct the path $P(\pi)$ which starts from $O=(1,1)$, ends at $y=n$, and connects all these points from left to right, using only north and east unit steps (see Fig.~\ref{triangularri}). The reader can easily verify that the path $P(\pi)$ completely determines the involution $\pi$, due to obvious symmetry properties and to the fact that $\pi$ is a square permutation. Such a path contains exactly ${n-1}$ north steps, and it always starts with a north step.
Now we may encode $P(\pi)$ by means of a binary word $w(\pi)$ of length $n-2$, by following the sequence of north steps from left to right and from bottom to top, and letting
$$ w(i) = \left \{ \begin{array}{ll} 1 &\mbox{if the $i+1$th north step is preceded by a north step,} \\
0 & \mbox{otherwise.} \end{array} \right. $$
It is easy to prove that the previously defined function is a bijection, hence the cardinality of $T_1(n)$ is~$2^{n-2}$.
\end{proof}
\begin{figure}[htb]
\begin{center}
\centerline{\hbox{\includegraphics[width=40mm]{triangular_r.eps}}} \caption{The triangular square involution $( \, 1 \, 3 \, 2 \, 4 \, 7 \, 9 \, 5 \, 8 \, 6 \, )$ and the corresponding word $1001101$.} \label{triangularri}
\end{center}
\end{figure}
The results stated in Propositions~\ref{t3} and~\ref{t1} allow us to determine the number of triangular involutions of length $n$.
\begin{proposition}\label{tri}
For $\, n\geq 2 \,$, the number of triangular involutions of $n$ is $\, 2^{n-1}-{{n-2}\choose {\lfloor \frac{n-2}{2} \rfloor}} \,$.
\end{proposition}
\begin{proof}
The result directly follows from the equations $|T(n)|=|T_1(n)|+|T_2(n)|-|T_1(n) \cap T_2(n)|$, and $|T_1(n)|=|T_2(n)|$.
\end{proof}
\section{Decomposable Square Involutions}
Let us recall that, given two permutations $\pi_1 \, = \, ( \, \pi_1(1) \, \ldots \, \pi_1(n) \, ) \, $, and
$\pi_2 \, = \, ( \, \pi_2(1) \, \ldots \, \pi_2(m) \, ) \, $, $\, \pi_1 \oplus \pi_2 \, = \, ( \, \pi_1(1) \, \ldots \, \pi_1(n) \, n+\pi_2(1) \, \ldots \, n+\pi_2(m) \, ) \, $ denotes their {\em direct sum} along the main diagonal, and $\pi_1 \ominus \pi_2 \, = \, ( \, m+\pi_1(1) \, \ldots \, m+\pi_1(n) \, \pi_2(1) \, \ldots \, \pi_2(m) \, ) \, $ denotes their direct sum along the anti-diagonal (sometimes called {\em direct difference}).
In this section consider square involutions which are {\em decomposable}, to be precise:
\begin{description}
\item{i.} the {\em decomposable} square involutions, i.e. the square involutions $\pi$ for which there are permutations $\pi_1,\pi_2$ such that $\pi=\pi_1 \oplus \pi_2$ (see Fig.~\ref{rev_r}~(a));
\item{ii.} the {\em reverse decomposable} (briefly, {\em r-decomposable}) square involutions, i.e. the square involutions $\pi$ for which there are permutations $\pi_1,\pi_2$ such that $\pi=\pi_1 \ominus \pi_2$ (see Fig.~\ref{rev_r}~(b)).
\end{description}
\begin{figure}[htb]
\begin{center}
\centerline{\hbox{\includegraphics[width=100mm]{rev_r}}} \caption{(a) A decomposable square involution; (b) An $r$-decomposable square involution.} \label{rev_r}
\end{center}
\end{figure}
Let us start with the class of $r$-decomposable square involutions.
\begin{proposition}\label{rv}
For $n\geq 2$, the number of r-decomposable square involutions of length $n$ is equal to:
\begin{equation}\label{rev}
\left | R(n) \right | \, = \, 2^{n-3}+\left ( \frac{1+(-1)^n}{4} \right ) {{n-2}\choose {\lfloor \frac{n-2}{2} \rfloor}} \, .
\end{equation}
\end{proposition}
\begin{proof} A reverse-decomposable square involution $\pi$ of length $n$ can be uniquely decomposed as $\pi=\sigma \ominus \mu \ominus \sigma^{-1}$, where
$\sigma$ is a (non empty) permutation, $\mu$ is the (possibly empty) indecomposable central block, and $\sigma^{-1}$ is the group inverse of $\sigma$ (see Fig.~\ref{revcent_r}~(a)). Hence $\pi$ is uniquely determined by $\sigma$ and $\mu$, which are square permutations satisfying special properties, and need to be studied separately.
\begin{description}
\item{i.} Let $m\geq 1$ be the length of $\sigma$. If we consider the permutation $\sigma \ominus (1)$, we uniquely obtain a triangular permutation of length $m+1$ with a single source (see Fig.~\ref{revcent_r}~(b)). This correspondence is clearly bijective, hence the permutations $\sigma$ of length $m$ are equinumerous to the triangular permutations of length $m+1$. From equation (\ref{2f}) we derive that their number is
$$ {{2(m-1)} \choose {m-1}}.$$
Now, let $A(x)=\frac{x}{\sqrt{1-4x}}$ be the generating function of these objects.
\begin{figure}[htb]
\begin{center}
\centerline{\hbox{\includegraphics[width=110mm]{revcent_r}}} \caption{(a) An $r$-decomposable square involution; (b) the $3$-face permutation with single source $U$ corresponding to $\sigma$; (c) the central block $\mu$.} \label{revcent_r}
\end{center}
\end{figure}
\item{ii.} The involution $\mu$ can be characterized as an involution avoiding the pattern $123$. In fact, being $\sigma$ non empty, we have that $\mu$ contains the pattern $123$ if and only if $\pi$ contains the pattern $(1)\ominus (1 \, 2 \, 3) \ominus (1)=(5 \, 2\, 3\, 4\, 1)$, which implies that $\pi$ is not a square permutation. The number of involutions of length $h$ avoiding $123$ is given by ${{h-1}\choose {\lfloor \frac{h-1}{2} \rfloor } }$, with $h\geq 1$ \cite{SS}. We only have to point out that the central block may be empty, as in the case of Fig.~\ref{rev_r}~(b), so we include the {\em null} permutation of length~$0$.
Let $B(x)= \frac{1+2x+\sqrt{1-4x^2}}{2\sqrt{1-4x^2}} $ be the generating function of (possibly null) involutions avoiding the pattern $123$.
\end{description}
\noindent Finally, the generating function of $r$-decomposable involutions is given by
$$ R(x)=A(x^2)B(x)=\frac{x^2}{2} \, \left ( \, \frac{1}{1-2x} \, + \, \frac{1}{\sqrt{1-4x^2}} \, \right ) \, , $$
from which the assertion follows.
\end{proof}
Concerning decomposable square involutions, using an analogous decomposition strategy, we are able to derive the following results.
\begin{proposition}
The generating function for decomposable square involutions is
$$ D(x)=\frac{x^2 \, (1-2x+\sqrt{1-4x^2})}{2(1-2x)^2} \, ,$$
hence, for $ n \geq 2 $, the number of decomposable square involutions of length $n$ is equal to:
$$ \left | D(n) \right | = 2^{n-3}+\frac{1}{2}\sum_{k=0}^{\frac{n-1}{2}} {{n-1}\choose {k}} \frac{(n-1-2k)^3}{n-1} \, .$$
\end{proposition}
\section{Fat Involutions}
In this section we will make the final step which will bring us to the enumeration of square involutions. {\em Fat} involutions can be defined as those square involutions which are not $r$-decomposable, neither start with~$1$. Let $F(n)$ denote the set of fat involutions of length $n$. Now square involutions of length $n$, denoted by $I(n)$, are given by the disjoint union of:
\begin{itemize}
\item triangular involutions with $\pi(1)=1$, $T_1(n)$;
\item $r$-decomposable square involutions, $R(n)$;
\item fat involutions, $F(n)$.
\end{itemize}
Enumeration of fat involutions will require all the ingredients we have used in the previous sections.
\begin{proposition}\label{fat}
For $n\geq 2$, the number of fat involutions of length $n$ is
\begin{equation}\label{ft}
\left | F(n) \right | \, = \, \frac{n-1}{2} \left( {2}^{n-2}-{{n-2}\choose \lfloor \frac{n-2}{2} \rfloor } \right).
\end{equation}
\end{proposition}
\begin{proof} Let $\pi$ be a fat involution of length $n$, let $h+1=\pi(1)>1$, and $O=(1,h+1)$.
Similarly to what we have done for triangular involutions, we associate to $\pi$ a closed path $P(\pi)$. Such a path is obtained by joining, starting from $O$, and in a clockwise way: the left-to-right maxima of $\pi$ by means of north and east unit steps, then the right-to-left maxima of $\pi$ by means of south and east unit steps, the right-to-left minima of $\pi$ by means of south and west unit steps, and finally, the left-to-right minima of $\pi$ by means of north and west unit steps (see Fig.~\ref{fat_r}~(a)).
The path we obtain is the contour of a {\em convex permutominide} \cite{sim}. Without going further into formal definitions, a convex permutominide of size $n$ is substantially a polyomino the boundary of which is allowed to touch itself, while the rows and the columns remain connected, and with exactly one edge for every abscissa and exactly one edge for every ordinate between $1$ and $n$.
We observe that the path $P(\pi)$ can touch itself, but it needs happen in a double point of $\pi$ lying in the main diagonal. Since the path $P(\pi)$ is symmetric w.r.t. the main diagonal, the fat involution $\pi$ is uniquely determined by the {\em positive} half of $P(\pi)$, i.e. that lying weakly above the main diagonal.
\begin{figure}[htb]
\begin{center}
\centerline{\hbox{\includegraphics[width=130mm]{fat_r.eps}}} \caption{(a) A fat involution an the corresponding permutominide; (b) the upper and the lower path of the fat involution.} \label{fat_r}
\end{center}
\end{figure}
More precisely, let us consider two subpaths of the positive half of $P(\pi)$, called the {\em lower} path of $\pi$, denoted by $l(\pi)$, running counterclockwise from $O$ to the main diagonal, and the {\em upper} path of $\pi$, denoted by $u(\pi)$, running clockwise from $O$ to $y=n$ (see Fig.~\ref{fat_r}~(b)); by hypothesis, the two paths cannot be empty.
\smallskip
\noindent {\em Claim 1.} The pair $(l(\pi),u(\pi))$ encodes the path $P(\pi)$, hence the fat involution $\pi$.
\smallskip
\noindent {\em Proof.} Let $O'=(h+1,1)$ be the reflection of $O$ w.r.t. the main diagonal. The subpath running clockwise from $O'$ to the main diagonal, and the subpath running counterclockwise from $O'$ to $x=n$ are determined due to symmetry by $l(\pi)$, and $u(\pi)$, respectively. Now, there is only one possible subpath from $(\pi(n),n)$ to $(n,\pi(n))$ such that the obtained closed path is the boundary of a convex permutominide.
\medskip
We study the properties of the lower and the upper paths separately, and then we exhibit characterizations of both the paths.
\noindent{\bf The lower path.} Let $L(n,h)$ be the set of the paths from $O=(1,h+1)$, $h>0$, to the main diagonal, using east or south unit steps, starting with an east step, and not crossing the antidiagonal $x+y=n+1$.
\smallskip
\noindent {\em Claim 2.} A path $l$ is the lower path of a fat involution of length $n$ if and only if $l \in L(n,h)$ for some $h\geq 1$.
\smallskip
\noindent {\em Proof.} We only have to prove that the lower path of a fat permutation $\pi$ cannot cross the antidiagonal. Let us proceed by contradiction, assuming that $l=l(\pi)$ crosses the antidiagonal, and let $u(\pi)$ be the upper path of $\pi$. Moreover, let $S=(j,n-j+1)$ be the first point where the lower path crosses the antidiagonal, and $T=(t,n)$ the point where the upper path meets the line $y=n$ (see Fig.~\ref{cross_r}~(a)). Let us consider the convex permutominide $P(\pi)$ determined by $l(\pi)$ and $u(\pi)$. By definition, $P(\pi)$ must have a vertical bond for each abscissa between $1$ and $j$, and an horizontal bond for each ordinate between $n-j+1$ and $n$, furthermore $P(\pi)$ is convex. Then the boundary of $P(\pi)$ must touch itself in $S$, and the two subpaths of the boundary of $P(\pi)$ running from $T$ to $S$ must entirely be contained in the rectangle having $(1,n)$ and $S$ as opposite vertices (see Fig.~\ref{cross_r}~(b)). Hence the points of $\pi$ placed inside such a rectangle form a permutation of length $n-j+1$, and $\pi$ is $r$-decomposable.
\smallskip
\begin{figure}[htb]
\begin{center}
\centerline{\hbox{\includegraphics[width=130mm]{cross_r.eps}}} \caption{(a) A pair $(l(\pi),u(\pi))$, where the lower path crosses the antidiagonal; (b) the boundary of $P(\pi)$ touches itself in $S$, then $\pi$ is $r$-decomposable.} \label{cross_r}
\end{center}
\end{figure}
\smallskip
\noindent {\em Claim 3.} For $n>2$, $0 \frac{n-1}{2}$, we must count only the paths starting from $O$ and not crossing the antidiagonal. We partition these paths according to the ending point, namely $(i,i)$:
\begin{enumerate}
\item if $i\leq n-h$, the path cannot cross the antidiagonal. So the number of paths of $L(n,h)$ ending at $(i,i)$ is equal to $${{h-1}\choose{i-2}}$$ (see Fig.~\ref{lnh}~(a));
\item if $i> n-h$, then we must remove, from all the paths ending at $(i,i)$, those crossing the antidiagonal (see Fig.~\ref{lnh}~(b)). Using a pretty standard technique~\cite{Stanley}, we can establish a bijective correspondence between the paths ending at $(i,i)$ and crossing the antidiagonal, and the paths ending at $(n-i+2,n-i+2)$ (see Fig.~\ref{lnh}~(c)). Then, the number of paths in $L(n,h)$ ending at $(i,i)$ is equal to $${{h-1}\choose{i-2}}-{{h-1}\choose{n-1}}.$$
Finally, summing all the terms with $2 \leq i \leq \lfloor \frac{n+1}{2} \rfloor$, we obtain that the number of paths in $L(n,h)$ is given by
$\sum_{k=0}^{n-h-2} {{h-1} \choose {h-\lfloor \frac{n-1}{2} \rfloor }+k}$.
\end{enumerate}
We easily observe that both cases 1. and 2. are expressed by formula (\ref{ln}).
\end{enumerate}
\begin{figure}[htb]
\begin{center}
\centerline{\hbox{\includegraphics[width=150mm]{lnh.eps}}} \caption{(a) A path in $L(9,6)$ ending at $(4,4)$; (b) A path from $O=(1,8)$ to $(4,4)$ crossing the anti-diagonal, (c) The associated path, ending at $(7,7)$.} \label{lnh}
\end{center}
\end{figure}
\noindent{\bf The upper path.} Once the lower path $l$ is fixed, concerning the upper path we can use the same encoding as we used
for triangular involutions (Proposition~\ref{t3}), in terms of binary words, as graphically explained in Fig.~\ref{fat_r}~(b).
More precisely, an upper path $u$ from $O=(1,h+1)$ to $y=n$ can be encoded by a binary word $w(l,u)$ of length $n-h-2$. The following property is then straightforward.
\smallskip
\noindent {\em Claim 4.} Let $n>2$, $h>0$, and let $l$ be fixed. The number of words $w(l,u)$ encoding an upper path $u$ related to $l\in L(h,n)$ is given by $2^{n-h-2}$.
\smallskip
We remark again that the word encoding for the upper path is bijective only if we have previously fixed the lower path. The reader can easily build an example where, choosing two different lower paths $l$ and $l'$, a word $w$ encodes two different upper paths.
\medskip
Summarizing, the pair $(l, w)$ determines a fat involution $\pi$ of length $|l| + |w| +1$. Now, for any fixed $n>2$, if $h$ denotes the length of the lower path, $0*