Bijective Counting of Involutive Baxter Permutations

Issue title: Lattice Path Combinatorics and Applications

Article type: Research Article

Authors: Fusy, Éric

Affiliations: LIX, École Polytechnique, 91128 Palaiseau Cedex, France, [email protected]

Note: [] Supported by the European Research Council under the European Community's 7th Framework Programme, ERC grant agreement no 208471 - ExploreMaps project Address for correspondence: LIX, É cole Polytechnique, 91128 Palaiseau Cedex, France

Abstract: We enumerate bijectively the family of involutive Baxter permutations according to various parameters; in particular we obtain an elementary proof that the number of involutive Baxter permutations of size 2n with no fixed points is ${3\cdot2^{n-1}\over (n+1)(n+2)} \big({2n \atop n}\big)$, a formula originally discovered by M. Bousquet-Mélou using generating functions. The same coefficient also enumerates planar maps with n edges, endowed with an acyclic orientation having a unique source, and such that the source and sinks are all incident to the outer face.

Keywords: Bipolar orientations, bijections, planar maps, lattice paths

DOI: 10.3233/FI-2012-694

Journal: Fundamenta Informaticae, vol. 117, no. 1-4, pp. 179-188, 2012