production

## Course Overview

Combinatorics is the branch of mathematics concerned with counting. This includes counting structures of a given kind (enumerative combinatorics), deciding when certain criteria can be met, finding "largest", "smallest", or "optimal" objects (external combinatorics and combinatorial optimization), and applying algebraic techniques to combinatorial problems (algebraic combinatorics). The course is recommended to students of mathematics and computing science.

### Course Details

Study Type Level Undergraduate 1 Second Sub Session 15 credits (7.5 ECTS credits) None. No Dr Irakli Patchkoria

### Qualification Prerequisites

• Either Programme Level 1 or Programme Level 2

None.

None.

No

### Course Description

* Induction * Growth rates * Subsets and binomial coefficients (subsets of fixed size, properties of binomial coefficients, the binomial therem) * Partitions and Bell numbers * Counting with symmetry * Recurrences * Generating functions * Derangements * Principle of inclusion-exclusion * External problems * The Pigeonhole Principle * Ramsey theory * Graph theory

Syllabus

• Counting and probability, induction, growth rates.
• Permutations, subsets, selections, the Binomial Theorem, partitions, Bell numbers.
• Generating functions, derangements, exponential generating functions.
• Inclusion and exclusion, Stirling numbers of the second kind.
• External set theory, intersecting families, Sperner families.
• The Pigeonhole Principle, Ramsey numbers, Ramsey’s Theorem.
• Graphs, paths, trees, topological graph theory, Euler’s Theorem, the Platonic solids.

Course Aims

### Contact Teaching Time

Information on contact teaching time is available from the course guide.

### Teaching Breakdown

Details, including assessments, may be subject to change until 31 August 2023 for 1st half-session courses and 22 December 2023 for 2nd half-session courses.

### Summative Assessments

1st Attempt: 1 two-hour written examination (80%); in-course assessment (20%). Resit: 1 two-hour written examination paper (maximum of (100%) resit and (80%) resit with (20%) in-course assessment).

### Formative Assessment

Informal assessment of weekly homework through discussions in tutorials.

### Feedback

In-course assignments will normally be marked within one week and feedback provided to students in tutorials.

None.

## Compatibility Mode

We have detected that you are have compatibility mode enabled or are using an old version of Internet Explorer. You either need to switch off compatibility mode for this site or upgrade your browser.