Jean-Philippe Labbé
Arnimallee 2, Room 103
familyname at math dot fu-berlin dot de

Johanna Steinmeyer
Arnimallee 2, Room K007
familyname at math dot fu-berlin dot de

Patrick Morris
Arnimallee 3, Room 207
pm0041 at zedat dot fu-berlin dot de

Course Schedule

Tuesdays from 14:00 to 16:00 in Arnimallee 3, HS 001, and on
Wednesdays from 14:00 to 16:00 in Takusstr. 9 SR 006.

Tuesday from 16:00 to 18:00 in Takustr. 9, SR 049, and
Wednesdays from 10:00 to 12:00 in Arnimallee 6, SR 025-6.


The course will cover a selection from the following topics:

Enumerative Combinatorics
Elementary counting methods, double-counting, pigeonhole principle, recursions, generating functions, inclusion-exclusion, inversion, Polya theory
Discrete Structures
Graphs, set systems, designs, posets, matroids
Graph Theory
Trees, matchings, connectivity, planarity, colourings

Final Exam and Requirements

Final Exam
The final exam takes place on
Wednesday July 26th, 14:00 to 16:00
Gr. Hörsaal, Takustr. 9

The re-take exam takes place on
Wednesday October 11th, 14:00 to 16:00
Gr. Hörsaal, Takustr. 9

The details of the requirements can be read HERE

Course Plan

These lectures notes may contain typos or mistakes. If you find a significant mistake, please let me know.

  • Week 1 (18-19 April): Numbers, Equinumerousity, Addition-Multiplication principles, Bijective Proof ([MN, Ch. 1])
  • Week 2 (25-26 April): Bijective Proof, Binomial Theorem, Inclusion-Exclusion Principle and Pigeonhole Principle ([A, Ch. 2], [B, Ch. 1,3,4], [MN, Ch. 3], [Br, Ch. 2,6 & 8])
  • Week 3 (2-3 May): The Twelvefold Way: Integer partitions, Set-partitions, compositions, Stirling numbers, Bell numbers ([St, 1.4], [B, Ch. 5], [A, 1.2 to 1.4], [Br, Ch.3])
  • Week 4 (9-10 May): Multinomial coefficients, weak compositions, Ferrers diagrams, Solving recurrence relations (Iteration and Char. polyn. Methods) ([B, 4.2], [A, 3.2], [MN, 12.3], [Br, Ch. 7.1-2])
  • Week 5 (16-17 May): Solving Rec. Rel. (Symbolic Differenciation and undetermined Coeff. Methods) Formal Power Series: Definitions and Operations. Generating Functions: basic examples. ([A, 3.1], [Br, Ch. 7.3-4], [MN, 12.1-2], [St, 4.1-2], [B, Ch. 8.1])
  • Week 6 (23-24 May): Applications of Generating Functions to enumeration. Recurrence relations. Catalan numbers. Exponential Generating Functions. ([MN, 12.3-7], [St. 4.1-3], [Br. 7.4-7], [B. Ch. 8], [A. Ch. 3])
  • Week 7 (30-31 May): Posets: Definitions and properties, constructions, examples, Lattices ([B. Ch. 16], [MN, Ch. 2], [St, Ch. 3])
  • Week 8 (6-7 June): Examples of lattices, Incidence Algebra, Delta, Zeta and Möbius Functions, Möbius Inversion formula, Examples ([B. Ch. 16], [MN, Ch. 2], [St, Ch. 3])
  • Week 9 (13-14 June): Incidence structures: Definitions, Examples, Adjacency and Incidency matrices, regularity, connectedness, chain, cycles, subgraphs, ([B. Ch. 9], [MN, Ch. 4], [Br. Ch.11], [A. Ch. 6])
  • Week 10 (20-21 June): Graph morphisms, (semi-)Eulerian graphs, (semi-)Hamiltonian graphs, Ore and Dirac's Theorems, Characterization of trees, Cayley's Theorem on labeled trees. ([Br. Ch.11], [MN, Ch.4-5], [A. Ch. 6-7], [B. Ch.9-10])
  • Week 11 (27-28 June): Algorithms: Minimal Spanning Tree, Growing a tree from a root, BFS, DFS, Kruskal algorithm, Dijkstra's Algorithm ([A. Ch. 7], [B. Ch. 10], [MN. Ch. 5.3-4])
  • Week 12 (4-5 July): Matchings in Bipartite graphs, Connectivity ([Br. Ch. 9], [A. Ch. 8], [B. Ch. 11])
  • Week 13 (11-12 July): Colorings of graphs, Planar graphs [Br. 13.1-3, MN. Ch. 6]
  • Week 14 (18-19 July): Chromatic polynomial, Deletion-Contraction principle, 5-Color Theorem [Br. Ch. 13.1-3]


  • Bona, M., A Walk Through Combinatorics
  • Brualdi, R., Introductory Combinatorics
  • Aigner, M., Discrete Mathematics (English or German)
  • West, D., Introduction to Graph Theory
  • Matousek, J., Nesetril, J., An invitation to Discrete Mathematics
  • Stanley, R., Enumerative Combinatorics (Volume 1)

comments powered by Disqus