Wallner, M. (2016). Combinatorics of lattice paths and tree-like structures [Dissertation, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2016.38100
This thesis is concerned with the enumerative and asymptotic analysis of directed lattice paths and tree-like structures. We introduce several new models and analyze some of their characterizing parameters, such as the number of returns to zero, or their average height and final altitude. The key tool in this context is the concept of generating functions. Their algebraic and analytic properties will help us to solve the enumeration problems. The methods and many other helpful theorems will be presented in the first part. Due to these methods this thesis belongs to the field of analytic combinatorics. The second part is dedicated to the study of directed lattice paths. Its first chapter treats the half-normal distribution, and presents a scheme for generating functions leading to such a distribution. We also state applications of this result in the theory of lattice paths. The next chapter continues the work of Cyril Banderier and Philippe Flajolet, and extends their work to the case when a boundary reflecting or absorbing condition is added to the classical models. The subsequent chapter then deals with a different family of paths: lattice paths below a line of rational slope. This work deals with the delicate problem of deriving asymptotic results for generating functions with a periodic support. It also answers an open problem by Donald E. Knuth on the asymptotics of such paths. The final chapter of this part deals with another model: lattice paths with catastrophes, which are jumps from any altitude to the x-axis. The third part treats the analysis of trees and tree-like structures. In the initial chapter we treat Pólya trees, which are unlabeled rooted trees. We present a new interpretation as Galton-Watson trees with many small forests. In the subsequent chapter we solve the counting problem of compacted trees of bounded right-height. Most trees contain redundant information in form of repeated occurrences of the same subtree. These trees can be compacted by representing each occurrence only once. The positions of the removed subtrees will be remembered by pointers which point to the common subtree. Such structures are known as directed acyclic graphs. The fourth and final part treats applications of analytic combinatorics to number theory. We study the exact divisibility of binomial coefficients by powers of primes by means of generating functions and singularity analysis.
en
Die vorliegende Dissertation beschäftigt sich mit der analytischen und enumerativen Analyse von gerichteten Gitterwegen und baumartigen Strukturen. Es werden verschiedene, neue Modelle vorgestellt und einige ihrer charakterisierenden Parameter, wie unter anderem die Anzahl der Berührungen der x-Achse, oder ihre durchschnittliche und finale Höhe, untersucht. Das wichtigste Werkzeug in diesem Kontext sind erzeugende Funktionen. Die vorliegenden Ergebnisse beruhen zum Großteil auf ihren algebraischen und analytischen Eigenschaften, wie ihrer Singularitätsstruktur. Aus diesem Grund ist die vorliegende Arbeit dem Feld der analytischen Kombinatorik zuzuordnen. Eine Einführung in dieses Gebiet wird im ersten Teil dieser Arbeit gegeben. Der zweite Teil behandelt das Thema der gerichteten Gitterwege. Sein erstes Kapitel ist der Halbnormalverteilung gewidmet. Es wird eine neue Methode zur Charakterisierung von bivariaten erzeugenden Funktionen, in denen ein Parameter markiert wurde, der dieser Grenzverteilung gehorcht, präsentiert. Am Ende werden natürliche Vorkommen dieser Situation vorgestellt. Das folgende Kapitel löst ein offenes Problem von Donald E. Knuth über die Asymptotik von Wegen unter einer Geraden mit rationaler Steigung. Die Lösung benötigt die Behandlung von periodischen Trägern von erzeugenden Funktionen, welche zu periodischen Singularitätsstrukturen führen. Das anschließende Kapitel präsentiert aufbauend auf der Arbeit von Cyril Banderier und Philippe Flajolet ein neues Modell: das "reflection-absorption model". Dieses erlaubt die Modellierung einer reflektierenden oder absorbierenden Randbedingung. Das letzte Kapitel dieses Teils behandelt ein weiteres neues Modell für Gitterwege, in dem "Katastrophen" eingeführt werden. Dies sind Sprünge von beliebiger Höhe zur x-Achse. Der dritte Teil handelt von Bäumen und baumartigen Strukturen. Zunächst wird eine neue Interpretation von Pólya Bäumen (unmarkierten Wurzelbäumen) vorgestellt, welche diese als Galton-Watson Bäume charakterisiert, an die viele kleine Wälder angehängt werden. Im darauffolgenden Kapitel wird die Kompaktifizierung von binären Bäumen behandelt. Dies führt zu baumartigen Strukturen, den sogenannten "directed acyclic graphs". Ein kompaktifizierter Baum ist ein Baum in dem jeder Teilbaum eindeutig ist und mehrfach auftretende Teilbäume durch Zeiger ersetzt wurden. Durch die Modellierung solcher Objekte mittels exponentiell erzeugender Funktionen wird das asymptotische Abzählproblem für kompaktifizierte Bäume mit beschränkter rechtsseitiger Höhe gelöst. Im vierten und letzten Teil wird ein neuer Themenschwerpunkt behandelt: Die Anwendung der analytischen Kombinatorik in der Zahlentheorie. Hier wird die exakte Teilbarkeit von Binomialkoeffizienten durch Potenzen von Primzahlen untersucht.