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: