Bijections for Baxter Families and Related Objects

Abstract

The Baxter number can be written as $B_n={\sum }_0^n{\Theta }_{k,n-k-1}$. 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 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.

31 pages, 22 figures, submitted to JCTA

References in corpus (2)

• Improved Compact Visibility Representation of Planar Graph via Schnyder's Realizer
• Orthogonal surfaces

Cited by in corpus (26)

• Cambrian Hopf Algebras
• The Hopf algebra of diagonal rectangulations
• Generic rectangulations
• Schnyder woods, SLE(16), and Liouville quantum gravity
• Tableau sequences, open diagrams, and Baxter families
• Scaling and local limits of Baxter permutations and bipolar orientations through coalescent-walk processes
• Counting elements and geodesics in Thompson's group $F$
• The Expected Shape of Random Doubly Alternating Baxter Permutations
• A generating tree approach to k-nonnesting partitions and permutations
• The skew Brownian permuton: a new universality class for random constrained permutations
• A Note on Flips in Diagonal Rectangulations
• On the number of planar Eulerian orientations
• A Baxter class of a different kind, and other bijective results using tableau sequences ending with a row shape
• Bijective counting of plane bipolar orientations and Schnyder woods
• Plane bipolar orientations and quadrant walks
• Orders induced by segments in floorplan partitions and (2-14-3,3-41-2)-avoiding permutations
• Mixing Times of Markov Chains on Degree Constrained Orientations of Planar Graphs
• The Flip Diameter of Rectangulations and Convex Subdivisions
• Rectangulotopes
• Coxeter-biCatalan combinatorics
• The generating function of planar Eulerian orientations
• Bijective counting of involutive Baxter permutations
• Slicings of parallelogram polyominoes: Catalan, Schröder, Baxter, and other sequences
• New bijective links on planar maps via orientations
• Schnyder decompositions for regular plane graphs and application to drawing
• Pattern avoidance in partial permutations