Manfred Buchacher,
"Algorithms for the Enumeration of Lattice Walks"
, 11-2021
Original Titel:
Algorithms for the Enumeration of Lattice Walks
Sprache des Titels:
Englisch
Original Kurzfassung:
This thesis is about enumerative combinatorics, generating functions and functional equations and their fruitful interplay. The object of interest are functional equations that arise in the enumeration of restricted lattice walks and that are referred to as discrete differential equations. Being able to solve such functional equations, knowing whether their solutions are rational, algebraic, D-finite or D-algebraic, and having representations of them in terms of polynomial or differential equations is a first step to get information about their coefficient sequences. Building on work of Mireille Bousquet-M\'elou and Marni Mishna and others we continue the study of discrete differential equations in terms of elementary power series algebra. We introduce a class of inhomogeneous lattice walks whose generating functions are described by systems of discrete differential equations. We prove that solutions of systems of linear ordinary differential equations are algebraic and approach the study of systems of linear partial discrete differential equations. We generalize the orbit sum method to linear partial discrete differential equations of order greater than $1$, and we approach the automatization of the obstinate kernel method. We explain how useful the invariant theory of finite groups for the latter is, how it leads to the problem of finding elements in polynomial ideals whose variables are separated in a certain sense, and solve the problem for the special case of ideals of bivariate polynomial rings. Finally, we present some non-trivial examples that show that the characterization of D-finiteness and algebraicity of solutions of certain discrete differential equations in terms of the finiteness of a group and the zeroness of its orbit sum does not hold under all circumstances.
Forschungs-