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:

• 1.1, 1.2
• 2.2, 2.5
• 3.1, 3.2, 3.3
• 4.1, 4.3
• 4.2, 4.4, 4.5
• 6.1, 6.2, 6.3
• 7.1, 7.2, 7.3
• 8.1, 8.2, 8.3, 8.4
• 10.1
• 11.4

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.

• Week 2: Exercises 1.2, 1.3 Solutions
• Week 3: Exercises 2.1, 2.13, 2.14 Solutions
• Week 4: Exercises 3.1, 3.2, 3.6, 3.10
• Week 5: Exercises 3.11, 3.20, 3.23, 3.24 Solutions
• Week 6: Exercises 4.3, 4.4, 4.5, 4.9
• Week 7: Exercises 4.10, 4.11, 4.12
• Solutions
• Week 8: Exercises 6.3, 6.4, 6.5 Solutions
• Week 9: Exercises 7.1, 7.3, 7.5, and fill in the missing step in the proof of Theorem 7.2.
• Solutions
• Week 10: Exercises 8.1, 8.3, 8.4, 8.7
• Week 11: Exercises 10.1, 11.2

Other web resources:

• The book Analytic Combinatorics by Flajolet and Sedgwick is free to download here (but it is over 800 pages long!)
• Another free-to-download book on enumerative combinatorics is A=B, by Petkovsek, Wilf and Zeilberger; this discusses a computational method for proving complicated identities.

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)