Basic methods in enumerative combinatorics. "The twelvefold way" (counting functions subject to various restrictions), sieve methods such as different versions of inclusion-exclusion, the involution principle and determinantal lattice path counting. Various aspects of the theory of partially ordered sets, e.g. lattice theory. Möbius inversion in posets and connections to topology.
SF2708 Combinatorics 7.5 credits
An advanced course in combinatorics.
Information per course offering
Course offerings are missing for current or upcoming semesters.
Course syllabus as PDF
Please note: all information from the Course syllabus is available on this page in an accessible format.
Course syllabus SF2708 (Autumn 2007–)Content and learning outcomes
Course contents
Intended learning outcomes
The course aims to give acquaintance with basic combinatorial theory and methods. The purpose is to provide deeper knowledge in order to give a foundation for further mathematical studies as well as for applications in related fields, notably computer science. In practice, this means that the student should
- Be familiar with various standard combinatorial objects and sequences and their properties
- Reformulate, and consequently solve, problems in terms of the aforementioned objects
- Perform computations with, and deduce properties of, formal power series
- Deduce recursions, generating functions and explicit expressions for combinatorially defined number sequences
- Construct combinatorial proofs of identities and inequalities
- Apply Möbius inversion, inclusion-exclusion and related sieve methods to solve enumerative problems
- Define and deduce properties of various classes of posets
- Describe, and perform computations in, the incidence algebra of a poset
- Use various methods to compute the Möbius function of a poset and interpret such problems in topological terms.
Literature and preparations
Specific prerequisites
SF1631 Discrete Mathematics or equivalent material. Some mathematical maturity.
Recommended prerequisites
Equipment
Literature
Richard P. Stanley, "Enumerative Combinatorics Vol. I", 2nd edition,
Cambridge University Press, 1997.
Examination and completion
If the course is discontinued, students may request to be examined during the following two academic years.
Grading scale
Examination
- TEN1 - Examination, 7.5 credits, grading scale: A, B, C, D, E, FX, F
Based on recommendation from KTH’s coordinator for disabilities, the examiner will decide how to adapt an examination for students with documented disability.
The examiner may apply another examination format when re-examining individual students.
Other requirements for final grade
Homework assignments, possibly with some sort of oral or written supplementary examination.
Opportunity to complete the requirements via supplementary examination
Opportunity to raise an approved grade via renewed examination
Examiner
Ethical approach
- All members of a group are responsible for the group's work.
- In any assessment, every student shall honestly disclose any help received and sources used.
- In an oral assessment, every student shall be able to present and answer questions about the entire assignment and solution.