Annals of Combinatorics 3 (1999) 265-275
Partial Difference Equation Method for Lattice Path Problems
R. Brak1, J.W. Essam2, and A.L. Owczarek1
1Department of Mathematics and Statistics, The University of Melbourne, Parkville, VIC 3052, Australia
2Department of Mathematics, Royal Holloway, University of London, Egham, Surrey TW20 0EX, England
Received November 30, 1998
AMS Subject Classification: 05A15, 82B41
Abstract. Many problems concerning lattice paths, especially on the square lattice have been exactly solved. For a single path, many methods exist that allow exact calculation regardless of whether the path inhabits a strip, a semi-infinite space or infinite space, or perhaps interacts with the walls. It has been shown that a transfer matrix method using the Bethe Ansatz allows for the calculation of the partition function for many non-intersecting paths interacting with a wall. This problem can also be considered using the Gessel--Viennot methodology. In a concurrent development, two non-intersecting paths interacting with a wall have been examined in semi-infinite space using a set of partial difference equations. Here, we review this partial difference equation method for the case of one path in a half plane. We then demonstrate that the answer for arbitrary numbers of non-intersecting paths interacting with a wall can be obtained using this method. One reason for doing this is its pedagogical value in showing its ease of use compared to the transfer matrix method. The solution is expressed in a new form as a ``constant term'' formula, which is readily evaluated. More importantly, it is the natural method that generalizes easily to many intersecting paths where there is inter-path interactions (e.g., osculating lattice paths). We discuss the relationship of the partial difference equation method to the transfer matrix method and their solution via a Bethe Ansatz.
Keywords: directed paths, interacting walks, lattice paths, difference equations, constant term, Gessel--Viennot theorem, Bethe Ansatz, transfer matrix method
1. R. Brak, Osculating lattice paths and alternating sign matrices, In: Proceedings of the ``Formal Power Series and Algebraic Combinatorics'' Conference, University of Vienna, Vienna, 1997.
2. R. Brak, J. Essam, and A.L. Owczarek, Exact solution of N directed non-intersecting walks interacting with one or two boundaries, J. Phys. A 32 (1999) 2921–2929.
3. R. Brak, J. Essam, and A.L. Owczarek, From the Bethe Ansatz to the Gessel-Viennot theorem, Ann. Combin. 3 (1999) 251–263.
4. R. Brak, J. Essam, and A.L. Owczarek, New results for directed vesicles and chains near an attractive wall, J. Stat. Phys. 93 (1998) 155–192.
5. M.E. Fisher, Walks, walls, wetting and melting, J. Stat. Phys. 34 (1984) 667–729.
6. P.J. Forrester, Probability of survival for vicious walkers near a cliff, J. Phys. A 22 (1989) L609–L613.
7. I.M. Gessel and X. Viennot, Determinants, paths, and plane partitions, 1989, preprint.
8. I.M. Gessel and X. Viennot, Binomial determinants, paths, and hook length formulae, Adv. Math. 58} (1985) 300–321.
9. A.J. Guttmann, A.L. Owczarek, and X.G. Viennot, Vicious walkers and young tableaux I: Without walls, J. Phys. A 31 (1998) 8123–8135.
10. E.H. Lieb, Residual entropy of square ice,Phys. Rev. 162 (1967) 162–172.
11. F.Y. Wu, Remarks on the modified potassium dihydrogen phosphate model of a ferroelectric, Phys. Rev. 168 (1968) 539–543.