Zur Seitenansicht


Restricted Lattice Paths and Their Generating Functions / submitted by Rika Yatchak
VerfasserYatchak, Rika
Begutachter / BegutachterinKauers, Manuel ; Gittenberger, Bernhard
GutachterKauers, Manuel
ErschienenLinz, 2017
Umfangviii, 100 Seiten : Illustrationen
HochschulschriftUniversität Linz, Dissertation, 2017
Schlagwörter (EN)combinatorics / algorithmic combinatorics / symbolic computation
Schlagwörter (GND)Gitterpfad / Erzeugende Funktion / Computeralgebra
URNurn:nbn:at:at-ubl:1-17492 Persistent Identifier (URN)
 Das Werk ist gemäß den "Hinweisen für BenützerInnen" verfügbar
Restricted Lattice Paths and Their Generating Functions [1.06 mb]
Zusammenfassung (Englisch)

A multivariate power series F (x, y, z, t) is called D-finite if it satisfies a linear differential equation with polynomial coefficients with respect to each of its variables. Such power series are comparatively well-behaved, and the behavior of their asymptotics is well known.

We study the generating functions of walks with small steps in the positive octant: steps can have -1, 0, or 1 in their coordinates, and they are confined to the lattice (Z0 ) 3 . For each stepset, we form an associated multivariate generating function F (x, y, z, t) and ask: is F D-finite?

We continue the classification of positive octant walks with small steps whose generating functions are D-finite. In particular, building on previous results of Bousquet-Mélou, Bostan, Kauers, and Melczer, we show that all three-dimensional positive octant walks with finite associated group and nonzero orbit sum have D-finite generating functions. We automate the orbit sum proof technique using the theory of multivariate formal Laurent series. For the collection of mysterious positive octant walks for which no known method can prove (or disprove) D-finite character, we provide computationally guessed asymptotics, including some results which suggest that at least some positive octant walks with finite group do not have D-finite generating functions.

We also identify families of all positive quadrant walks with multiplicities having group of order 4, 6, or 8, and prove that all such walks have D-finite generating functions. Using these families, we provide D-finiteness proofs for certain two-dimensional positive octant walks. We also prove that some two-dimensional positive octant walks have non-D-finite generating functions.