Per accedir als documents amb el text complet, si us plau, seguiu el següent enllaç: http://hdl.handle.net/2117/12212

Títol:	Bijections for Baxter families and related objects
Autor/a:	Felsner, Stefan; Fusy, Éric; Noy Serrano, Marcos; Orden, David
Altres autors:	Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II; Universitat Politècnica de Catalunya. MD - Matemàtica Discreta
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.
Matèries:	-Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Teoria de grafs -Àrees temàtiques de la UPC::Matemàtiques i estadística::Matemàtica discreta::Combinatòria -Catalan numbers (Mathematics) -Combinatorial analysis -Graph theory -Nombres naturals -Anàlisi combinatòria -Grafs, Teoria de -Classificació AMS::05 Combinatorics::05A Enumerative combinatorics -Classificació AMS::05 Combinatorics::05C Graph theory
Drets:	Attribution-NonCommercial-NoDerivs 3.0 Spain http://creativecommons.org/licenses/by-nc-nd/3.0/es/
Tipus de document:	Article - Versió publicada Article
Compartir:

Mostra el registre complet del document