SF2708 Combinatorics 7.5 credits

Course contents

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.

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.

Course disposition

No information inserted

Specific prerequisites

SF1631 Discrete Mathematics or equivalent material. Some mathematical maturity.

Recommended prerequisites

No information inserted

Equipment

No information inserted

Literature

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.

Grading scale

A, B, C, D, E, FX, F

Examination

• TEN1 - Examination, 7,5 hp, betygsskala: 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

No information inserted

Opportunity to raise an approved grade via renewed examination

No information inserted

Examiner

No information inserted

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.

Course web

Further information about the course can be found on the Course web at the link below. Information on the Course web will later be moved to this site.

Offered by

SCI/Mathematics

Main field of study

Mathematics

Education cycle

Second cycle

Add-on studies

No information inserted