# 2015/16 Undergraduate Module Catalogue

## MATH3143 Combinatorics

### 15 creditsClass Size: 130

**Module manager:** Dr C Harris**Email:** matcmh@leeds.ac.uk

**Taught:** Semester 2 View Timetable

**Year running** 2015/16

### Pre-requisite qualifications

Familiarity with abstract, mathematical proof writing.**This module is approved as a discovery module**

### Module summary

Combinatorics is concerned with the counting arrangements, patterns, designs, assignments, schedules, and configurations of objects. Its applications are widespread: computer scientists, bankers, statisticians, works supervisors, industrial engineers being amongst its users.### Objectives

Many problems in the real world take the form 'how many…?' Not all such problems have easy solutions. This module introduces techniques for dealing with some of the more difficult problems of this kind.On completion of this module, students should be able to decide which of the several counting techniques introduced in the course (e.g. the inclusion-exclusion principle, Ferrers diagrams, generating functions, etc.), is best suited to solving any one of a large class of counting problems, and should be able to apply that technique to solve the problem.

### Syllabus

Examples of problems include:

(i) How many ways are there to distribute 10 distinct books among 6 identical boxes?

(ii) If you and I each have a pack of 52 cards, what are the chances, if we simultaneously turn over one card at a time, that at least one pair matches exactly?

(iii) Every day, fifteen children walk to school in five groups of three. Can you arrange the groups for seven days so that each pair of children will walk together exactly once?

Topics covered include:

1. Multiplication and summation principles.

2. Counting permutations and combinations. Occupancy problems. Selection problems.

3. Inclusion-exclusion principle. Derangements.

4. Partitions of sets. Partitions of integers. Ferrers diagrams and duality.

5. Generating functions. Euler's generating function for partition numbers.

6. Hall's marriage theorem. Latin squares. Systems of distinct representatives.

7. Sperner families. De Bruijn-Erdős theorem.

8. Steiner triple systems.

(Possibly) 9. Pigeonhole principle and Ramsey numbers.

### Teaching methods

Delivery type | Number | Length hours | Student hours |

Lecture | 33 | 1.00 | 33.00 |

Private study hours | 117.00 | ||

Total Contact hours | 33.00 | ||

Total hours (100hr per 10 credits) | 150.00 |

### Private study

Studying and revising of course material.Completing of assignments and assessments.

### Opportunities for Formative Feedback

Regular problem solving assignments### Methods of assessment

**Exams**

Exam type | Exam duration | % of formal assessment |

Standard exam (closed essays, MCQs etc) | 2 hr 30 mins | 100.00 |

Total percentage (Assessment Exams) | 100.00 |

Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated

### Reading list

The reading list is available from the Library websiteLast updated: 08/02/2016

## Browse Other Catalogues

- Undergraduate module catalogue
- Taught Postgraduate module catalogue
- Undergraduate programme catalogue
- Taught Postgraduate programme catalogue

Errors, omissions, failed links etc should be notified to the Catalogue Team.PROD