ProV Logo
0
Bijections for Baxter Families and Relat...
Felsner, Stefan...

Free

Bijections for Baxter Families and Related Objects by Felsner, Stefan ( Author )
Lemonjar Open Access
N.A
11-03-2008
The Baxter number can be written as Bn=∑n0Θk,n−k−1. These numbers have first appeared in the enumeration of so-called Baxter permutations; Bn is the number of Baxter permutations of size n, and Θ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 Θ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 Θk,l as an application of the lemma of Gessel and 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 plan bipolar orientations also Schnyder woods of triangulations, which are known to be in bijection with 3-orientations.
-
Article
pdf
36.88 KB
English
-
MYR 0.00
-
https://arxiv.org/abs/0803.1546
Share this eBook