Analytic Combinatorics and Bijections for Directed Lattice Paths

Abstract

Die zentralen mathematischen Objekte in der Analyse von Gitternetzpfaden sind die erzeugenden Funktionen. Wir führen sie zunächst als formale Potenzreihen ein, deren algebraische Struktur unmittelbar die Struktur der zugrundeliegenden kombinatorischen Klassen widerspiegelt. Der logische erste Schritt zur Analyse einer beliebigen Familie von Gitternetzpfaden liegt in der Herleitung ihrer erzeugenden Funktion. Nach der Identifizierung einer formalen Spezifikation dieser Familie, in Form grundlegender mengentheoretischer Konstruktionen, liefert die sogenannte symbolische Methode eine Funktionalgleichung für die erzeugende Funktion. Darauf aufbauend, liefert uns schließlich die sogenannte „kernel method“ ein leistungsfähiges Werkzeug zur Lösung solcher, oftmals scheinbar unterbestimmten, Gleichungen. Sobald wir die erzeugende Funktion endlich in der Hand haben, schreiten wir in drei mögliche Richtungen voran. Erstens ist es in einfachen Fällen möglich, durch eine Kombination von Newtons verallgemeinertem binomischem Lehrsatz mit der Lagrangeschen Inversionsformel, eine geschlossene Formel für die entsprechende Zählsequenz zu erhalten. Zweitens gewährt eine Untersuchung der Lage und des Typs der dominanten Singularitäten der erzeugenden Funktion tiefe Einblicke in die asymptotischen Wachstumsraten ihrer Koeffizienten, selbst wenn eine geschlossene Formel nicht mehr in Reichweite ist. Schließlich verwenden wir die erzeugenden Funktionen, um mit Hilfe der On-Line Encyclopedia of Integer Sequences (OEIS) Verbindungen zu verwandten kombinatorischen Strukturen zu entdecken, welche dieselbe Zählsequenz aufweisen. Die Gleichheit dieser Sequenzen garantiert zwar die Existenz eines kombinatorischen Isomorphismus, allerdings ist die tatsächliche Konstruktion einer solchen Bijektion oft alles andere als offensichtlich.

The central mathematical objects of lattice path combinatorics are generating functions. Initially, we introduce them as formal power series, whose algebraic structure directly reflects the structure of combinatorial classes. Hence, the logical first step for analyzing any family of lattice paths lies in the derivation of its generating function. After identifying a formal specification of this family in terms of basic set-theoretic constructions, the symbolic method provides us with a functional equation satisfied by our generating function. Next, the so-called kernel method serves as a powerful tool to solve this often seemingly underdetermined functional equation. Once the generating function has been derived, we may continue in three possible directions. Firstly, in simple cases, it is possible to obtain a closed-form expression for the corresponding counting sequence via a combination of Newton’s generalized binomial theorem and Lagrange’s inversion formula. Secondly, an investigation into the nature and location of the complex singularities of the generating function provides vital insights into the asymptotic growth rates of their coefficients, even if a closed-form formula is no longer feasible. Finally, we use the generating functions in conjunction with the On-Line Encyclopedia of Integer Sequences (OEIS) to discover connections to related combinatorial structures and construct explicit bijections between them. While the equality of the counting sequences guarantees the existence of such a function, the actual construction is often far from obvious.