QUEEN MARY, UNIVERSITY OF LONDON

MTHM030/MTH710U

Enumerative and Asymptotic Combinatorics

Course Material January - April 2011


The syllabus for the course is:

  1. Techniques: inclusion-exclusion, recurrence relations and generating functions.
  2. Subsets, partitions, permutations: binomial coefficients; partition, Bell, and Stirling numbers; derangements. q-analogues: Gaussian coefficients, q-binomial theorem.
  3. Linear recurrence relations with constant coefficients.
  4. Counting up to group action: orbit-counting lemma, cycle index theorem.
  5. Posets and Möbius inversion, Möbius function of projective space.
  6. Asymptotic techniques: order notation: O, o, ~. Stirling's formula. Techniques from complex analysis including Hayman's Theorem.

The course will be based roughly on the contents of Peter Cameron's notes from the 2006 course, which are available here. However, there is a new version of the notes (last updated 18 February 2010), which he intends to publish. The current plan is to cover the following sections in the new version of the notes:

Exercises

There are many exercises given at the end of each chapter in Peter's notes. You should think about all the exercises which are relevant to the above sections of the notes. You should hand in solutions to the following exercises from the new version of the notes at our weekly meetings.

Other web resources:

Past exam papers

A sample exam paper and six past exam papers are here: 2003 exam, 2005 exam, 2006 exam, 2008 exam, 2009 exam, and 2010 exam. Note that there was a typo in Q1(d) 2010: P and Q should be exponential generating functions and the required identitiy should be P(x)=Q(exp(x)-1)