Bijections for Baxter families and related objects

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:118

Article

Felsner, Stefan¹  Fusy, Eric²  Noy, Marc³  Orden, David⁴ 

[1] Tech Univ Berlin, Inst Math, D-1000 Berlin, Germany

[2] Ecole Polytech, Lab Informat LIX, F-91128 Palaiseau, France

[3] Univ Politecn Cataluna, Dept Matemat Aplicada 2, E-08028 Barcelona, Spain

[4] Univ Alcala, Dept Matemat, Alcala De Henares, Spain

关键词: Baxter numbers;    Bijections;    Catalan numbers;    Orientations of planar maps;    Schnyder woods;   

DOI  :  10.1016/j.jcta.2010.03.017

来源: Elsevier

【 摘 要 】

The Baxter number B-n can be written as B-n = Sigma(n)(k=0) Theta(k,n-k-1) with Theta(k,l) = 2/(k + 1)(2)(k + 2)(k + l k)(k + l + 1 k)(k + l + 2 k). These numbers have first appeared in the enumeration of so-called Baxter permutations; B-n is the number of Baxter permutations of size n, and Theta(k,l) is the number of Baxter permutations with k descents and l rises. With a series of bijections we identify several families of combinatorial objects counted by the numbers Theta(k,l). Apart from Baxter permutations, these include plane bipolar orientations with k + 2 vertices and l + 2 faces, 2-orientations of planar quadrangulations with k + 2 white and l + 2 black vertices, certain pairs of binary trees with k + 1 left and l + 1 right leaves, and a family of triples of non-intersecting lattice paths. This last family allows us to determine the value of Theta(k,l), as an application of the lemma of Lindstrom Gessel-Viennot. The approach also allows us to count certain other subfamilies, e.g., alternating Baxter permutations, objects with symmetries and, via a bijection with a class of plane bipolar orientations, also Schnyder woods of triangulations. Most of the enumerative results and some of the bijections are not new. Our contribution is mainly in the simplified and unifying presentation of this beautiful piece of combinatorics. (C) 2010 Elsevier Inc. All rights reserved.

【 授权许可】

Free