Combinatorics - 2019 entry

Combinatorics, a branch of pure mathematics, is the study of finite mathematical structures and is used frequently in computer science to obtain estimates on the number of elements of certain sets. This module will be particularly concerned with enumerative questions, that is, counting the number of structures of a particular kind. We will consider structures, including partitions, lattice paths and block designs. Furthermore, we will look at relations with other branches of mathematics, notably probability theory, algebra, matrix theory and number theory. Your goal is to solve combinatorial problems of standard type in the topics covered and to tackle easier problems of non-standard form.

Prerequisite module: MTH1002 Methods and MTH2002 Algebra, or equivalent

To inspire a genuine engagement with combinatorial methods and their applications in other branches of mathematics.

On successful completion of this module, you should be able to:

Module Specific Skills and Knowledge:

1 solve combinatorial problems of standard type in the topics covered and to tackle easier problems of non-standard form.

Discipline Specific Skills and Knowledge:

2 understand the close links between combinatorial problems and other areas of mathematics including the central topics of algebra and probability theory;

3 appreciate the role of conjecture and investigation within mathematics.

Personal and Key Transferable/ Employment Skills and  Knowledge:

4 develop strategies to solve challenging mathematical problems, which will enhance your time management and problem solving skills.

- binomial and multinomial coefficients;

- application to basic enumerative problems and to lattice path counting;

- the pigeonhole principle;

- parity arguments;

- the inclusion-exclusion principle;

- recurrences;

- generating functions;

- the Catalan numbers and Catalan families;

- rook polynomials applications to derangements and the probleme des menages;

- designs;

- affine and projective designs;

- Fisher's inequality;

- symmetric designs;

- Steiner triple systems;

- partitions of sets;

- Stirling and Bell numbers;

- partitions of numbers;

- partitions with restricted parts;

- Euler's pentagonal number theorem.

If a module is normally assessed entirely by coursework, all referred/deferred assessments will normally be by assignment.

If a module is normally assessed by examination or examination plus coursework, referred and deferred assessment will normally be by examination. For referrals, only the examination will count, a mark of 40% being awarded if the examination is passed. For deferrals, candidates will be awarded the higher of the deferred examination mark or the deferred examination mark combined with the original coursework mark.

ELE: http://vle.exeter.ac.uk

Reading list for this module: