# 2008/09 Undergraduate Module Catalogue

## MATH3142 Combinatorics

### 10 creditsClass Size: 200

**Module manager:** Professor A. Pillay**Email:** pillay@maths.leeds.ac.uk

**Taught:** Semester 2 (Jan to Jun) View Timetable

**Year running** 2008/09

### Pre-requisites

MATH2210 | Introduction to Discrete Mathematics |

**This module is approved as an Elective**

### Module summary

Combinatorics is concerned with the study of arrangements, patterns, designs, assignments, schedules, configurations, in particular with the question 'How many ?' Its applications are widespread: computer scientists, bankers, statisticians, works supervisors, industrial engineers being amongst its users.### Objectives

Many counting problems arise in the real world in 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 (e.g. inclusion-exclusion principle, dot diagram method, generating function method etc.), introduced in the course, is best suited to solving any one of a large class of counting problems and should be able to apply that technique to complete the problem?s solution.### Syllabus

Examples of problems include:

(i) How many different solutions are there in positive integers x, y, z, t to the inequality x + y + z + t < 41 ? (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? In how many different ways can you paint the squares of an 8 x 8 grid with black/white paint if two paintings are regarded as the same if one can be obtained from the other by a rotation? To solve these and similar problems is not hard - if you go about it the right way.

Topics covered include:

1. Sum Rule, product rule.

2. Problems involving binomial coefficients. Occupancy problems. Inclusion-exclusion principle. Derangements.

3. Partitions. Dot diagrams.

4. Stirling's formula.

5. Generating functions. Theory and lots of examples. Homogeneous and inhomogeneous linear recurrences (by generating function and characteristic equation method).

6. Polya's theory of counting. Including Burnside's lemma, the orbit stabliliser theorem and Polya's theorem.

7. Dirichlet's box principle. Generalisation to Ramsey numbers.

### Teaching methods

Due to COVID-19, teaching and assessment activities are being kept under review - see module enrolment pages for information

Delivery type | Number | Length hours | Student hours |

Example Class | 6 | 1.00 | 6.00 |

Lecture | 20 | 1.00 | 20.00 |

Private study hours | 74.00 | ||

Total Contact hours | 26.00 | ||

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

### Methods of assessment

Due to COVID-19, teaching and assessment activities are being kept under review - see module enrolment pages for information

**Exams**

Exam type | Exam duration | % of formal assessment |

Standard exam (closed essays, MCQs etc) | 2 hr | 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: 22/03/2010

## 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