Two Dimensional Directed Lattice Walks with Boundaries

By Arvind Ayyer and Doron Zeilberger

.pdf   .ps  
[Appeared in "Tapas in Experimental Mathematics", Contemporary Mathematics, v. 457 (2008), 1-20, (Tewodros Amdeberhan and Victor Moll, eds.)].
Written: Jan. 29, 2007.

In How many ways can you walk in the discrete plane, with arbitrary set of steps and interact with a boundary? These questions are of interest in statistical mechanics, but for general sets of steps is beyond the scope of mere humans. But, once the algorithms in this paper are taught to a computer, using Maple (or any other computer algebra system), it can do amazing symbol-crunching that gives exact and rigorous results, that in turn, can be used to derive exact numerics, more efficiently and much more accurately, than simulation.

Important: This article is accompanied by Maple package POLYMER (written by Arvind Ayyer, with some minimal guidance by Doron Zeilberger) that automatically computes generating functions and other quantities of interest regarding two dimensional directed lattice walks with boundaries.
Added Feb. 28, 2007: Philippe Duchon (LaBRI, Universite Bordeaux 1) has kindly pointed out that the results about the "unbounded case" were already discovered by him in his article: "On the enumeration and generation of generalyzed Dyck words", Discrete Mathematics vol. 225 (2000).

Added March, 2007: In this revised version write a revised version we referenced Duchon's work appropriately.

Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page