Exact solution of two classes of prudent polygons
by Uwe Schwerdtfeger
Abstract: A prudent walk is a walk on the square lattice consisting of
nearest neighbour steps, such that in the course the walker never steps
towards an occupied vertex, no matter at what distance. In particular,
such a walk is self-avoiding.
Three subclasses of such walks, called one-, two- and three-sided
prudent walks, have been solved so far. The first class has a rational
generating function. The second was shown to have an algebraic
generating function by E. Ducci in 2005. Recently, Mireille
Bousquet-Melou solved these two classes and the third, whose
generating function turns out to be non-holonomic.
In this talk we study polygon versions of the two- and three-sided
walks, meaning walks ending at a vertex adjacent to their starting
point. Similar to the walk cases, we find an algebraic generating
function for the former and a non-holonomic one for the latter class.
For More Information: Contact: Iwan Jensen I.Jensen@ms.unimelb.edu.au