Séminaire Lotharingien de Combinatoire, B30g (1993), 11 pp.
[Formerly: Publ. I.R.M.A. Strasbourg, 1993, 1993/034, p. 19-28.]

Serge Dulucq, Sophie Gire, Olivier Guibert and Julian West

Enumération de permutations à motifs exclus

Abstract. 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: