Combinatorics
 BMS Basic Course -- Diskrete Strukturen I
Summer Term 2023

Sommersemester 2023
Prof. Stefan Felsner
LV-Nr.: 3236 L 149
The lecture is scheduled at 12am on Tuesday in room A053 (architecture building!)
and at 10am Thursday in the same room A053.
Zeichnung

News:

In the last exercise session on 18th of July we will take some time for your questions about the exam. It will take place in E-N 195.

The remaining Thursday lectures will all be in A 053 (same as Tuesdays)!

Two years ago some students took the initiative and compiled a script from the lecture series. Here is a link to the document: Skript.pdf.

General:

This is a Berlin Mathematical School (BMS) Basic Course, and will thus be taught in English.

This is the first course of the course series (Studienschwerpunkt) Diskrete Strukturen. It will be continued by Graphentheorie/Graph Theory (Diskrete Strukturen II), winter term 23/24, and a more specialized course Diskrete Strukturen III in the summer term 2024.

Contents:

Combinatorics is a branch of pure mathematics concerning the study of mostly finite objects. It is related to many other areas of mathematics, such as algebra, probability theory and geometry, as well as to applied subjects in computer science and statistical physics. Typical combinatorial questions are: Does a set with certain properties exist at all? If yes, how many are there? How do I find them? Combinatorics abounds with beautiful problems that are easily understood, but often a real challenge to solve.

Combinatorics is as much about problem solving as theory building, though it has developed powerful theoretical methods, especially since the later twentieth century. The goal of this course will be to provide you with a broad overview – and with a firm, concrete “working knowledge” on basic combinatorial principles, tools, methods, theories, and results.

The course will cover most of the following topics:
  1. Basic Counting
  2. Generating Functions
  3. Combinatorics of Finite Sets
  4. Posets
  5. Duality Theorems
  6. Polya Theory
  7. Design Theory
  8. Catalan Families

Tutorials:

The tutorials are directed by Felix Schröder. There will be two tutorials a week, one in English, the other in German, starting from April 24th.
Questions? Send an email to
fschroed(at)math.tu-berlin.de

Problem sets

PrePractice sheet [pdf]
This sheet is optional. However, we recommend thinking about the problems.
  1. Practice sheet [pdf]
  2. Practice sheet [pdf]
  3. Practice sheet [pdf]
  4. Practice sheet [pdf]
  5. Practice sheet [pdf]
  6. Practice sheet [pdf]
  7. Practice sheet [pdf]
  8. Practice sheet [pdf]
  9. Practice sheet [pdf]
  10. Practice sheet [pdf]
  11. Practice sheet [pdf(changed)]
  12. Practice sheet [pdf]

    13. Exercises marked with a star (*) are especially hard and give extra points.

Terms to receive a certificate / credit-points:

At the beginning of every tutorial every participant has to mark in a list, which exercises of the current sheet she/he solved and is able to present. Then for every exercise one of the participants is chosen to present it. We expect better presentations and solutions of Master- and BMS students, compared to the ones acceptable from Bachelor students. To complete the Modul, participants have to pass an oral exam.

References:

Last modified April 2023