Titelaufnahme

Titel
Applications of the Kernel method / von Michael Kammer
VerfasserKammer, Michael
Begutachter / BegutachterinPanholzer, Alois
Erschienen2011
UmfangIV, 95 Bl. : graph. Darst.
HochschulschriftWien, Techn. Univ., Dipl.-Arb., 2011
Anmerkung
Zsfassung in dt. Sprache
SpracheEnglisch
DokumenttypDiplomarbeit
Schlagwörter (DE)Kernel / Abzählformeln / Rekursionen / Erzeugende Funktionen / Gitterpfade / Permutationen / Mustervermeidung / Parking Funktionen
Schlagwörter (EN)Kernel / enumeration formulae / recursions / generating functions / lattice paths / permutations / pattern avoidance / parking functions
URNurn:nbn:at:at-ubtuw:1-59291 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Applications of the Kernel method [0.93 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

Rekursive Gleichungen finden oftmals Anwendung in vielen verschiedenen Gebieten der Mathematik. Eine Lösung solcher Gleichungen, das heißt eine geschlossene Formel zur Berechnung der durch die Rekursion definierten Zahlen, kann mithilfe einer erzeugenden Funktion gefunden werden. Hierbei werden die Zahlen als Koeffizienten einer formalen Potenzreihe F kodiert. Eine Funktionalgleichung, welche diese implizit definiert, kann aus der Rekursion gewonnen werden. Es ist jedoch häufig sehr schwierig, daraus eine explizite Darstellung der Funktion zu finden. Im speziellen Fall, dass die Gleichung eine Linearkombination von F und einiger sehr ähnlichen Funktionen darstellt, bietet die Kernelmethode ein einfaches Mittel, die erzeugende Funktion zu berechnen. Es werden dabei Kombinationen von Variablen gefunden, sodass der Nenner, der sogenannte Kernel, der erzeugenden Funktion verschwindet. Aufgrund des kombinatorischen Kontextes folgt, dass F eine formale Potenzreihenentwicklung besitzen muss. Daher ergeben sich zusätzliche Gleichungen für die betrachteten Objekte, welche im Wesentlichen der erzeugenden Funktion, ausgewertet mit speziellen Argumenten, entsprechen. Aus diesen kann eine allgemeine Formel für die Funktion und damit die Lösung der Rekursion erhalten werden.

Die Kernelmethode, welche in den letzten Jahren zunehmend Popularität gewann, gehört seit den 1970er Jahren zur mathematischen Folklore und wurde vermutlich von verschiedenen Autoren immer wieder neu entdeckt. In dieser Diplomarbeit, inspiriert von Prodingers ,,A collection of examples'' (2004), werden wir eine dieser Arbeiten von Knuth (1968) präsentieren, sowie die Nützlichkeit der Methode in komplexeren Beispielen aufzeigen. Wir werden diese in allen Details vorstellen, die nötigen Theoreme und Begriffe für das Verständnis der Theorie hinter der Kernelmethode besprechen und die Grenzen der Methode kennen lernen.

Zusammenfassung (Englisch)

Recursions occur frequently throughout various areas of mathematics. To obtain a solution, that is a closed formula for the numbers defined by the recursive equation, one may apply the generating function approach. This involves encoding these numbers as coefficients of a formal power series F. A functional equation which implicitly defines this function may be derived from the recursion, however, it might be difficult to find an explicit expression for the solution of the resulting equation. For certain cases, namely if the functional equation consists of a linear combination of F and a number of functions closely related to it, the Kernel method provides a simple way to actually compute it. One finds couplings of variables such that the numerator of the generating function, called the Kernel, vanishes.

Considering the combinatorial context and hence that F must have a formal power series expansion, this yields additional equations for the involved entities, which are essentially the generating function evaluated with special arguments. From this, an expression for the generating function in general and subsequently the solution of the recursion may be obtained.

The Kernel method, gaining popularity in the recent years, belongs to mathematical folklore since the 1970's and was most likely discovered several times by different authors. In this thesis, inspired by Prodinger's "A collection of examples" (2004), we will present one of those instances as given by Knuth (1968). Furthermore, we will demonstrate the usefulness of the method in more sophisticated examples.

We will study these in full detail, discuss the necessary theorems and notions to understand the theoretical depth behind the Kernel method and encounter some of its limitations.