
An advanced course in combinatorics.
Course offering missing
Course offering missing for current semester as well as for previous and coming semestersContent and learning outcomes
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
Literature and preparations
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.
Examination and completion
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.
Further information
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.
Course web SF2708Offered by
Main field of study
Mathematics
Education cycle
Second cycle
Add-on studies
No information inserted