WS2021: Proseminar „Erzeugende Funktionen“

Hier ensteht eine Web-Seite zum Proseminar „Erzeugende Funktionen“, das ich im WS2021 anbieten werde. Im Moment ist noch unklar, ob die Vorlesung als Präsenzveranstaltung oder online stattfinden wird. Wir bitten bis zur Klärung um Geduld!

Vorträge

Das Seminar orientiert an dem Buch [Wil90].

  1. Formale Potenzreihen
    Ziel des Vortrags ist es, die theoretischen Grundlagen für das Rechnen mit Potenzreihen zu vermitteln. Dazu definieren wir den Ring der formalen Potenzreihen und lernen darin Kehrwerte und Inverse (unter bestimmten Voraussetzungen) zu berechnen, sowie formales Ableiten. Zudem sollte das allgemeine Vorgehen („The Method“)
    vorgestellt und anhand erster Beispiele vorgestellt werden.
    Literatur: [Wil90, §§2.1, 1.1–1.2].
  2. Potenzreihen und Konvergenz
    Zunächst soll untersucht werden, was für Auswikungen eine Veränderung der Folge auf die zugehörige Reihe hat (Stichworte: „Shifting“ und Ableitung). Dann wollen wir uns kurz mit dem Problem befassen, dass wir auf Konvergenz achten müssen, sobald wir unsere Potenzreihen auswerten wollen. Dazu sollten die Konvergenzkriterien (knapp!)
    wiederholt werden. Als Beispiel wird die Fibonacci-Folge behandelt.
    Literatur: [Wil90, §§2.2, 2.4, 1.3].
  3. Exponentielle Erzeugendenfunktionen
    Als spezielle Klasse von erzeugenden Funktionen lernen wir Exponentielle Erzeugendenfunktionen kennen. Zu diesen sollten Beispiele vorgeführt werden. Außerdem sollen in diesem Vortrag die Catalan-Zahlen vorgestellt werden. Bei diesen sollte auf verschiedene Interpretationen und Anwendungen eingegangen werden.
    Literatur: [Wil90, §2.3] + evtl. zusätzliche Quellen für Catalan-Zahlen.
  4. Zählprobleme I
    Zunächst sollte an die Definition von Graphen erinnert werden. Daraus ergeben sich sofort eine Vielzahl von Zählproblemen. Um diese fassen zu können und eine allgemeine Theorie zu entwickeln, soll die Notation von „Decks“, „Cards“ und „Hands“ eingeführt, sowie an Beispielen erläutert werden. Insbesondere kann man auf diese Art auch Permutationen zählen, an deren Definition zuvor kurz erinnert werden sollte (Absprache mit Zählprobleme II!).
    Literatur: [Wil90, §§3.1–3.3].
  5. Zählprobleme II
    Die vorgestellten Zählprobleme können nun mit Hilfe einer allgemeinen Methode bewältigt werden. Diese soll zunächst vorgestellt und danach ein recht konkreter Zählsatz, der Lösungen für die Zählprobleme liefert, bewiesen werden (Stichworte: „Trickle“, „Flow“ und „Flood“). Als Anwendungsbeispiel sollten danach noch einmal Permutationen gezählt werden.
    Literatur: [Wil90, §§3.4–3.5, §3.3 Example 2].
  6. Zählprobleme III
    Als weiteres Beispiel sollen Partitionen gezählt werden. Das führt uns zu den Stirling-Zahlen, die viele interessante Eigenschaften aufweisen.
    Literatur: [Wil90, §1.6, §§3.6–3.8].
  7. Zählprobleme IV
    In diesem Vortrag kehren wir zu Graphen zurück. Auch hier wird der Zählsatz verwendet, um eine Reihe von Zählproblemen zu lösen.
    Literatur: [Wil90, §§3.9–3.12].
  8. „Unlabeled Cards“ I
    In den nächsten zwei Vorträgen geht es um eine etwas andere Art Zählproblem: Das Zählen unbeschrifteter Objekte. Zunächst sollte der Unterschied zwischen dem zählen beschrifteter und unbeschrifteter Objekte deutlich gemacht werden. Dann werden die entsprechenden Zählsätze für diese Probleme bewiesen.
    Literatur: [Wil90, §3.14].
  9. „Unlabeled Cards“ II
    Ein Beispiel für ein Zählproblem unbeschrifteter Objekte ist das „Money Changing Problem“. Dies ist Hauptinhalt des Vortrags und kann bei Bedarf durch weitere Beispiele ergänzt werden.
    Literatur: [Wil90, §3.15].
  10. Sieve Method I
    Die „Sieve Method“ ist eine Methode, die es uns erlaubt, Objekte mit vorgegebenen Eigenschaften zu zählen. Diese soll anhand mehrerer Beispiele erläutert werden.
    Literatur: [Wil90, §4.2].
  11. Sieve Method II
    In diesem Vortrag sollen zum einen weitere interessante Beispiele der „Sieve Method“ vorgestellt werden. Weiterhin soll die „Snake Oil Method“, ein weiteres Verfahren zum Lösen bestimmter Zählprobleme, zusammen mit Beispielen vorgestellt werden.
    Literatur: [Wil90, §4.3].
  12. ζ- und Möbiusfunktionen
    Dieser Vortrag hat einen eher zahlentheoretischen Charakter. Wir lernen zunächst Dirichletreihen als Beispiele arithmetischer Funktionen kennen. Das sind Reihen, die ein ähnliches Faltungsverhalten wie gewöhnliche Potenzreihen aufweisen, welches sie –insbesondere für zahlentheoretische Fragen– sehr interessant macht. Auch hier werden wir formales Invertieren lernen und als Spezialfall die Möbiusinversionsformel sehen.
    Literatur: [Wil90, §2.6].
  13. Gitterpunkte I
    In diesem Vortrag werden zunächst Gitter definiert und in diesem Zusammenhang die Begriffe Fundamentalparallelotop und Gitterdeterminante eingeführt. Eventuell sollte [Wol11, Satz 8.1] skizziert werden. Ziel ist es, Gitterpunkte zu vorgegebenen Radius zu zählen, bzw. Aussagen über Asymptotik machen.
    Literatur: [Wol11, §8.1 und §§8.5.1–8.5.3].
  14. Gitterpunkte II
    Nun interessieren wir uns für die Teilmenge der primitiven Gitterpunkte. Wie viele gibt es zu vorgegebener Länge? Was hat das mit Linien auf dem Torus zu tun?
    Literatur: [Wol11, §8.6] + zusätzliche Literatur zum Torus.

Literatur

  • [Wil90] Herbert S. Wilf. Generatingfunctionology. San Diego: Academic Press, 1990.
    url: http://www.math.upenn.edu/~wilf/DownldGF.html.
  • [Wol11] Jürgen Wolfart. Einführung in die Zahlentheorie und Algebra. 2., überarbeitete und erweiterte Auflage. Wiesbaden: Vieweg+Teubner, 2011.