Linear operators and functionals are tools for lattice paths enumeration
by
Heinrich Niederhausen
Florida Atlantic University

A simple lattice path begins at the origin, takes steps ái, j ñ Î S, the step set, from point (n, m) to (n+i, m+j), and cannot intersect itself. The step set S however, may be infinite and the steps may be weighted. Furthermore, the path can be restricted by boundaries. We only consider one boundary, a straight line of positive integer slope. The boundary can be reached from points above it by steps from a special access step set. The special access set may or may not be a subset of the general step set, and it can be infinite as well. If it is empty, the lattice paths are restricted to points above the boundary. We enumerate the paths with the help of linear algebra; if the number of paths from the origin to (n, m) above the boundary is the value p_n(m) of a polynomial of degree n, then the path recursion, given by the step set, defines a relationship between linear operators on polynomials, and the special access condition defines a linear functional on polynomials. Applying Rota's Finite Operator Calculus we determine the solution, the Sheffer sequence (p_n), from the problem specific operator equation and functional condition. Depending on the two step sets, the generating function of a solution will be rational or not. We will give examples of the latter case.

Date received: March 29, 2005