# Mathematics and Statistics Group

## MAT9KA: Combinatorics

**SCQF Level: **10

**Availability: **Autumn, Advanced module

**Course Prerequisite: **MAT9K4

**Credit Value: **22 (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.