Department of
Applied
Mathematics

Enumeration of lattice paths with forbidden patterns

Andrei Asinowski

Abstract

(joint work with A. Bacher, C. Banderier and B. Gittenberger)

A ("directed") lattice path is a word (a_1, ..., a_n) over an alphabet S, a prechosen set of integer numbers. It is visualized as a polygonal line which starts at the origin and consists of the vectors (1, a_i), i=1..n, appended to each other. In 2002, Banderier and Flajolet developed a systematic study of lattice paths by means of analytic combinatorics. In particular, they found general expressions for generating functions for several classes of lattice paths ("walks", "bridges", "meanders", and "excursions") over S.

We extend and refine the study of Banderier and Flajolet by considering lattice paths that avoid a "pattern" -- a fixed word p. In many cases we obtain expressions that generalize those from the work by Banderier and Flajolet. Our results unify and include numerous earlier results on lattice paths with forbidden patterns (for example, UDU-avoiding Dyck paths, UHD-avoiding Motzkin paths, etc.) Our main tool is a combination of finite automata machinery with a suitable extention of the kernel method.