In dieser Vorlesung werden beschriftete Objekte vorgestellt, bei denen die Atome, die wir zum Aufbau von Objekten verwenden, unterscheidbar sind. Wir verwenden exponentiell erzeugende Funktionen EGFs, um kombinatorische Klassen zu untersuchen, die aus markierten Objekten aufgebaut sind. Wie in Vorlesung 1 definieren wir kombinatorische Konstruktionen, die zu EGF-Gleichungen führen, und betrachten zahlreiche Beispiele aus der klassischen Kombinatorik.

Dieser Vortrag beschreibt den Prozess des Hinzufügens von Variablen zur Markierung von Parametern und der anschließenden Verwendung der Konstruktionen aus den Vorlesungen 1 und 2 sowie der natürlichen Erweiterungen der Transfertheoreme zur Definition multivariater GFs, die Informationen über Parameter enthalten. Wir konzentrieren uns auf bivariate generierende Funktionen (BGFs), bei denen eine Variable die Größe eines Objekts und die andere den Wert eines Parameters markiert. Nachdem wir untersucht haben, wie man den Mittelwert, die Standardabweichung und andere Momente aus BGFs berechnen kann, betrachten wir einige Beispiele im Detail.

In dieser Woche stellen wir die Idee vor, erzeugende Funktionen als analytische Objekte zu betrachten, was uns zu asymptotischen Schätzungen von Koeffizienten führt. Der Ansatz ist am fruchtbarsten, wenn wir GFs als komplexe Funktionen betrachten. Daher führen wir grundlegende Konzepte der komplexen Analyse ein und wenden sie an. Wir gehen von grundlegenden Prinzipien aus, so dass Vorkenntnisse in komplexer Analysis nicht erforderlich sind.

Wir betrachten Anwendungen des allgemeinen Transfertheorems aus der vorherigen Vorlesung auf viele der klassischen kombinatorischen Klassen, die wir in den Vorlesungen 1 und 2 kennengelernt haben. Dann betrachten wir ein universelles Gesetz, das Asymptotik für eine breite Palette von kombinatorischen Klassen liefert, die mit der Sequenzkonstruktion aufgebaut wurden.

Diese Vorlesung befasst sich mit dem grundlegenden Flajolet-Odlyzko-Theorem, bei dem wir den Bereich der Analytizität der Funktion in der Nähe ihrer dominanten Singularität finden, mit Hilfe von Funktionen aus der Standardskala approximieren und dann Term für Term zur Koeffizientenasymptotik übergehen.

Wir sehen, wie der Flajolet-Odlyzko-Ansatz zu universellen Gesetzen führt, die kombinatorische Klassen abdecken, die mit den Konstruktionen für Mengen, Multisets und rekursive Sequenzen erstellt wurden. Dann betrachten wir Anwendungen auf viele der klassischen kombinatorischen Klassen, die wir in den Vorlesungen 1 und 2 kennengelernt haben.

Wir betrachten die Sattelpunktmethode, eine allgemeine Technik zur Konturintegration, die auch einen effektiven Weg zur Entwicklung der Koeffizientenasymptotik für GFs ohne Singularitäten bietet. Wie üblich betrachten wir die Anwendung dieser Methode auf einige der in den Vorlesungen 1 und 2 vorgestellten klassischen Probleme.