Séminaire Lotharingien de Combinatoire, B33c (1994), 9 pp.
S. Dulucq, O. Guibert
Permutations de Baxter
Abstract.
Chung, Graham, Hoggatt and Kleiman
have given an explicit formula for the number of Baxter permutations
on [n].
Viennot has then given a combinatorial proof
of this formula, showing this sum corresponds to the distribution
of these permutations according to their number of rises.
Cori, Dulucq and Viennot,
by making a correspondence between two families of planar maps,
have shown that the number of alternating Baxter permutations
on [2n+d] is the (n+d)-th Catalan number.
We establish a new one-to-one correspondence between the
Baxter permutations and three nonintersecting paths,
which unifies the previous approaches.
Moreover, we obtain more precise results for the enumeration of
(alternating or not) Baxter permutations
according to various parameters.
This provides a combinatorial interpretation of Mallows's formula.
The following versions are available: