University of St Andrews

MT5821: Advanced Combinatorics

Notice
This material will remain here until the end of August.

The module

The module will run in Semester 2 (January to April 2017).

The module descriptor is here. As you will see, this allows some flexibility. This year, we will be doing syllabus 1 (enumeration and formal power series). Materials for the other syllabuses are available: polynomial combinatorics, finite geometries.

Organisation

The module information sheet is here.

Lectures are Mondays (odd weeks), Wednesdays, and Fridays at 12:00 in room 1A. Tutorials are Mondays at 15:00 and Tuesdays at 11:00 in room 3B. You are welcome to come to my office at any time when I am free; please see my timetable for my free hours.

Course material and resources

Lecture notes

This schedule for the semester is somewhat tentative!

1. Counting subsets
2. Combinatorics of subsets
3. Formal power series
4. Linear recurrences with constant coefficients
5. Gaussian coefficients
6. Möbius inversion
7. Number partitions
8. Set partitions and permutations
9. Product and substitution revisited
10. Counting up to symmetry

Problems and solutions

The solutions given here do not aim to solve the problems in the most efficient way possible; but if you read them, you may learn something from them. But note that they are not model solutions to guide you in the exam!

• Problems 1: Binomial coefficients; solutions
• Problems 2: Ramsey's Theorem, Steiner systems; solutions
• Problems 3: Formal power series; solutions
• Revision Problems 1; solutions
• Problems 4: Recurrence relations; solutions
• Problems 5: Gaussian coefficients; solutions
• Problems 6: Inclusion-exclusion, Möbius function; solutions
• Revision problems 2; solutions
• Problems 7: Number partitions; solutions
• Problems 8: Set partitions and permutations; solutions
• Problems 9: Counting up to symmetry; solutions

Past exam papers

Here are the sample exam paper and the actual paper set in 2014, the last time this syllabus was used.

Miscellany

The upper bound for the Ramsey number R₂(5,5) (the smallest number n such that n people at a party must include either 5 mutual friends or 5 mutual strangers) has been improved from 49 to 48. The paper is here. The lower bound remains at 43 (which is conjectured to be the correct value).

We showed early on in the module that the number of compositions of n (expressions of n as an ordered sum of positive integers) is 2ⁿ⁻¹, while the number of compositions of n into 1s and 2s is a Fibonacci number.

Prove that the number of compositions of n into odd numbers is also a Fibonacci number (suitably shifted).

A solution is here.

--oo--

Here is a problem for you to try. No special knowledge required.

Problem
Let f be a polynomial which takes integer values on all the non-negative integers. Show that f takes integer values on all integers.

Here is a solution (but try it yourself first!)

Here is Zhu Shijie's "Pascal triangle" from his book Siyuan Yujian (1303).

Peter J. Cameron
Room 317, Mathematical Institute
pjc20@st-andrews.ac.uk
19 May 2017