tailieunhanh - Báo cáo toán học: "On generalized Dyck paths"

Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí Department of Mathematic dành cho các bạn yêu thích môn toán học đề tài: On generalized Dyck paths. | On generalized Dyck paths Josef RukavickaJ Submitted Nov 15 2010 Accepted Feb 3 2011 Published Feb 14 2011 Mathematics Subject Classification 05A15 Abstract We generalize the elegant bijective proof of the Chung Feller theorem from the paper of Young-Ming Chen The Chung-Feller theorem revisited Disc. Math. 308 2008 1328-1329 . 1 Introduction In 1 the Chung Feller theorem has been proved by presenting a bijection between n-Dyck paths with j flaws and n-Dyck paths with j 1 flaws for j 0 1 . n 1. The Chung Feller theorem states that the number of n-Dyck paths with j flaws is independent of j and is equal to the Catalan number Cn. The bijection consists in switching selected parts of a Dyck path in such a way the number of flaws increases by one. The author showed how to select the parts to be switched and proved that it is a bijection. In this paper we present a generalized version of the proof for Dyck paths with additional requirements concerning the length and the number of horizontal steps. 2 contains a result that covers the main result here using analytic method. The merit of the current paper is that it offers a simple and elegant bijective proof. 2 Bijection of Dyck paths We consider a Dyck path p as a sequence of n vertical steps of the length 1 meaning one edge of a grid and k n horizontal steps of the lengths l1 l2 . lk in a grid of n X n squares such that 11 12 lk n. The number of flaws is considered as the number of vertical steps above the diagonal. Formally we may define a Dyck path as a sequence of positive integers The work was partially supported by the Grant Agency of the Academy of Sciences of Czech Republic under grant No. KJB101210801. 1 Department of Mathematics Faculty of Electrical Engineering CZECH TECHNICAL UNIVERSITY IN PRAGUE rukavij@ . THE ELECTRONIC JOURNAL OF COMBINATORICS 18 2011 P40 1 Definition Let hn ti li t2 l2 . tm lm be a set of pairs of ordered positive integers such that tili t2l2 tmlm n and li Ij for i j. We define

• Báo cáo khoa học
• báo cáo của tạp chí Department of Mathematic
• tài liệu báo cáo nghiên cứu khoa học
• cách trình bày báo cáo
• kiến thức toán học
• báo cáo toán học