TAILIEUCHUNG - Báo cáo toán học: "General results on the enumeration of strings in 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: General results on the enumeration of strings in Dyck paths. | General results on the enumeration of strings in Dyck paths K. Manes A. Sapounakis I. Tasoulas and P. Tsikouras Department of Informatics University of Piraeus Piraeus Greece kmanes arissap jtas pgtsik @ Submitted Dec 18 2010 Accepted Mar 23 2011 Published Mar 2011 Mathematics Subject Classifications 05A15 05A19 Abstract Let T be a fixed lattice path called in this context string on the integer plane consisting of two kinds of steps. The Dyck path statistic number of occurrences of T has been studied by many authors for particular strings only. In this paper arbitrary strings are considered. The associated generating function is evaluated when T is a Dyck prefix or a Dyck suffix . Furthermore the case when T is neither a Dyck prefix nor a Dyck suffix is considered giving some partial results. Finally the statistic number of occurrences of T at height at least j is considered evaluating the corresponding generating function when T is either a Dyck prefix or a Dyck suffix. 1 Introduction Throughout this paper a path is considered to be a lattice path on the integer plane consisting of steps u 1 1 called rises and d 1 1 called falls . Since the sequence of steps of a path is encoded by a word in u d we will make no distinction between these two notions. The length a of a path a is the number of its steps. The height of a point of a path is its y-coordinate. A Dyck path is a path that starts and ends at the same height and lies weakly above this height. It is convenient to consider that the starting point of a Dyck path is the origin of a pair of axes see Fig. 1 . The set of Dyck paths of semilength n is denoted by Dn and we set D un 0 Dn where D0 e and E is the empty path. It is well known that Dn Cn where Cn n 1 2n is the n-th Catalan number see sequence A000108 in 23 . Every non-empty Dyck path a can be uniquely decomposed in the form a u dy where d 7 6 D. This is the so called first return decomposition. If Y E then a is a prime Dyck path. THE ELECTRONIC .

• 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