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
Homework assignment will be posted here.
- Sheet 0 (not to be submitted)
- Sheet 1, Sheet 1 - Sol. sketchs
- Sheet 2, Sheet 2 - Sol. sketchs
- Sheet 3 (corrected a mistake in Problem 10.), Sheet 3 - Some scanned sol.
- Sheet 4, Sheet 4 - Some scanned sol.
- Sheet 5,
- Sheet 6, Sheet 6 - Some scanned sol.
- Sheet 7, Sheet 7 - Some scanned sol.
- Sheet 8, (corrected a mistake in Problem 4)
- Sheet 9,
- Sheet 10, (to be submitted before June 28th, 16:00)
- Sheet 11
- Sheet 12
Here are more exercises covering the first part of the course.
- Supplementary Exercises, (not to be submitted)
Here is a Formative Midterm exam to assess your progression.
- Formative Exam, (to be submitted before June 20th, 16:00)
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):
- Week 12 (4-5 July):
- Week 13 (11-12 July):
- Week 14 (18-19 July):
- 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)