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í toán học quốc tế đề tài: Enumerating Up-Side Self-Avoiding Walks on Integer Lattices. | Enumerating Up-Side Self-Avoiding Walks on Integer Lattices Lauren K Williams Harvard University Cambridge MA 02138 lkwill@ .edu Submitted September 4 1996 Accepted September 26 1996. Abstract A self-avoiding walk saw is a path on a lattice that does not pass through the same point twice. Though mathematicians have studied saws for over fifty years the number of n-step saws is unknown. This paper examines a special case of this problem finding the number of n-step up-side saws ussaws saws restricted to moving up and sideways. It presents formulas for the number of n-step ussaws on various lattices found using generating functions with decomposition and recursive methods. 1 Introduction A self-avoiding walk saw is a path on a lattice that does not cross the same point twice on the two-dimensional lattice it is a finite sequence of distinct lattice points xo yo 0 0 x1 y1 xniyn such that for all i xi yi and xi 1 yi 1 are separated by a unit distance. Saws although easy to describe pose a number of interesting unsolved problems. In particular the number of n-step saws is unknown. I began my study of the number of n-step saws at the 1994 Research Science Institute by reviewing a paper by Doron Zeil-berger a professor of math at Temple University. He described his approach studying n-step saws on lattices of restricted width 4 as follows When a problem seems intractable it is often a good idea to study toy versions of it in the hope that as the toys become increasingly larger . they would metamorphose in the limit to the real thing. My analysis also considers a restricted version of the problem A Self Avoiding Walk of counting saws - counting up-side saws ussaws saws that move up and sideways but not down on various lattices. I utilize two methods an extension of Zeilberger s decomposition method and a recursive method. Generating functions gf s are a primary tool of these methods. According to Wilf 3 a generating function is a clothesline on which we hang .
