Module manager: Francesca Fedele
Email: F.Fedele@leeds.ac.uk
Taught: Semester 2 (Jan to Jun) View Timetable
Year running 2024/25
Familiarity with abstract, mathematical proof writing.
This module is approved as a discovery module
Combinatorics is concerned with counting (and giving bounds for the number of, and proving existence of) 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.
Many problems in the real world take the form 'How many?' or 'Do there exist?'. 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.
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) Show that at a party of 6 people there must be either 3 people who have all met one another before, or 3 people who are mutual strangers.
Topics covered include:
1. Ordered and unordered selections, occupancy problems.
2. Partitions of sets, Bell numbers, and Stirling numbers.
3. The Inclusion-Exclusion principle and applications.
4. Partitions of numbers.
5. Generating functions. Euler's generating function for partition numbers.
6. Systems of distinct representatives and Hall's Theorem.
7. Latin squares.
8. Extremal Set Theory: intersecting families and Sperner families.
Further topics will be drawn from:
9. The pigeonhole principle & Ramsey numbers.
10. Steiner triple systems.
| Delivery type | Number | Length hours | Student hours |
|---|---|---|---|
| Lecture | 33 | 1 | 33 |
| Private study hours | 117 | ||
| Total Contact hours | 33 | ||
| Total hours (100hr per 10 credits) | 150 | ||
Studying and revising of course material.
Completing of assignments and assessments.
Regular problem solving assignments
| Exam type | Exam duration | % of formal assessment |
|---|---|---|
| Standard exam (closed essays, MCQs etc) | 2.0 Hrs 30 Mins | 100 |
| Total percentage (Assessment Exams) | 100 | |
Normally resits will be assessed by the same methodology as the first attempt, unless otherwise stated
The reading list is available from the Library website
Last updated: 4/29/2024
Errors, omissions, failed links etc should be notified to the Catalogue Team