Séminaire Lotharingien de Combinatoire, B30g (1993), 11
[Formerly: Publ. I.R.M.A. Strasbourg, 1993, 1993/034, p.
Serge Dulucq, Sophie Gire, Olivier Guibert and Julian West
Enumération de permutations à motifs exclus
We give a combinatorial proof that two-stack sortable permutations
are equinumerous with rooted nonseparable planar maps, by making
use of the concept of generating trees. To be precise, we construct
generating trees for both objects under consideration and show
that they are isomorphic. A detailed study of the correspondence
allows us to conclude refined enumeration results where we are
also able to keep track of several parameters defined for
these permutations, respectively these maps.
The following version are available: