## MAS334 Combinatorics

 Semester 1, 2018/19 10 Credits Lecturer: Prof Neil Strickland Home page Reading List Aims Outcomes Teaching Methods Assessment Full Syllabus

Combinatorics is the mathematics of selections and combinations. For example, given a collection of sets, when is it possible to choose a different element from each of them? That simple question leads to Hall's Theorem, a far-reaching result with applications to counting and pairing problems throughout mathematics.

Prerequisites: MAS211 (Advanced Calculus and Linear Algebra)
No other modules have this module as a prerequisite.

## Outline syllabus

• The binomial coefficients
• Three basic principles: parity, pigeon-holes and inclusion/exclusion
• Rook polynomials
• Hall's Marriage Theorem and its applications
• Latin squares
• Block designs and codes

## Office hours

Fridays at 14:00 in Hicks room J26

## Aims

• To illustrate the wide range of selection problems in combinatorial mathematics
• To teach the basic techniques of selection and arrangement problems
• To show how to solve a wide range of natural counting problems using these techniques

## Learning outcomes

• Solve counting and selection problems using the binomial coefficients and the basic counting principles of combinatorics
• Understand Hall's Theorem and its wide range of applications
• Appreciate the use of designs and be able to construct them

## Teaching methods

Lectures and problem-solving.

Lectures will cover the topics in the printed notes and provide proofs and solutions to many examples.
Exercises are at the back of the lecture notes, arranged into five examples sheets (the final one covering the final two chapters of the module). Four pieces of homework will be set at approximately two-week intervals over the semester. Students' handed-in solutions will be marked and returned with feedback, around one week after the hand-in deadline. Help from the lecturer is available in the office hour or by appointment. Solutions will be placed on the module web page as the course progresses.

20 lectures, no tutorials

## Assessment

One formal 2.5 hour examination. Format: answer all questions.

## Full syllabus

The course is divided into six sections.

1. The binomial coefficients
Permutations and combinations, the binomial expansion, and various applications including routes in grids and their uses in counting solutions of equations. (3-4 lectures)
2. Three basic principles
Parity checks, the pigeon-hole principle, and the inclusion/exclusion principle, with lots of applications. (3 lectures)
3. Rook polynomials
The calculation of the rook polynomial for an arbitrary board. Then the reduction of many allocation problems to a rook format in order to solve them. The examples include the famous `snap' and `hostess' problems. (4 lectures)
4. Hall's Marriage Theorem and its applications
Hall's Theorem in various forms (marriage/transversal/matrix). The applications include the Konig-Ergervary Theorem and its use in job allocation problems using the Hungarian algorithm, and proving Landau's Theorem on tournaments. (4 lectures)
5. Latin squares
Application of Hall's Theorem to the problem of extending Latin rectangles to squares. Euler's problem on orthogonal Latin squares. (2-3 lectures)
6. Designs and codes
Balanced incomplete block designs and their use in the setting-up of fair experiments. Symmetric designs. The construction of various designs, for example by using quadratic residues to create cyclic designs. The links between orthogonal Latin squares and designs. The construction of some efficient error-correcting codes from symmetric designs. (2-3 lectures)

Much more detail can be obtained by consulting the relevant chapters of the book Aspects of combinatorics, by Victor Bryant, CUP (1993).