tailieunhanh - Báo cáo toán học: "Generalizing Narayana and Schr¨der Numbers o to Higher Dimensions"

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: Generalizing Narayana and Schr¨der Numbers o to Higher Dimensions. | Generalizing Narayana and Schroder Numbers to Higher Dimensions Robert A. Sulanke Boise State University Boise Idaho USA sulanke@ Submitted Dec 29 2003 Accepted May 15 2004 Published Aug 23 2004 Abstract Let C d n denote the set of d-dimensional lattice paths using the steps X 1 0 . 0 X2 0 1 . 0 . Xd 0 0 . 1 running from 0 0 . 0 to n n . n and lying in x1 x2 . xd 0 X1 x2 . xd . On any path P p1p2 . .pdn G C d n define the statistics asc P PiPi 1 XjXf j t and des P PiPi 1 XjX j t . Define the generalized Narayana number N d n k to count the paths in C d n with asc P k. We consider the derivation of a formula for N d n k implicit in MacMahon s work. We examine other statistics for N d n k and show that the statistics asc and des d 1 are equidistributed. We use Wegschaider s algorithm extending Sister Celine s Wilf-Zeilberger method to multiple summation to obtain recurrences for N 3 n k . We introduce the generalized large Schroder numbers 2d 1 fik N d n k 2k n 1 to count constrained paths using step sets which include diagonal steps. Key phases Lattice paths Catalan numbers Narayana numbers Schroder numbers Sister Celine s Wilf-Zeilberger method Mathematics Subject Classification 05A15 1 Introduction In d-dimensional coordinate space consider lattice paths that use the unit steps X1 1 0 . 0 X 0 1 . 0 . Xd 0 0 . 1 . Let C d n denote the set of lattice paths running from 0 0 . 0 to n n . n and lying in the region x1 x2 . xd 0 x1 x2 . xd . On any path P P1P2 . .pdn we call any step pair PiPi 1 an ascent respectively a descent if PiPi 1 XjX THE ELECTRONIC JOURNAL OF COMBINATORICS 11 2004 R54 1 P e C 3 2 asc P des P hdes P ZZYYXX 0 2 2 ZZYXYX 1 3 1 ZYZYXX 1 3 1 ZYZXYX 2 3 1 ZYXZYX 1 4 0 Table 1 For d 3 and n 2. hdes P appears in . for j I respectively for j . See Remark . To denote the statistics for the number of ascents and the number of descents we put asc P PiPi 1 XjXe for j k des P PiPi 1 XjX for j . For convenience when d 3 put X X1 Y X2 .