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:

Synergies:

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

Content:

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

Books:

Edward E. Bender and S. Gill Williamson, Foundations of Combinatorics with Applications, Dover Publications, 2006. Available online at the author's website: http://www.math.ucsd.edu/~ebender/CombText/

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

Additional Resources