MATU9KA - Combinatorics

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

Aims

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.

Content

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.

Bibliography

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.

Assessment

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

© University of Stirling FK9 4LA Scotland UK • Telephone +44 1786 473171 • Scottish Charity No SC011159
Portal Logon