tailieunhanh - Báo cáo toán học: "Bijective Recurrences concerning Schr¨der paths o Robert A. Sulanke Boise State University Boise, Idaho, USA"

Tuyển tập các báo cáo nghiên cứu khoa học hay nhất của tạp chí toán học quốc tế đề tài: Bijective Recurrences concerning Schr¨der paths o Robert A. Sulanke Boise State University Boise, Idaho, USA. | Bijective Recurrences concerning Schroder paths Robert A. Sulanke Boise State University Boise Idaho USA sulanke@ Submitted April 7 1998 Accepted October 30 1998 Abstract Consider lattice paths in Z2 with three step types the up diagonal 1 1 the down diagonal 1 -1 and the double horizontal 2 0 . For n 1 let Sn denote the set of such paths running from 0 0 to 2n 0 and remaining strictly above the x-axis except initially and terminally. It is well known that the cardinalities rn Sn are the large Schroder numbers. We use lattice paths to interpret bijectively the recurrence n 1 rn 1 3 2n 1 rn n 2 rn-1 for n 2 with r1 1 and r2 2. We then use the bijective scheme to prove a result of Kreweras that the sum of the areas of the regions lying under the paths of Sn and above the x-axis denoted by ASn satisfies ASn 1 6ASn ASn-1 for n 2 with AS1 1 and AS2 7. Hence ASn 1 7 41 239 1393 . The bijective scheme yields analogous recurrences for elevated Catalan paths. Mathematical Reviews Subject Classification 05A15 1 The paths and the recurrences We will consider lattice paths in Z2 whose permitted step types are the up diagonal 1 1 denoted by U the down diagonal 1 1 denoted by D and the double horizontal 2 0 denoted by H. We will focus on paths that run from 0 0 to 2n 0 for n 1 and that never touch or pass below the x-axis except initially and terminally. Let Cn denote the set of such paths when only U-steps and D-steps are allowed and let Sn denote the set of such paths when all three types are allowed. It is well known that the cardinalities cn Cn and rn Sn for n 1 are the Catalan numbers and the large Schroder numbers respectively. See Section 4 particularly Notes 2 and 4. Hence here one might view the elements of Sn as elevated Schroder paths. Let ACn denote the sum of the areas of the regions lying under the paths of Cn and 1 THE ELECTRONIC .JOURNAL OF COmBINATORICS 47 1998 R47 2 above the x-axis. Likewise let ASn denote the sum of the areas of the regions .