BMS Basic Course -- Diskrete Strukturen I
Summer Term 2021
Prof. Stefan Felsner
LV-Nr.: 3236 L 149
The lecture is scheduled at 10am every Tuesday and Thursday
during the semester.
April 20., 13:25
It seems that due to a zoom update parts of the net were
I have recorded the lecture it will be uploaded to youtube today.
For the link visit detailed contents (Vorlesungsinhalte).
April 20., 10:25
We have problems with zoom. Update version and forgotten meetings.
I'll try to give and record the lecture as soon as possible.
The first meeting will be April 13. at 10am
on zoom in this virtual room:
This is a Berlin Mathematical School (BMS) Basic Course, and will thus be taught in
According to the Corona regulations of TU Berlin the course will be
given in a distance learning scheme.
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 21/22, and a more specialized course
Diskrete Strukturen III in the summer term 2022.
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 very 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:
- Basic Counting
- Generating Functions
- Combinatorics of Finite Sets
- Duality Theorems
- Polya Theory
- Design Theory
- Graphs and Chromatic Number
- Gray Codes and De Brujin Sequences
- Catalan Families
The tutorials are directed by Felix Schröder.
There will be two tutorials a week, one in English, the other in German.
- Tuesday 14:15 - 15:45, [zoom] (Kenncode 006171)
- Thursday 16:15 - 17:45 [zoom] (Kenncode 075428)
This sheet is optional. However, we recommend thinking about the problems.
- Practice sheet
- Practice sheet
Exercises marked with a star (*) are optional 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. If somebody marks an exercise she/he is not able to
present in a satisfying way, ALL exercises of this sheet will be
disregarded and therefore not counted (also, each exercise is only
counted once, even if presented in both tutorials). We expect a better
presentation and solutions of master- and BMS students, compared to
the ones acceptable from bachelor students. To receive a
certificate for the tutorials (Schein), you have to solve at least 50%
of the exercises.
the Modul, participants have to pass an oral exam.
- M.Aigner: A Course in Enumeration;
- R.Graham, D.Knuth, O.Patashnik: Concrete Mathematics;
- S.Jukna: Extremal Combinatorics;
- J.H.van Lint and R.M.Wilson: A Course in Combinatorics (2nd ed.);
Cambridge Univ. Press, 2001.
- R.Stanley: Enumerative Combinatorics, Volume I;
Cambridge Univ. Press, 1997.
- R.Stanley: Enumerative Combinatorics, Volume II;
Cambridge Univ. Press, 1999.
- D.B.West: Combinatorial Mathematics;
Cambridge Univ. Press, 2021.
Last modified April 2021