# Discrete Mathematics (G5136)

15 credits, Level 4

Autumn teaching

Mathematics developed because humans had the need to count objects, or to understand the land around them (e.g. areas, volumes, location of stars). So this is where we begin this module.

A proportion of it is devoted to counting, i.e. we will find proper ways to count the number of elements in complicated sets. For example the number of phone numbers that can still connect you to the correct number, even if one digit is wrong.

These principles of counting, like the inclusion-exclusion principle naturally lead into a chapter on combinatorics, where we explore ways to count fast so we can use this ability in other disciplines, like probability.

Finally, we understand that not everything can be counted in a nice fast way. We will develop the idea of recursive equations to help us count complicated sets with the aid of computing power, which also feeds into the Computational Mathematics module.

We also develop the mathematics of graph theory. A graph is just a collection of points and lines and they are extremely versatile modelling objects. For example, a constellation is a graph, a genealogy tree is a graph and so is a map of a country. Similarly, the connections between Instagram followers is a graph, and so is the road network of a city. We will describe properties of all these different graphs in a rigorous mathematical context.

• How can you draw a given graph without lifting your pencil from the paper and without backtracking?
• How can a university timetable be created so that every student can select the modules they like without conflict?
• How many squares can you see in an NxN square grid?

### Teaching 100%: Lecture

### Assessment 20%: Coursework (Portfolio, Problem set) 80%: Examination (Unseen examination)