کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
4656128 1343420 2011 28 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Bijections for Baxter families and related objects
موضوعات مرتبط
مهندسی و علوم پایه ریاضیات ریاضیات گسسته و ترکیبات
پیش نمایش صفحه اول مقاله
Bijections for Baxter families and related objects
چکیده انگلیسی

The Baxter number BnBn can be written as Bn=∑k=0nΘk,n−k−1 withΘk,ℓ=2(k+1)2(k+2)(k+ℓk)(k+ℓ+1k)(k+ℓ+2k). These numbers have first appeared in the enumeration of so-called Baxter permutations; BnBn is the number of Baxter permutations of size n  , and Θk,ℓΘk,ℓ is the number of Baxter permutations with k descents and ℓ   rises. With a series of bijections we identify several families of combinatorial objects counted by the numbers Θk,ℓΘk,ℓ. Apart from Baxter permutations, these include plane bipolar orientations with k+2k+2 vertices and ℓ+2ℓ+2 faces, 2-orientations of planar quadrangulations with k+2k+2 white and ℓ+2ℓ+2 black vertices, certain pairs of binary trees with k+1k+1 left and ℓ+1ℓ+1 right leaves, and a family of triples of non-intersecting lattice paths. This last family allows us to determine the value of Θk,ℓΘk,ℓ as an application of the lemma of Lindström 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.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Combinatorial Theory, Series A - Volume 118, Issue 3, April 2011, Pages 993–1020
نویسندگان
, , , ,