Solving Discrete Initial- and Boundary-Value Problems

Multivariate linear recurrences appear in such diverse fields of mathematics as combinatorics, probability theory, and numerical solution of partial differential equations. Whereas in the univariate case the solution of a constant-coefficient recurrence always has a rational generating function, this is no longer true in the multivariate case where this generating function can be non-rational, non-algebraic, and even non-D-finite. However, there are some important cases where the solution can nevertheless be computed exactly in terms of algebraic functions. Examples include many lattice-path problems such as enumeration of Dyck, Motzkin, and Schroeder paths, determining the cardinality of various free algebras, and (in some cases) enumeration of permutations avoiding some forbidden pattern.

This is joint work with Mireille Bousquet-Mélou (CNRS, Univ. Bordeaux I).