SF2708 Combinatorics 7.5 credits

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.

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.

SF1631 Discrete Mathematics or equivalent material. Some mathematical maturity.

Richard P. Stanley, "Enumerative Combinatorics Vol. I", 2nd edition,

Cambridge University Press, 1997.

If the course is discontinued, students may request to be examined during the following two academic years.

• 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.

Homework assignments, possibly with some sort of oral or written supplementary examination.

• 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.