tailieunhanh - Báo cáo toán học: " The Number of [Old-Time] Basketball Games with Final Score n:n where the Home Team was never losing but also never ahead by more than w Point"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: The Number of [Old-Time] Basketball Games with Final Score n:n where the Home Team was never losing but also never ahead by more than w Points. | The Number of Old-Time Basketball Games with Final Score n n where the Home Team was never losing but also never ahead by more than w Points Arvind Ayyer Department of Physics 136 Frelinghuysen Rd Piscataway NJ 08854. ayyer@ Doron Zeilberger Department of Mathematics 110 Frelinghuysen Rd Piscataway NJ 08854. zeilberg@ Submitted Oct 24 2006 Accepted Dec 15 2006 Published Jan 29 2007 Mathematics Subject Classification 05A15 Abstract We show that the generating function in n for the number of walks on the square lattice with steps 1 1 1 1 2 2 and 2 2 from 0 0 to 2n 0 in the region 0 y w satisfies a very special fifth order nonlinear recurrence relation in w that implies both its numerator and denominator satisfy a linear recurrence relation. 1 Introduction We consider walks in the two-dimensional square lattice with steps 1 1 1 -1 2 2 and 2 -2 . We assign a weight pz for a unit distance along the x-axis. We constrain them to lie in the region defined by y 0 and y w. The motivation for considering such walks is the modelling of polymers forced to lie between plates separated by a small distance. One would then like to calculate various combinatorial quantities. In principle one hopes to count all possible configurations of the polymer modelling it as a self-avoiding THE ELECTRONIC JOURNAL OF COMBINATORICS 14 2007 R19 1 walk WSCM MTW . Since this is a tough nut to crack one simplifying approach is to treat the polymer as a directed walk. Studies of this kind have been done in the literature with simpler steps such as Dyck paths 1 1 and 1 1 which we review in the next section. See for example DR BORW . For further developments on the subject see R and the references therein. Even though the motivation came from Physics BORW it later occured to us that this is the number of basketball games post-1896 and pre-1961 when the three-pointer did not exist in which the home team always leads the visitor by at most w points ending in a tie 2 .