Skip to main page content - your browser does not fully support our CSS, or is text-only.

Mathematics and Statistics Group

MAT9KA: Combinatorics

SCQF Level: 10
Availability: Autumn, Advanced module
Course Prerequisite: MAT9K4
Credit Value: 22 (1 module)


To provide techniques for the solution of problems concerning task assignment, scheduling, networks, searching and counting; and to establish algorithms where appropriate.

Learning Outcomes

Students should be able to select and implement counting techniques, find systems of distinct representatives of appropriate sets, employ graph-theoretical arguments, and apply criteria for the traversability of networks.


1. Introduction - Methods of counting, selections, binomial coefficients.
2. Pairing problems - Matchings, distinct representatives, optimal assignment algorithm.
3. Recurrence relations - Growth rates, counting problems, generating functions.
4. Inclusion-exclusion principle - Derangements, rook polynomials, forbidden permutations.
5. Graphs - Paths and cycles, matrices, vertex degrees, trees, graph-colouring and timetabling, planarity.
6. Properties of networks - Traversability, connectivity, Menger's Theorem.

Transferable Skills

Problem solving, logical skills.


I. ANDERSON, A first course in combinatorial mathematics, 2nd edn. OUP, 1989.
R.J. WILSON and J. J. WATKINS, Graphs - an introductory approach, Wiley, 1990 or
R.J. WILSON, Introduction to Graph Theory, 4th Edn., Prentice Hall, 1996.

Teaching Format

3 one-hour lectures and a 1 hour tutorial per week.


1/3 coursework (2 class tests) and 2/3 examination.