tailieunhanh - Báo cáo toán học: "A Combinatorial Interpretation of the Area of Schr¨der Paths o"

Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: A Combinatorial Interpretation of the Area of Schr¨der Paths o. | A Combinatorial Interpretation of the Area of Schroder Paths E. Pergola R. Pinzani Dipartimento di Sistemi e Informatica Università di Firenze Via Lombroso 6 17 50134 Firenze Italy e-mail elisa@ pinzani@ Submitted September 3 1999 Accepted October 14 1999. Abstract An elevated Schroder path is a lattice path that uses the steps 1 1 1 1 and 2 0 that begins and ends on the x-axis and that remains strictly above the x-axis otherwise. The total area of elevated Schroder paths of length 2n 2 satisfies the recurrence fn 1 6fn fn-1 n 2 with the initial conditions f0 1 fl 7. A combinatorial interpretation of this recurrence is given by first introducing sets of unrestricted paths whose cardinality also satisfies the recurrence relation and then establishing a bijection between the set of these paths and the set of triangles constituting the total area of elevated Schroder paths. 1 Introduction In the plane Zx Z we will use lattice paths with three steps types a rise step defined by 1 1 a fall step defined by 1 1 and a horizontal step defined by 2 0 . A Schroder path is a sequence of rise fall and horizontal steps running from 0 0 to 2n 0 and remaining weakly above the x-axis. These paths are counted by the large Schroder numbers denoted by rn. The first few entries of the sequence rn n 0 are 1 2 6 22 90 394 . sequence M1659 in 14 and their generating function is P rntn 91 6t t2. For n 0 THE ELECTRONIC .JOURNAL OF COmBINATORICS 6 1999 R40 2 other combinatorial objects counted by the Schroder numbers see 2 4 5 6 10 11 12 13 . An elevated Schroder path is the path obtained from a Schroder path by adding a rise step at its beginning and a fall step at its end. In the sequel we denote S2n the class of elevated Schroder paths of length 2n. We wish to use the area under Schroder paths to consider the combinatorial signihcance of the recurrence fn 1 6fn - fn-1 n 2 1 subject to the initial conditions f0 1 f1 7. This recurrence dehnes a sequence whose hrst .