Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "Matchings avoiding partial patterns and lattice paths"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Matchings avoiding partial patterns and lattice paths. | Matchings avoiding partial patterns and lattice paths Vit Jelinek Department of Applied Mathematics Charles University Malostranské námẽstí 25 Prague Czech Republic. jelinek@kam.mff.cuni.cz Nelson Y. Li Center for Combinatorics LPMC Nankai University 300071 Tianjin P.R. China nelsonli@eyou.com Toufik Mansour Department of Mathematics University of Haifa 31905 Haifa Israel. Center for Combinatorics LPMC Nankai University 300071 Tianjin P.R. China toufik@math.haifa.ac.il Sherry H. F. Yan Center for Combinatorics LPMC Nankai University 300071 Tianjin P.R. China huifangyan@eyou.com Submitted May 17 2006 Accepted Sep 29 2006 Published Oct 19 2006 Mathematics Subject Classihcation 05A05 05C30. Abstract In this paper we consider matchings avoiding partial patterns 1123 and 1132. We give a bijection between 1123-avoiding matchings with n edges and nonnegative lattice paths from 0 2 to 2n 0 . As a consequence the rehned enumeration of 1123-avoiding matchings can be reduced to the enumeration of certain lattice paths. Another result of this paper is a bijection between 1132-avoiding matchings with n edges and lattice paths from 0 0 to 2n 0 starting with an up step which may go under the x-axis. 1 Introduction A matching on a set 2n 1 2 . 2ng is a partition of 2n of the type 2 2 . 2 or equivalently a graph in which every vertex has degree one. There are many ways to THE ELECTRONIC JOURNAL OF COMBINATORICS 13 2006 R89 1 represent a matching. It can be displayed by drawing 2n points in the plane lying on a horizontal line and connecting them by n arcs each arc connecting two of the points and lying above the points such representation is called the linear representation of the matching 1 . An edge i j is drawn as an arc between the nodes i and j above the horizontal line where the vertices i and j are called the initial point and the end point respectively. An edge e i j is always written in such a way that i j. Let e i j and e i j be two edges of a matching M we say that e .