Skip to main content Skip to navigation

MA241 Combinatorics

Lecturer: Robert Silversmith

Term(s): Term 1

Status for Mathematics students: List A for Mathematics

Commitment: 30 lectures

Assessment: 10% by 4 fortnightly assignments during the term, 90% by a two-hour written examination

Formal registration prerequisites: None

Assumed knowledge: The module starts from first principles and requires only interest in Mathematics and some level of mathematical maturity

Useful background:


Leads to: The following modules have this module listed as assumed knowledge or useful background:


I Enumerative Combinatorics:

  • Basic counting (Lists with and without repetitions, Binomial coefficients and the Binomial Theorem)

  • Applications of the Binomial Theorem (Multinomial Theorem, Multiset formula, Principle of inclusion/exclusion)
  • Linear recurrence relations and the Fibonacci numbers

  • Generating functions and the Catalan numbers

  • Permutations, Partitions and the Stirling and Bell numbers

II Graph Theory:

  • Basic concepts (isomorphism, connectivity, Euler circuits)

  • Trees (basic properties of trees, spanning trees, counting trees)

  • Planarity (Euler's formula, Kuratowski’s theorem, the Four Colour Problem)

  • Matching Theory (Hall's Theorem and Systems of Distinct Representatives)

  • Elements of Ramsey Theory

III Boolean Functions


Edward E. Bender and S. Gill Williamson, Foundations of Combinatorics with Applications, Dover Publications, 2006. Available online at the author's website:

John M. Harris, Jeffry L. Hirst and Michael J. Mossinghoff, Combinatorics and Graph Theory, Springer-Verlag, 2000.

Additional Resources