# MATH1031 Discrete Mathematics

This module introduces a wide variety of topics about objects and structures that are discrete (like the integers) rather than continuous (like the real numbers). We will often ask "how many?"; these counting problems can be simple to state, using ordinary language, but surprisingly difficult to solve, needing both careful common sense and some specific techniques. We also study graphs (not the familiar graphs of functions, but networks) and their many applications.

While we will present some general mathematical techniques, many of the problems that you will encounter encourage some creative thinking in their solution; you must learn to explain your logic clearly, in some suitable combination of words, symbols and diagrams.

The main emphasis of the work of second term will be the development, via topics drawn from graph theory and combinatorics, of important abilities such as problem-solving, self-study, written and oral presentation skills. This will be done through guided workshops and a presentation to other students, and will prepare you for project work in your final year. Of course these skills will be very useful for other modules, and the rest of your life.

For the first 13 weeks there are two lectures and one tutorial per week. Problems are set weekly to be handed in and there is a compulsory examination (Collections) in January to see how you are going on. In May/June there is a 2-hour written examination worth 70% of the module mark. In weeks 14 to 19 there will be 2-hour workshop sessions. You will give a presentation on this work in week 19 and hand in a final report at the end of term. The presentation is worth 10% and the report is worth 20% of the module mark.

The books by Biggs, Grimaldi and Tucker all cover most of the material. Graham, Knuth and Patashnik is a mine of interesting information and examples, written in a very chatty style. Wilson’s book is excellent for the graph theory part of the course and goes well beyond. Marcus is very good on the other parts of the course. Please see the readling list for details.

## Outline of Course

Aim: To provide students with a range of tools for counting discrete mathematical objects. To provide experience in problem-solving, presentation, mathematical writing and group working skills through guided self-study and seminars in topics in combinatorics and graph theory.

### Term 1

- Principles of counting: arrangements and permutations, selections and combinations, mathematical induction, combinatorial vs. computational proof; pigeonhole principle, inclusion-exclusion formula.
- Recurrence relations and generating functions: recurrence relations, generating functions, partitions.

### Terms 2 & 3

- Graphs: basic concepts (paths, circuits, connectedness, trees, etc.).
- Project & presentation topics: students will work through guided self-study on one of a set of graph theoretic or combinatorial topics such as planar graphs, derangements, graph colouring and optimisation problems.

### Prerequisites

For details of prerequisites, corequisites, excluded combinations, teaching methods, and assessment details, please see the Faculty Handbook.

### Reading List

Please see the Library Catalogue for the MATH1031 reading list.

### Examination Information

For information about use of calculators and dictionaries in exams please see the Examination Information page in the Degree Programme Handbook.