Automatic classification of lattice walks in three dimensions
Lattice walks are a classical topic in combinatorics. The principal question
is: how many possibilities are there to go from some prescribed startpoint in
some prescribed grid with some prescribed number of steps to some prescribed
endpoint. For example, on a chess board, on how many different paths can the
king move from A1 to H8 in n moves, where n is a variable.
The answer is a certain sequence of numbers and it may be of interest to find
a closed form, or a recurrence, or an asymptotic form of this sequence, or at
least some of its algebraic properties. In many cases, such questions can be
answered quickly by computer algebra. The use of computer algebra makes it
feasible to consider an enormous number of different walk types and to search
systematically for "interesting" cases. For a particular class of walks in
three dimensions, a systematic classification has been initiated in [BoKa09]. The
goal of a Masters thesis could be to continue this work. The thesis would be
co-advised by Alin Bostan from INRIA
Paris-Rocquencourt and Manuel Kauers
from RISC in Linz.
Alin Bostan and Manuel Kauers,
Automatic Classification of Restricted Lattice Walks.
FPSAC'09, Discrete Mathematics and Theoretical Computer Science, pp. 203–217, 2009.