UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

Multidimensional lattice walk enumeration through coefficient extraction operators Vlasev, Aleksandar

Abstract

In this thesis, we investigate the enumeration of lattice walk models, with or without interactions, in multiple dimensions, through the use of linear operators comprised of coefficient or term extractions. This is done with the goal of furthering our abilities to automate the derivation and solutions of the functional equations for the generating functions for the models. In particular, for a fairly large class of d-dimensional lattice walk models with interactions and arbitrary step sets, the generating function Q satisfies the functional equation (1 - tΓS)Q = q, where Γ is an operator, and S and q are Laurent polynomials. We can automatically expand this equation to obtain an explicit functional equation satisfied by Q. For example, we derive an equation for d-dimensional lattice walks with interactions and small steps living in an orthant. We also use this operator approach to unify and extend the algebraic and obstinate kernel methods through the use of a weighted orbit summation operator and substitutions. Other topics include: a partial classification of two-dimensional models with interactions and small steps on the quarter plane, explicit relations for Q and partially-interacting versions of itself for some models, and an analysis of some of the more abstract properties of the operators involved.

Item Citations and Data

Rights

Attribution-NonCommercial-NoDerivs 2.5 Canada