Combinatorics BMS basic Course -- Diskrete Strukturen I Summer Term 2019 Sommersemester 2019 Prof. Stefan Felsner Sprechstunde n.V. LV-Nr.: 3236 L 149 Di 12-14, MA 141 Fr 10-12, MA 141

## News:

The oral exams will be on 11.+12.7.,8.8. as well as 1.+2.10.2019. Please write an email to
Felix for an appointment.

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

This is also the first course of the course series Diskrete Strukturen. It will be continued by Graphentheorie/Graph Theory (Diskrete Strukturen II), winter term 19/20, and a more special course Diskrete Strukturen III in the summer term 2020.

## 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 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:
1. Basic Counting
2. Generating Functions
3. Combinatorics of Finite Sets
4. Posets
5. Duality Theorems
6. Polya Theory
7. Design Theory
8. Graphs and Chromatic Number
9. Gray Codes and De Brujin Sequences
10. 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.
• Tuesday 14:15 - 15:45, MA 549,
• Thursday 10:15 - 11:45, MA 549

fschroed(at)math.tu-berlin.de, room MA 509

### 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]
12. Practice sheet [pdf] updated
13. Practice sheet [pdf]

14. 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 recieve a certificate for the tutorials (Schein), you have to solve at least 50% of the exercises.
To complete the modul participants have to pass an additional oral exam.

## References:

• M.Aigner: A Course in Enumeration;
Springer, 2007.
• R.Graham, D.Knuth, O.Patashnik: Concrete Mathematics;