VVZ API is not affiliated with ETH Zurich. Data might be outdated or incorrect. Please view the official ETHZ Vorlesungsverzeichnis for binding information.
Generating Functions
Erzeugende Funktionen
Last Updated: 2026-02-05 14:59:54
Abstract
Lecture on generating functions. A generating function counts combinatorial objects by means of a formal power series where the coefficients are the number of objects of interest of a given size. One can then use analytic methods to explore the coefficients.We are interested in the following topics:ordinary and exponential generating functions, Lagrange inversion, Singularity analysis.
Content
Erzeugende Funktionen sind eine Methode zum Zählen kombinatorischer Objekte. Dabei wird eine formale Potenzreihe aufgestellt, deren Koeffizienten die uns interessierenden Grössen sind, die implizit gegeben sind. So kann der n-te Koeffizient zum Beispiel die Anzahl aller Permutationen von n Zahlen oder die Anzahl aller planarer Graphen auf n Knoten sein. Man kann nun die formale Potenzreihe als Funktion auffassen und analytische Methoden benutzen, um Informationen über die Koeffizienten zu erhalten. In der Vorlesung werden die grundlegenden Konzepte von (exponentiellen) Erzeugenden Funktionen ausführlich besprochen und anschliessend die Methode der Singularitätsanalyse vorgestellt, die es erlaubt, das asymptotische Wachstum der zugrundeliegenden kombinatorischen Objekte zu bestimmen.
Resources
Literature
Herbert S. Wilf, generatingfunctionology, Academic Press, 1994 Philippe Flajolet and Robert Sedgewick, Analytic Combinatorics, available on the web.
General Information
- Language
- German
- Frequency
- Yearly recurring
Examination
- Type
- session examination
- Mode
- oral 15 minutes
Course Components
| Type | Title | Time & Place | Hours |
|---|---|---|---|
| lecture | Erzeugende Funktionen |
|
2 h weekly |
| exercise | Erzeugende Funktionen |
|
1 h weekly |