\documentclass{article}
%\documentstyle{article}
\usepackage[dvips]{epsfig}
\usepackage{epsf}
\textheight 230mm
\textwidth 164mm
\hoffset -26mm
\voffset -13mm
\font\Ch=msbm10
\def\cqfd{\par\nopagebreak\rightline{\vrule height 3pt width 5pt depth 2pt}
\medbreak}
\newcommand{\gf}{generating function}
\newcommand{\gfs}{generating functions}
\newcommand{\GN}{\mbox{\rm I$\!$N}}
\newcommand{\GL}{\mbox{\rm I$\!$L}}
\newcommand{\N}{\mbox{\Ch N}}
\newcommand{\K}{\mbox{\rm I$\!$K}}
\newcommand{\C}{\mbox{\rm $~\vrule height6.5pt width0.5pt depth0.3pt\!\!$C}}
\newcommand{\R}{\mbox{\rm I$\!$R}}
\newcommand{\Z}{{\rm Z\hskip-0.32em Z}}
\newcommand{\tssps}{two-stack-sortable permutations}
\newcommand{\tssp}{two-stack-sortable permutation}
\newcommand{\beq}{\begin{equation}}
\newcommand{\eeq}{\end{equation}}
\newtheorem{theo}{\bf Theorem}[section]
\newtheorem{propo}[theo]{\bf Proposition}
\newtheorem{lemma}[theo]{\bf Lemma}
\newtheorem{defi}[theo]{\bf Definition}
\newtheorem{coro}[theo]{\bf Corollary}
\newtheorem{conj}[theo]{\bf Conjecture}
\begin{document}
\pagestyle{myheadings} 
\markright{\sc the electronic journal of combinatorics 5 (1998), \#R21\hfill} 
\thispagestyle{empty} 
\title{\bf Multi-statistic enumeration\\
of two-stack sortable permutations}
\author{{\sc Mireille Bousquet-M{\'e}lou}\\
{\small LaBRI, Universit\'e Bordeaux 1}\\
{\small 351 cours de la Lib\'eration }\\
{\small 33405 Talence Cedex,  FRANCE}\\
{\small bousquet@labri.u-bordeaux.fr }\\
{\small Submitted: October 1, 1997.  Accepted: April 1, 1998}}
\date{}
\maketitle



\begin{abstract}
Using Zeilberger's factorization of \tssps , we write a functional
equation --- of a strange sort ---  
that defines their \gf \  according to
five statistics: length, number of descents, number of right-to-left
and left-to-right maxima, and a fifth statistic that is closely
linked to the factorization. Then, we show how one can translate this
functional equation into a polynomial one. We thus prove that our
five-variable \gf \ for \tssps \ is algebraic of degree 20.
\end{abstract}

\section{Introduction}\label{intro}
The aim of this paper is twofold. Our first intention is to draw
attention on the factorization of \tssps \ described by Zeilberger in
\cite{zeil}. Among other advantages, this factorization preserves many standard
statistics defined on 
permutations, and  hence, constitutes an efficient first step for their
enumeration. We thus obtain
a functional equation --- of a strange kind --- that defines a five-variable
 \gf \ for these permutations (see Eq. (\ref{principale})).

Our second point is to show how one can ``solve'' such an equation,
or, more precisely, convert it into a {\em polynomial\/} one: in
particular, we prove that the \gf \ for \tssps , counted 
according to the length, number of descents, number of right-to-left and
left-to-right maxima, is algebraic of degree $10$. In passing, we
translate some of our results in terms of 
non-separable maps, since two (sophisticated) bijections have been
described between these maps and \tssps \ \cite{dgw,dgg,gw}. We believe
that our method can be applied to, or at least inspire, the solution of
other functional equations having similar features.

Let us mention that our first point (celebrating Zeilberger's
factorization) is extended in a forthcoming paper
\cite{bousquet-sortable}, where we study several enumeration problems (and
their $q$-analogues) related to the sorting procedure decribed below.

\subsection{The sorting procedure}
Let $\sigma = \sigma_1 \sigma_2 \ldots \sigma_n$ be a word on the
alphabet $\GN ^* = \{1,2, \ldots \}$, having all its letters
distinct. If $n=0$, let $T(\sigma)$ be the empty word. Otherwise, let
$T(\sigma)$ be   obtained by permuting the 
letters of $\sigma$ as follows: if $m= \max (\sigma_1, \ldots , \sigma
_n)$ and $\sigma = \sigma^{(\ell)} m \sigma^{(r)}$, then
$$T(\sigma) = T(\sigma^{(\ell)})T(\sigma^{(r)})m.$$
For instance, sorting the permutation  $\sigma = 2351674$ gives 
 $T(\sigma)=2315647$.

Where does this definition come from?
Imagine $\sigma$ stands on the right of an empty stack, as in Figure
\ref{stack}(a), and we try to {\em sort\/} its letters through the
stack, that is, obtain them on the left of the stack in increasing
order; in addition, letters must always move from right to left
and cannot overtake each other. Clearly, the only algorithm that
leaves a hope to obtain the letters of $\sigma$ in the output in
increasing order is the following: add letters from $\sigma$ on the
top of the stack as long as the letters in the stack decrease
from bottom to top, and otherwise, remove the top letter from the
stack.  Figure \ref{stack}  shows four stages of this
procedure. Applying this algorithm gives $T(\sigma)$ as the output.

\begin{figure}[hbt]
\begin{center}
\input{stack.pstex_t}
\end{center}
\caption{The sorting algorithm.}
\label{stack}
\end{figure}

\subsection{Enumeration}
This sorting procedure was apparently first described by Knuth
\cite[p. 238]{knuth}, who proved that the number of {\em one-stack
sortable permutations\/} of length $n$, i.e. of permutations $\sigma$
such that $T(\sigma)= 1 2 \ldots n$, is the Catalan number $C_n={2n
\choose n}/(n+1)$. This procedure was later thoroughly studied by West
in his Ph.D. thesis \cite{west}. In particular, he conjectured
\cite{west-sfca} that
the number of  {\em two-stack
sortable permutations\/} of length $n$, i.e. of permutations $\sigma$
such that $T^2(\sigma)= 1 2 \ldots n$, is
$2(3n)!/((2n+1)!(n+1)!)$. This conjecture was first proved by
Zeilberger: in \cite{zeil}, he describes a clever factorization of
these permutations that gives a functional equation for their \gf ;
then, he solves this equation via a very complicated method that we
will simplify below.
 In addition, there exist two bijective proofs of this result \cite{dgg,gw}, based on
the fact that $2(3n)!/((2n+1)!(n+1)!)$ is also the number of
non-separable planar maps \cite{brown-maps,tutte-census}. Nothing is
known about  $k$-stack sortable permutations when $k >2$.

In this paper, we shall enumerate \tssps \ $\sigma$ according to the following
classic statistics:\\
$\bullet$ the length $n$ (meaning that $\sigma$ belongs to the
symmetric group $S_n$), \\
$\bullet$ the number of descents, i.e. the number of $i \in \{1,
\ldots , n\}$ such that $\sigma(i)>\sigma(i+1)$ (with $\sigma(n+1)=0$),\\
$\bullet$ the number of right-to-left maxima, i.e. the number of $i \in \{1,
\ldots , n\}$
such that $\sigma(i) >\sigma(j) $ for all $j >i$, \\
$\bullet$ the number of left-to-right maxima,  i.e. the number of $i\in \{1,
\ldots , n\}$
such that $\sigma(i) >\sigma(j) $ for all $j
<i$. \\
Moreover, using Zeilberger's factorization
requires to introduce another statistic  $\ell(\sigma)$, defined by
$$\ell(\sigma) = \max \{ \ell : \sigma^{-1}(n) <  \sigma^{-1}(n-1)<
\cdots <  \sigma^{-1}(n-\ell+1) \}.$$
These five statistics will respectively be counted by the
indeterminates  $x, z,
u, v$ and $t$. By convention, the ``empty'' permutation is given the
weight $v$. 
We shall not prove the following proposition, as it
is a direct consequence of Zeilberger's factorization \cite{zeil}.
%
%
\begin{propo} \label{Seq} Let $\phi(x,z,u,v,t)$ be the generating function for
two-stack sortable permutations.
This series  is completely defined by the following
equation:
$$\phi(x,z,u,v,t)=\frac{v}{1-xzut} \hskip 13cm $$
\beq \hskip 5mm + xut \left[ v(1-v)+\frac{
(v+tu-tuv)\phi(x,z,1,v,1)-\phi(x,z,1,v,tu)}{1-tu}
\right]
\left[\frac{\phi(x,z,u,1,1)-t\phi(x,z,u,1,t)}{1-t}
\right]. \label{principale} \eeq 
%In what follows, the series $\phi(x,z,u,v,t)$ will be often denoted
%$\phi(u,v,t)$. 
\end{propo}
%
%

\bigskip
This equation will be the central object of this paper, and deserves a
few comments. 
First of all, it perfectly defines $\phi(x,z,u,v,t)$: indeed, the coefficient
of $x^n$ in this series is a polynomial in $z,u,v$ and $t$, which can be
computed from (\ref{principale}) by induction on $n$. We have:
$$\phi(x,z,u,v,t)= v+ xzuvt+ x^2 zuvt(v+zut) +
x^3zuvt(vzu+vzut+vz+ztu+z^2t^2u^2+v^2) + O(x^4).$$
 However, this equation is not completely satisfactory, as it is not a
very standard way of specifying a generating function. 
Most combinatorialists probably think they have a better knowledge of a series
when they know it satisfies a differential or
algebraic equation.
 In this particular case, it is known \cite{zeil} that the
length \gf \ for 
two-stack-sortable permutations, in other words $\phi(x,1,1,1,1)$, is
cubic over $\R (x)$. Can we derive
this information from (\ref{principale})?
Other partial results, like the expansions of 
$\phi(x,z,1,1,1)$ and $\phi(x,1,u,1,1)$ 
\cite{dgg}, or the algebraic
equation (of degree 6) satisfied by $\phi(x,1,1,1,t)$ \cite{zeil},
suggest that the {\em complete\/} \gf \
$\phi(x,z,u,v,t)$ could be algebraic over $\R (x,z,u,v,t)$, but
Eq. (\ref{principale}) does not permit to prove this immediately.

 The main difficulty with this equation is that we cannot substitute
$1$ for $t$ (or only after multiplying the whole equation by $(1-t)$,
but then we end up with a tautology). 
 This kind of ``frustrating'' equation occurs in many
enumeration problems, because divided differences (or discrete
derivatives) like  
$$Df(x,t) =\frac{f(x,1)-f(x,t)}{1-t}$$
have a simple combinatorial meaning: if $f(x,t) = \sum a_{nm} x^n
t^m$, then the series $Df(x,t) = \sum a_{nm} x^n (1+ t + \cdots + t^{m-1})$
somehow corresponds to ``choosing one among the $m$ cells'', an
operation that occurs frequently in combinatorial
constructions. Examples can be found in the enumeration of maps
 \cite[section 2.9.1]{brown-maps,brown-tutte,cori,gao,gj}, of
polygons \cite{bousquet-temperley,feretic-svrtan}, and 
permutations \cite{bousquet-sortable,guibert-these}.
 Being able to solve these equations systematically would be very helpful.


In this paper, with the help of Maple, 
we  shall elucidate completely the algebraic status of
the series $\phi(x,z,u,v,t)$ and its main significant specializations, proving
the following theorem.
%
%
\begin{theo} The \gf \ $\phi(x,z,u,v,t)$ for \tssps , and all its
specializations obtained by setting one or several of the variables
$z,u,v$ and $t$ to $1$, are algebraic on the field 
$\K=\R(x,z,u,v,t)$ of rational functions in the variables $x,z,u,v$ and
$t$. \\
Figure {\em \ref{figure}} shows the inclusion
properties and the degrees of the relevant extensions of $\K$, in the
case $z \not = 1$.
When $z=1$, the pattern is the same as in Figure {\em \ref{figure}},  
except that 
$\phi(x,1,1,1,1)$  is only cubic over $\K$.
\end{theo}
%
%

\begin{figure}[hbt]
\begin{center}
\input{zqq.pstex_t}
\end{center}
\caption{Algebraicity of $\phi(x,z,u,v,t)$ and its specializations.}
\label{figure}
\end{figure}

To prove this theorem, we shall  derive from the functional equation
(\ref{principale}) 
an  algebraic equation satisfied by $\phi(x,z,u,v,t)$.
Our method is partly based on, and largely inspired by, the so-called
{\em quadratic method\/}  invented by   Brown to count quadrangular
dissections of the disc \cite{brown,brown-dissections} (see
also \cite[section 2.9.1]{gj}). Before handling the whole equation, we
shall show how this method works by handling the simplest (and original)
case $z=u=v=1$. The complete solution requiring several steps, we
shall then proceed with the case $u=v=1$, then 
$u=1$, then $v=1$, and end up with the complete \gf \  $\phi(x,z,u,v,t)$.

\bigskip \noindent {\bf Notations.} Given a field $\GL$ and $n$
indeterminates $x_1, \ldots , x_n$, we denote by:

$ \bullet \GL [x_1, \ldots , x_n] $ the ring of polynomials in $x _1 ,
\ldots ,x_n$ with coefficients in $\GL$,

$\bullet \GL (x_1, \ldots , x_n) $ the field of rational functions in $x _1 ,
\ldots ,x_n$ with coefficients in $\GL$,

$\bullet \GL [[x_1, \ldots , x_n]] $ the ring of formal power series in $x _1 ,
\ldots ,x_n$ with coefficients in $\GL$.\\
Throughout the paper, we denote by $\K$ the field $\R(x,z,u,v,t)$. The
series $\phi(x,z,u,v,t)$ will often be denoted $\phi(u,v,t)$.

\bigskip

\noindent We shall often make use of the following simple remark. \\
{\bf Remark.} Let $\GL$ be a field, and let $f(x,t)$ be a
formal power series of $\GL [t][[x]]$, i.e. a series in $x$ with
polynomial coefficients in $t$. If $f(x,t)$ is algebraic of degree $k$
over $\GL(x,t)$, then $f(x,1)$ is algebraic of degree {\em at most\/}
$k$ over $\GL(x)$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The quadratic method and Zeilberger's result ($z=u=v=1$)}
 The two-variable \gf \ $\phi(x,1,1,1,t)=Z(x,t)$ satisfies
\beq Z(x,t)=\frac{1}{1-xt} +xt \left[ \frac{Z(x,1)-Z(x,t)}{1-t}\right]
\left[ \frac{Z(x,1)-tZ(x,t)}{1-t}\right] . \label{eq-simple} \eeq
This is exactly the equation established by Zeilberger in \cite{zeil}. Let us rewrite
it  by constructing a  square
involving all powers of $Z(x,t)$:
\beq (1-xt)\left[ 1-t + xt \ \frac{(1+t)Z(x,1)-2tZ(x,t)}{1-t} \right] ^2
= E(t),\label{eq-lourde} \eeq
where $E(t)$ is the following polynomial in $t$ with coefficients in
$\R[x,Z(x,1)]$:
$$ E(t)=1- \left[2+x-2xZ(x,1)\right]t +
\left[xZ(x,1)-2x+1\right]\left[1+xZ(x,1)\right]t^2-   x\left[
1+xZ(x,1)\right]^2t^3. $$
Let us consider the term 
$$\frac{(1+t)Z(x,1)-2tZ(x,t)}{1-t}.$$
It is a formal power series in $x$ with coefficients in $\R
[t]$. There exists in $\R [[x]]$ a (unique) formal power series $T=T(x) = 1+x +4x^2 +
O(x^3)$
satisfying
\beq  T=1 + xT\  \frac{(1+T)Z(x,1)-2TZ(x,T)}{1-T}.\label{eq-T} \eeq
(The coefficient of $x^n$ in $T(x)$ can de determined by induction on
$n$ using this equation.)
Eq. (\ref{eq-lourde}) shows that the polynomial $E(t)$ has  a double
zero at $t=T(x)$. Hence, the resultant of
  $E(t)$ and  ${\partial E}/{\partial t}(t)$, taken
as polynomials in $t$, is zero. This gives:
$$16x^2\left[ x^2Z(x,1)^3+(2x+3x^2)Z(x,1)^2+(1-14x+
3x^2)Z(x,1)+11x+x^2-1\right] \left[1+xZ(x,1)\right]^4=0,$$
from which we obtain the {\em cubic\/} equation satisfied by $Z(x,1)$. 
We have thus proved Zeilberger's result:
%
%
%
\begin{propo} \label{x} 
The length \gf \ $Z(x,1)=\phi(x,1,1,1,1)$ for two-stack-sortable
permutations is cubic on $\R (x)$:
$$ x^2Z(x,1)^3+x(2+3x)Z(x,1)^2+(1-14x+
3x^2)Z(x,1)+x^2+11x-1=0.$$
The Lagrange inversion formula gives
\beq Z(x,1)=1+\sum_{n\ge 1}
\frac{2(3n)!}{(2n+1)!(n+1)!}x^n. \label{Z1111-expr} \eeq
The \gf \ $Z(x,t)=\phi(x,1,1,1,t)$ for two-stack-sortable
permutations, counted according
to their length and DZ's statistic, is algebraic of degree $6$ over
$\R (x,t)$, and the field $\R (x,t, Z(x,t))$ contains $Z(x,1)$.
\end{propo}
%
%
%
{\bf Proof.} To obtain the expansion of $Z(x,1)$, we introduce the
series $Y=Y(x)$ defined by
$$Y=x(1+Y)^3,$$
and then check that $1+Y-Y^2$ satisfies the same equation as $Z(x,1)$.
This implies
that $Z(x,1)=1+Y-Y^2.$
We then obtain (\ref{Z1111-expr})  thanks to the Lagrange inversion formula. 


Now, Eq. (\ref{eq-simple}) shows that $Z=Z(x,t)$ is at most quadratic over $\R(x,t,Z(x,1))$, and hence
algebraic of degree at most 6  over $\R (x,t)$.
The (minimal) algebraic equation it satisfies can  be obtained by
eliminating $Z(x,1)$ in
(\ref{eq-simple}):
$$(xt-1)^3x^5t^6 Z^6
+(3xt^2+3xt-t^2+8t-3)(xt-1)^3x^4t^4 Z^5
+(3x^3t^5+9x^3t^4$$
$$+3x^3t^3-20x^2t^5+15x^2t^4-17x^2t^3-9
x^2t^2+13xt^4+11xt^3-11xt^2+9xt+4t^3-23t^2+16t-3)(xt-1)^2x^3t^2
Z^4$$
$$+
(x^4t^7+9x^4t^6+9x^4t^5+x^4t^4+8x^3t^7-43x^3t^6-27x^3t^5-4x^3t^4-4x^3t^3+16x^2t^7-128x^2t^6+161x^2t^5-51x^2t^4-6x^2t^3$$
$$+6x^2t^2-16xt^6+95xt^5-53xt^4+25xt^3+9xt^2-4xt+2t^5-t^4-20t^3+22t^2-8t+1)(xt-1)^2x^2Z^3$$
$$+(xt-1)(3x^6t^7+9x^6t^6+3x^6t^5+29x^5t^7-84x^5t^6+23x^5t^5-12x^5t^4+88x^4t^7+57x^4t^6+145x^4t^5-22x^4t^4+15x^4t^3$$
$$+80x^3t^7-487x^3t^6+153x^3t
^5-238x^3t^4-31x^3t^3-3x^3t^2-140x^2t^6+584x^2t^5-383x^2t^4+244x^2t^3+6x^2t^2-6x^2t$$
$$+68xt^5-211xt^4+172xt^3-84xt^2+18xt+3x-5t^4+14t^3-10t^2+2t)xZ^2
+(xt-1)(3x^7t^6+3x^7t^5+16x^6t^6+19x^6t^5$$
$$-9x^6t^4-8x^5t^6-490x^5t^5+113x^5t^4+3x^5t^3-64x^4t^6+270x^4t^5+741x^4t^4-244x^4t^3+9x^4t^2+128x^3t^6
-197x^3t^5$$
$$-127x^3t^4-395x^3t^3+180x^3t^2-3x^3t-148x^2t^5+285x^2t^4-107x^2t^3+87x^2t^2-60x^2t-3x^2+33xt^4-73xt^3+42xt^2$$
$$-4xt-t^4+2t^3-t^2)Z
+x^8t^6+22x^7t^6-3x^7t^5+116x^6t^6-60x^6t^5+132x^5t^6-659x^5t^5+208x^5t^4+5x^5t^3-160x^4t^6$$
$$+74x^4t^5+824x^4t^4-336x^4t^3+64x^3t^6+114x^3t^5
-292x^3t^4-277x^3t^3+206x^3t^2-3x^3t-88x^2t^5+91x^2t^4+74x^2t^3$$
\beq -17x^2t^2-34x^2t-x^2+28xt^4-59xt^3+32xt^2-2xt-t^4+2 t^3-t^2
=0. \label{grosxt} \eeq
This polynomial is irreducible, and thus $Z(x,t)$ has degree
 exactly $6$ over $\R (x,t)$. The fields $\R(x,t,Z(x,t))$ and
$\R(x,t,Z(x,1),Z(x,t))$ 
 have both degree $6$ over $\R(x,t)$ and hence, are
equal. In particular, $\R(x,t,Z(x,t))$ contains  $Z(x,1)$.
\cqfd
\bigskip 

\noindent {\bf Remarks} 

1. The algebraic equation satisfied by $Z(x,1)$ has been obtained
without having to  guess anything. But the idea of introducing
the series $Y$ satisfying $Y =x(1+Y)^3$ seems only natural if one
suspects the expansion (\ref{Z1111-expr}). However, we can
alternatively obtain this expansion, without guessing it, via the
following procedure. We convert the algebraic equation satisfied by $Z(x,1)$ into a linear
differential equation (using for instance the Maple package Gfun
\cite{gfun}):
$$x^2(27x-4) \frac{\partial ^2 Z}{\partial x^2}(x,1)
+2x(27x-5)\frac{\partial  Z}{\partial x}(x,1)
+2(3x-1)Z(x,1) + 2(3x-1) =0.
$$
Denoting by $a_n$ the coefficient of $x^n$ in $Z(x,1)$, this
differential equation gives:
\beq a_0=1, \ \ a_1=1, \ \ 
\hbox{and for } n\ge 2, \ \ 
a_n= \frac{3(3n-1)(3n-2)}{2(n+1)(2n+1)} a_{n-1}.\label{recurrence} \eeq
We then obtain our result\footnote{As noticed by Gilles Schaeffer,
another hint about the right parametrization (by $Y$) is given by the
equation satisfied by the series $T$ defined by (\ref{eq-T}). We
obtain: $T(1-2xT)^2=(1-xT)^3$, which suggests (?) $Y=xT/(1-2xT)$.}
 by induction on $n$. If the recurrence
relation (\ref{recurrence}) 
had not been of order $1$, we could still have
looked for its hypergeometric solutions via Petkov{\u s}ek's algorithm \cite{ab}.


2. The  expression of
$Z(x,1)$ was first conjectured by West \cite{west}, then proved by 
Zeilberger \cite{zeil},
Dulucq, Gire and Guibert \cite{dgg}, and finally Goulden and West
\cite{gw}. Zeilberger solves (\ref{eq-simple}) by first {\em
guessing\/} Eq. (\ref{grosxt}), and then checking that (\ref{grosxt})
and (\ref{eq-simple}) have a common solution. This procedure was later
simplified by Gessel, but his approach still requires to conjecture
the value of $Z(x,1)$. In the two  other papers
\cite{dgg,gw},  a bijection between \tssps \ and rooted non-separable
planar maps is given, and the authors conclude thanks to the results of Brown and
Tutte \cite{brown-maps,brown-tutte} on the enumeration of maps.
\bigskip 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The number of descents ($u=v=1$)}
We shall now, step by step, ``solve'' the equation of in
Proposition \ref{Seq}, i.e., transform it into a polynomial equation. 
The first step is the case
$u=v=1$. It is achieved again via the quadratic method. We follow the
calculation of the previous section.
Our starting point is the equation
\beq \phi(1,1,t)=\frac{1}{1-xzt} +xt \ \left[ \frac{\phi(1,1,1)-\phi(1,1,t)}{1-t}\right]
\left[ \frac{\phi(1,1,1)-t\phi(1,1,t)}{1-t}\right]. \label{eq-simple-z} \eeq
(Recall that $\phi(1,1,t) $ stands for $\phi(x,z,1,1,t)$.)
The construction of a square involving all powers of
$\phi(1,1,t)$ gives
\beq (1-xzt)\left[ 1-t + xt\  \frac{(1+t)\phi(1,1,1)-2t\phi(1,1,t)}{1-t} \right] ^2
= E(t)\label{eq-lourde-z} \eeq
where
\bigskip
$$E(t)=1- \left[2+xz-2x\phi(1,1,1)\right]t \hskip 12cm$$
$$\hskip 3cm+
\left[1-4x+2xz+2x(1-xz)\phi(1,1,1) +x^2\phi(1,1,1)^2\right]t^2-   xz\left[
1+x\phi(1,1,1)\right]^2t^3.$$
Again, $E(t)$ has a double root at $t=T(x,z)$, where $T(x,z)=T$ is the
unique solution (in $\R[z][[x]]$) of
$$  T=1 + xT\  \frac{(1+T)\phi(1,1,1)-2T\phi(1,1,t)}{1-T},$$
and the resultant of
$E(t)$ and $\partial E /\partial t$, taken as polynomials in $t$, is
zero. We obtain the following refinement of Proposition \ref{x}.
%
%
\begin{propo} \label{xz} 
The \gf \ $S=\phi(x,z,1,1,1)$ for two-stack-sortable permutations,
counted according
to their length and number of descents, is algebraic of degree $5$ over
$\R (x,z)$:
$$x^4S^5+x^3(4zx-x+4) S^4+
x^2(-3zx^2+6z^2x^2+4zx-12x+6) S^3$$
$$+x(-3z^2x^3+4z^3x^3-4z^2x^2+8x^2+13zx^2-22x-4zx+4)
S^2$$
$$+(-z^3x^4+z^4x^4-20zx^3-4z^3x^3+26z^2x^3+32x^2+6z^2x^2-13
zx^2-12x-4zx+1) S$$
$$+z^3x^3-z^2x^3-3z^2x^2+20zx^2-16x^2+8x+3z x-1=0.$$
The Lagrange-Good inversion formula gives
$$\phi(x,z,1,1,1)=1+\sum_{1\le j \le n}
\frac{(2n-j)!(n+j-1)!}{(2n-2j+1)!(n-j+1)!(2j-1)!j!}x^nz^j.$$
The series $\phi(x,z,1,1,t)$ is algebraic of degree $10$ over $\R
(x,z,t)$, and $\R(x,z,t,\phi(x,z,1,1,t))$ contains $\phi(x,z,1,1,1)$.
\end{propo}
%
%
{\bf Proof.}  To obtain the expression of $\phi(1,1,1)$, we introduce the
series $U=U(x,z)$ and $V=V(x,z) $ defined by
\beq U=x(1+U)(1+V)^2 \ \ \ \hbox{and} \ \ \ V=xz(1+V)(1+U)^2,
\label{UVparam} \eeq
and then check that $1+V(1-UV)/(1+U)$ satisfies the same equation as $\phi(1,1,1)$.
This implies
that $$\phi(1,1,1)=1+V\ \frac{1-UV}{1+U}.$$
We conclude thanks to the Lagrange-Good inversion formula (see
\cite{gessel-lagrange} for instance). 

Eq. (\ref{eq-simple-z}) shows that $\phi(1,1,t)$ is at most quadratic over
$\R(x,z,t,\phi(1,1,1))$, and hence
algebraic of degree at most 10  over $\R (x,z,t)$.
The (minimal) algebraic equation it satisfies can  be obtained by
eliminating $\phi(1,1,1)$ in
(\ref{eq-simple-z}): it has degree exactly $10$ --- and takes
several Maple pages.
To obtain an ``explicit'' expression of $\phi(1,1,t)$, we can go back
to (\ref{eq-lourde-z}). Expressing $x$, $z$ and $\phi(1,1,1)$ in terms
of $U$ and $V$, we  factor $E(t)$:
$$E(t)=(1-\alpha t)^2(1-\beta t),$$
where $\alpha$ and $\beta$ are  series in $x$ and $z$:
$$ \alpha = \frac{xz}{V}(1+U+V) \ \ \ \ 
\hbox{and} \ \ \ \  \beta = xz(1+2U)^2.$$
This gives finally:
\beq 2xt^2\phi(1,1,t)=(1-t)^2+xt(1+t)\phi(1,1,1)-(1-t)(1-\alpha
t)\sqrt{\frac{1-\beta t}{1-xzt}}. \label{Z11t-Z111}\eeq

\cqfd
\noindent{\bf Note.} Again, the idea of introducing the series $U$ and
$V$ satisfying (\ref{UVparam}) is only natural after having
conjectured the expansion of $\phi(x,z,1,1,1)$. This expansion was
 obtained bijectively by Dulucq, Gire and Guibert \cite{dgg,guibert-these} and
Goulden and West \cite{gw}: it is equivalent to the enumeration of
non-separable planar maps according to the number of edges and
vertices \cite{brown-tutte}.

\section{Descents and left-to-right maxima ($u=1$)}
Let us now climb one more step, by handling the equation of
Proposition \ref{Seq} in the case $u=1$. The equation reads:
$$\phi(1,v,t)=\frac{v}{1-xzt}  + xt \left[ v(1-v)+\frac{
(v+t-tv)\phi(1,v,1)-\phi(1,v,t)}{1-t}
\right]
\left[\frac{\phi(1,1,1)-t\phi(1,1,t)}{1-t} \right].$$
It can be rewritten as
\beq \left[ \frac{\phi(1,v,t)-(v+t-tv)\phi(1,v,1)}{1-t}-v(1-v)\right]
\left[ 1-t+xt \ \frac {\phi(1,1,1)-t\phi(1,1,t)}{1-t} \right] \hskip 5cm
\label{eqvt}\eeq
$$\hskip 5cm =\frac{v}{1-xzt} -(v+t-tv) \phi(1,v,1) -v(1-v)(1-t).$$
Let $T=T(x,z)$ be the (unique) formal power series in $x$ and $z$ satisfying
$$T= 1+xT \ \frac {\phi(1,1,1)-T\phi(1,1,T)}{1-T}.$$
Note that $T$ does not depend on $v$. Substituting $T$ for $t$ in
(\ref{eqvt}) shows that for any $v$, 
\beq (v+T-Tv) \phi(1,v,1) =\frac{v}{1-xzT} -v(1-v)(1-T). \label{Tv}\eeq
In particular, for $v=1$, we obtain
\beq \phi(1,1,1)=\frac{1}{1-xzT}. \label{T1} \eeq
We can eliminate $T$ between (\ref{Tv}) and (\ref{T1}) to obtain
$\phi(1,v,1)$ as a {\em rational function\/} of $x,v,z$ and
$\phi(1,1,1)$.
%
%
\begin{propo} \label{xzv} The \gf \ $\phi(x,z,1,v,1)$ 
for two-stack-sortable permutations, counted according
to their length, number of descents and number of left-to-right
maxima, is given by
\beq \phi(x,z,1,v,1)=v+xzv\phi(1,1,1)\ \frac{1- \phi(1,1,1)}
{1-\phi(1,1,1)-v\left[ 1+(xz-1)\phi(1,1,1)\right]}, \label{eqxzv} \eeq
where $\phi(1,1,1)$ is the \gf \ for these permutations, according
to their length and number of descents, given by Proposition
{\em \ref{xz}}.
In other words, the length \gf \ for \tssps \ having $m$ left-to-right
maxima is
$$xz\phi(1,1,1) \left[ \frac{1+(xz-1)\phi(1,1,1)}{1-\phi(1,1,1)} \right] ^{m-1}.$$
In particular, $\phi(x,z,1,v,1)$ is algebraic of degree $5$ over
$\R (x,z,v)$, and $\K (\phi(1,v,1)) = \K (\phi(1,1,1))$.\\
Moreover,  $\K
(\phi(1,v,t)) = \K (\phi(1,1,t))$, and $\phi(1,v,t)$ is algebraic of
degree $10$ over $\R(x,z,v,t)$.
\end{propo}
%
%
{\bf Proof.}
The degree of $\phi(1,v,1)$ over $\K$ is bounded from above {\em and\/} from
below by the degree of $\phi(1,1,1)$:

-- from above, because  Eq. (\ref{eqxzv}) shows that $\phi(1,v,1)$
belongs to $\K(\phi(1,1,1))$;

-- from below, because  $\phi(1,1,1)$ is a specialization
of $\phi(1,v,1)$.\\
Hence the extensions $\K
(\phi(1,v,1))$ and $ \K (\phi(1,1,1))$ coincide and are of degree $5$
over $\K$. \\
According to Eq.  (\ref{eqvt}), a similar relation links  $\phi(1,v,t)$ and
$\phi(1,1,t)$. Hence, they have the same degree.
\cqfd
\noindent{\bf Remarks}


1. The algebraic equation satisfied by $\phi(1,v,1)$, obtained by
eliminating $\phi(1,1,1)$ in  (\ref{eqxzv}), has very big
coefficients, and we do not write it here. When $z=1$, the series
$\phi(1,1,1)$ is  only cubic (see Proposition \ref{x}), and 
so is $S=\phi(1,v,1)$. Here is the cubic equation it satisfies:
$$(x^4v^3+5x^3v^3+6x^3v^2-8x^2v^3-5x^2v^2+xv^3+12x^2v+8xv^2-17xv-v^2+8x+2v-1) S^3-v(3x^4v^3-6x^4v^2$$
$$+15x^3v^3-26x^3v^2-24x^2v^3-24x^3v-16x^2v^2+3xv^3+
45x^2v+25xv^2-24x^2-37xv-3v^2+11x+4v-1) S^2$$
$$+v^2(3x^4v^3-12x^4v^2+15x^3v^3+12x^4v-70x^3v^2-24x^2v^3+50x^3v-17x^2v^2+3xv^3+24x^3+48x^2v+26xv^2-163x^2$$
$$-24xv-3v^2+20x+2v)
S-v^3(x^4v^3-6x^4v^2+5x^3v^3+12x^4v-38x^3v^2-8x^2v^3-8x^4$$
$$+74x^3v-6x^2v^2+xv^3-63x^3+15x^2v+9xv^2-
120x^2-4xv-v^2+16x) =0.$$

2. It would be interesting to know which statistic defined on
non-seperable maps
corresponds to the number of left-to-right maxima of a \tssp \ through
the bijections described in \cite{dgg} and \cite{gw}.



\section{Descents and right-to-left maxima ($v=1$)}
The last step before we can complete the solution of (\ref{principale})
is the case $v=1$. The equation reads:
\beq \phi(u,1,t)=\frac{1}{1-xzut}  + xut \left[ \frac{
\phi(1,1,1)-\phi(1,1,tu)}{1-tu}
\right]
\left[\frac{\phi(u,1,1)-t\phi(u,1,t)}{1-t} \right].\label{eq-sec5} \eeq
It can be rewritten as
\beq \left[ \frac{t\phi(u,1,t)-\phi(u,1,1)}{1-t} \right] \left[ 1-t + xut^2
\ \frac{\phi(1,1,1)-\phi(1,1,tu)}{1-ut}\right] = \frac{t}{1-xzut}
-\phi(u,1,1).\label{equt} \eeq
Let $T=T(x,z,u)$ be the (unique) formal power series in $x, z$ and $u$
satisfying
\beq T= 1 + xuT^2 \ 
\frac{\phi(1,1,1)-\phi(1,1,Tu)}{1-uT}. \label{eq-Tu} \eeq
Substituting $T$ for $t$ in (\ref{equt}) shows that 
\beq  \phi(u,1,1)=\frac{T}{1-xzuT}. \label{equT} \eeq
We can obtain the quadratic equation (on
$\R(x,z,u,\phi(1,1,1))$) satisfied by $T(x,z,u)$ by eliminating
$\phi(1,1,Tu)$ between (\ref{eq-Tu}) and  (\ref{eq-simple-z}), in which $t$ is
replaced by $Tu$. We find:
$$1-u-T\left[ 1-u+xzu-xzu^2-xu\phi(1,1,1) \right]
-xuT^2\left[ 1-z+zu+xzu\phi(1,1,1)\right]  =0.$$
Finally, Eq.  (\ref{equT}) gives, from the equation satisfied by $T$,
the equation satisfied 
by $\phi(u,1,1)$.
%
%
\begin{propo}  \label{xzu} The \gf \ $\phi(u,1,1)=\phi(x,z,u,1,1)$ 
for two-stack-sortable permutations, counted according
to their length, number of descents and number of right-to-left maxima, is
quadratic on $\R(x,z,u,\phi(1,1,1))$:
\beq 1-u -\phi(u,1,1) \left[ 1-u-xzu+xzu^2-xu\phi(1,1,1)\right]
-xu \phi(u,1,1)^2=0. \label{xzu-eq-f1} \eeq
It is algebraic of degree $10$ over $\R (x,z,u)$. We can expand it
 explicitely: for $1 \le m \le j <n$, the number of \tssps \ of length
$n$ having $j$ descents and $m$ right-to-left maxima is
$$ \sum_{k=1}^{\min(m+1,n-j+1)}
\left[ (m-k+1) P(n,j,m,k,0) - \frac{2(k-1)(j-m)}{2n-2j-k+2}
P(n,j,m,k,1) \right]$$
$$
\times \frac{(n+j-m-1)!}{(n-j-k+1)!(2j-m+k-1)!}
\frac{(2n-j-m-k)!}{(j-m)!(2n-2j-k+1)!}
\frac{(m+k-2)!}{k!(k-1)!(m-k+1)!}$$
where $P(n,j,m,k,e)$ is the following polynomial:
$$P(n,j,m,k,e)=(2n-j-m-k+1)(2j-m+k-1)-(j-m-e)(4n-2j-3k-m+3).$$
The series
$\phi(x,z,u,1,t)$ is algebraic of degree $20$ over $\R (x,z,u,t)$.
\end{propo}
%
%
{\bf Proof.} Eq. (\ref{xzu-eq-f1}) shows that $\R(x,z,u,\phi(u,1,1))$
contains $\phi(1,1,1)$. In order to prove that $\phi(u,1,1)$ is
exactly quadratic on $\R(x,z,u,\phi(1,1,1))$, we have to show that the
discriminant $\Delta$ of (\ref{xzu-eq-f1}) is not a square in
$\R(x,z,u,\phi(1,1,1))= \R(u,U,V)$, where the series $U$ and $V$ are
defined by (\ref{UVparam}). Expressing $\Delta$ in terms of $u, U$ and
$V$ gives:
$$\Delta = (1+V)^2(1+U-u)^2\left[
(1+U)^2(1+V)^2-2uV(1+U)(1+2U+V)+u^2V^2\right].$$  
This discriminant cannot be factored further, and  $\phi(u,1,1)$ is
exactly quadratic on $\R(x,z,u,\phi(1,1,1))$ -- and thus of degree
$10$ over $\R(x,z,u)$. \\
We can now solve (\ref{xzu-eq-f1}) in terms of $u,U$ and $V$:
$$\phi(u,1,1)= \frac{1+V}{2uU(1+U)} \left[
-(1+V)(1+U)^2+u(1+U)(1+2U+2V)-u^2V  \frac{}{} \right.$$
$$\hskip 8mm
\left. +(1+U-u)((1+U)(1+V)-uV) 
\left( 1-\frac{4uUV(1+U)}{((1+U)(1+V)-uV)^2} \right)^{1/2} \right].$$
Expanding this solution in $u$ gives
$$\phi(u,1,1)=1+ \sum_{m\ge 1} \frac{u^m V^m}{U(1+U)^m (1+V)^{m-2}}
\sum_{k=1}^{m+1} \frac{(m+k-2)!}{k!(k-1)!(m-k+1)!}
\frac{U^k}{(1+V)^{k+1}} \left[ m-k+1+2(1-k)V \right].$$
We conclude thanks to the Lagrange-Good inversion formula.

Let us now consider $\phi(u,1,t)$. From (\ref{equt}), we conclude
that this series belongs to $\K(\phi(1,1,tu),\phi(u,1,1))$. In the
proof of Proposition \ref{xz}, we have seen (\ref{Z11t-Z111})  that
$$\K (\phi(1,1,tu)) = \K\left( \phi(1,1,1),
\sqrt{\frac{1-tu\beta}{1-xtu}} \right),$$
and thus $\phi(1,1,tu)$ cannot belong to $\K(\phi(u,1,1))$ (which
only contains rational functions in $t$). Hence, $\phi(1,1,tu)$ is quadratic over $\K(\phi(u,1,1))$, and $\K(\phi(1,1,tu),\phi(u,1,1))$ is of degree $20$ over
$\K$. In particular, $\phi(u,1,t)$ is of degree at most 20 on $\K$.
We can obtain an algebraic equation of degree $20$ satisfied by
$\phi(u,1,t)$ by 
eliminating from (\ref{eq-sec5}) first $\phi(1,1,tu)$ (using (\ref{eq-simple-z})), then
$\phi(u,1,1)$ (using (\ref{xzu-eq-f1})), and finally $\phi(1,1,1)$ (using
Proposition \ref{xz}). To check that this polynomial
is irreducible, it suffices to do this calculation for some
well-chosen values of $z,u$ and $t$: for instance, when $z=u=t=-1$,
the eliminations described above provide an {\em irreducible\/}
polynomial in $x$ and $\phi(u,1,t)$ of degree $20$.
%The final, irreducible polynomial we obtain is of degree $20$ exactly,
%and thus $\K(\phi(u,1,t))= \K(\phi(1,1,tu),\phi(u,1,1))$.
\cqfd
\noindent{\bf Note.} When $z=1$, a similar calculation can be done,
using the series $Y$ introduced in the proof of Proposition
\ref{x}. We obtain the number of \tssps \ of length $n$ having $m$
right-to-left maxima, as given in \cite{dgg}.

\bigskip
\noindent{\bf Remark.} According to \cite{dgg} and \cite{gw}, the number of
two-stack-sortable permutations of length $n$ having $j$ descents
(including $n$, by convention in this paper) and $m$ right-to-left
maxima is the number of rooted non-separable maps having $n+1$
edges, $j+1$ vertices and such that the degree of the root face
 is $m+1$. The enumeration of these maps according to the number of
edges and degree of the root face was achieved by Brown \cite{brown-maps}.
His work was extended by Brown and Tutte who also took into account
the number of vertices   \cite{brown-tutte}. To recover their result,
let us define 
$$B(x,u,z)= \sum_{n \ge 2, m \ge 2, j \ge 2} B_{n,m,j} \ x^n u^m z^j,$$
where $B_{n,m,j}$ is the number of non-separable maps having $n$
edges, $j$ vertices, and such that the degree of the root face is
$m$.
Then $B(x,u,z)= xzu (\phi(x,z,u,1,1)-1)$, and we derive from
Proposition \ref{xzu} the following equation for $B$:
$$B(x,u,z)^2+B(x,u,z) \left[ z(1-u)+xzu(1-z+zu)-uB(x,1,z)\right]
-xzu^2\left[ xz^2(1-u)+B(x,1,z)\right] =0.$$
This is equivalent to  Eq. (3.4) of
\cite{brown-tutte}. Proposition \ref{xzu} also provides the following
corollary.
\begin{coro}  The number of rooted non-separable maps having $n$
edges, $j$ vertices and such that the degree of the root face
 is $m$, is $1$ if $j=m=n\ge2$ and otherwise
$$\sum_{k=1}^{\min(m,n-j+1)}
\left[ (m-k) Q(n,j,m,k,0) - \frac{2(k-1)(j-m)}{2n-2j-k+2}
Q(n,j,m,k,1) \right]$$
$$
\times  \frac{(n+j-m-2)!}{(n-j-k+1)!(2j-m+k-2)!}
\frac{(2n-j-m-k)!}{(j-m)!(2n-2j-k+1)!}
\frac{(m+k-3)!}{k!(k-1)!(m-k)!},$$
 where $Q(n,j,m,k,e)$ is the following polynomial:
$$Q(n,j,m,k,e)=(2n-j-m-k+1)(2j-m+k-2)-(j-m-e)(4n-2j-3k-m+2).$$
\end{coro}

\section{The complete generating function}
Eq. (\ref{principale}), combined with the results of the previous sections,
summarized in Figure \ref{figure}, shows that $\phi(u,v,t)$ belongs to
$\K(\phi(u,1,t))$. Hence, it is of degree at most $20$ over $\K$. But
its degree is at least the degree of $\phi(u,1,t)$ (which is a
specialization of $\phi(u,v,t)$), and thus the complete \gf \
$\phi(x,z,u,v,t)$  is of degree exactly 20 over $\R(x,z,u,v,t)$.

The only result that is still missing is the degree of
$\phi(x,z,u,v,1)$, which counts \tssps \ according to the four most
natural statistics we defined in Section \ref{intro}. To fill in this
gap, let us, for the last time, consider the equation of Proposition
\ref{Seq}:
$$\phi(u,v,t)=\frac{v}{1-xzut}  + xut \left[ v(1-v)+\frac{
(v+tu-tuv)\phi(1,v,1)-\phi(1,v,tu)}{1-tu}
\right]
\left[\frac{\phi(u,1,1)-t\phi(u,1,t)}{1-t}
\right]. $$
Using Eqs. (\ref{eqvt}) (with $tu$ instead of $t$) and (\ref{equt}), we can
rewrite this equation as:
$$\phi(u,v,t)=\frac{v}{1-xzut}+ xut \ \frac{
\left[ \frac{v}{1-xzut}-v(1-v)(1-ut)-(v+tu-tuv)\phi(1,v,1)\right]
\left[
\frac{t}{1-xzut}-\phi(u,1,1) \right]}
{\displaystyle 
\left[ 1-tu +xtu \ \frac{\phi(1,1,1)-tu\phi(1,1,tu)}{1-tu}\right]
\left[ 1-t +xut^2 \ \frac{\phi(1,1,1)-\phi(1,1,tu)}{1-tu}\right]
}.$$
Now, we use Eq. (\ref{eq-simple-z}) (with $t$ replaced by $tu$) to remove the
quadratic terms from the denominator:
$$\phi(u,v,t)=\frac{v}{1-xzut}+ xut \ 
\frac{\left[ \frac{v}{1-xzut}-v(1-v)(1-ut)-(v+tu-tuv)\phi(1,v,1)\right] 
\left[
\frac{t}{1-xzut}-\phi(u,1,1) \right]}
{\displaystyle (1-t)(1-tu)-\frac{xut^2}{1-xzut}+\frac{xut (1-t^2u)
\phi(1,1,1)}{1-tu}
-\frac{xu^2t^2(1-t)\phi(1,1,tu)}{1-tu}}.$$
In particular, for $t=1$, we obtain:
$$\phi(u,v,1)=\frac{v}{1-xzu}+  \frac{
\left[ \frac{v}{1-xzu}-v(1-v)(1-u)-(v+u-uv)\phi(1,v,1)\right]
\left[
\frac{1}{1-xzu}-\phi(u,1,1) \right]}
{\phi(1,1,1)-\frac{1}{1-xzu}}.$$
This shows that $\phi(u,v,1)$ belongs to $\K(\phi(u,1,1))$. Hence, its
degree is bounded from above by the degree of $\phi(u,1,1)$,
which is $10$. But its degree is also bounded from below by the degree of
$\phi(u,1,1)$, which is a specialization of $\phi(u,v,1)$. This adds
the last brick to the wall of Figure \ref{figure}.
\cqfd

\bigskip 
\noindent {\bf Aknowledgements} to Gilles Schaeffer, first because he taught me
nothing less than the quadratic method, and then for his helpul comments on this note.


\begin{thebibliography}{99}
\bibitem{bousquet-sortable} M. Bousquet-M\'elou, Sorted and/or sortable
permutations, to be presented at  the 10th Conference ``Formal Power Series
and Algebraic Combinatorics'', Toronto, June 1998. 

\bibitem{bousquet-temperley}
M.~Bousquet-M\'elou,
\newblock A method for the enumeration of various classes of column-convex
  polygons,
\newblock {\em Discrete Math.} {\bf 154} (1996) 1--25.

\bibitem{brown-maps} W. G. Brown, Enumeration of non-separable planar
maps, {\em Canad. J. Math.} {\bf 15} (1963) 526--545.

\bibitem{brown} W. G. Brown,
On the existence of square roots in certain rings of power series,
{\em Math. Annalen} {\bf 158} (1965) 82-89.

\bibitem{brown-dissections} W. G. Brown, Enumeration of quadrangular
dissections of the disk, {\em Canad. J. Math.} {\bf 17} (1965) 302--317.

\bibitem{brown-tutte}  W. G. Brown and W. T. Tutte, 
On the enumeration of rooted non-seperable
planar maps, {\em Canad. J. Math.} {\bf 16} (1964) 572--577.


\bibitem{cori} R. Cori, B. Jacquard and G. Schaeffer, Description
trees for some families of planar maps, Proceedings of the $9$th
Conference ``Formal 
Power Series and Algebraic Combinatorics'', Vienna, 1997, pp. 196--208.

\bibitem{dgg}
S. {Dulucq}, S. {Gire}  and O. {Guibert}, 
\newblock {A} combinatorial proof of {J}.~{W}est's conjecture. To
appear in {\em Discrete  Math.}

\bibitem{dgw} S. {Dulucq}, S. {Gire} and J. West, Permutations with
forbidden subsequences and non-separable planar maps, {\em Discrete
Math.} {\bf 153} (1996) 85--103.

\bibitem{feretic-svrtan}
S.~Fereti\'c and D.~Svrtan,
\newblock On the number of column-convex polyominoes with given perimeter and
  number of columns,
\newblock in {\em Proceedings
  of the $5^{th}$ conference Formal Power Series and Algebraic
Combinatorics}, A.~Barlotti, M.~Delest, and R.~Pinzani eds.,
  pages 201--214, Florence, june 1993.

\bibitem{gao} 
Z.-G. Gao, The number of rooted triangular maps on a surface, {\em
J. Combin. Theory Ser. B} {\bf 52} (1991) 236--249.

\bibitem{gessel-lagrange} I. Gessel, A combinatorial proof of the
multivariable Lagrange inversion formula, {\em J. Combin. Theory
Ser. A} {\bf 45} (1987) 178--195.

%\bibitem{gessel} I. Gessel, Enumerating two-stack sortable
%multipermutations, {\em Abstracts Amer. Math. Soc.} {\bf 15} (1994) 535.

\bibitem{gj} I. P. Goulden and D. M. Jackson, {\em Combinatorial
enumeration,} John Wiley and  Sons, 1983.

\bibitem{gw} I. P. Goulden and J. West, Raney paths and a
combinatorial relationship between rooted non-separable planar maps
and two-stack-sortable permutations, {\em J. Combin. Theory Ser. A}
{\bf 75} (1996) 220--242.

\bibitem{guibert-these} O. Guibert, Combinatoire des permutations \`a
motifs exclus en liaison avec mots, cartes planaires et tableaux de
Young, Ph.D. thesis, Universit\'e Bordeaux 1, 1995.

\bibitem{knuth} D. E. Knuth, {\em The art of computer programming\/}
Vol.1, {\em Fundamental algorithms}, Addison-Wesley, Reading, Massachusetts,
1973.

\bibitem{ab}
M.~Petkov{\u s}ek, H.~S. Wilf, and D.~Zeilberger,
\newblock {\em {$A=B$}},
\newblock A. K. Peters, Wellesley, Massachusetts, 1996.

\bibitem{gfun}
B.~Salvy and P.~Zimmermann.
\newblock {GFUN}: a {MAPLE} package for the manipulation of generating and
  holonomic functions in one variable,
\newblock {\em ACM Transactions on Mathematical Software} {\bf 20}
(1994) 163--167 (see also
{\tt http://pauillac.inria.fr/algo/libraries/libraries.html}). 


\bibitem{tutte-census} W. T. Tutte, A census of planar maps, {\em
Canad. J. Math.} {\bf 15} (1963) 249--271.

\bibitem{west} J. West, Permutations with restricted subsequences and
stack-sortable permutations, Ph.D. thesis, MIT, 1990.

\bibitem{west-sfca} J. West, Sorting twice through a stack, {\em
Theoret. Comput. Sci.} {\bf 117} (1993) 303--313.

\bibitem{zeil} D. Zeilberger, A proof of Julian West's conjecture that
the number of two-stack-sortable permutations of length $n$ is
$2(3n)!/((n+1)!(2n+1)!)$, {\em Discrete Math.} {\bf 102} (1992) 85--93.

\end{thebibliography}
\end{document}