Skip to main content Skip to navigation

MA241 Combinatorics

Lecturer: Roman Koteck√Ĺ

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.

Prerequisites: No formal prerequisites. The module follows naturally from first year core modules and/or computer science option CS128 Discrete Mathematics.

Leads To: MA3J2 Combinatorics II

Content:

I Enumerative combinatorics

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

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

  4. Generating functions and the Catalan numbers

  5. Permutations, Partitions and the Stirling and Bell numbers

II Graph Theory

  1. Basic concepts (isomorphism, connectivity, Euler circuits)

  2. Trees (basic properties of trees, spanning trees, counting trees)

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

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

  5. Elements of Ramsey Theory

III Boolean Functions

Book:

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

Archived Pages: 2011 2012 2014 2015 2016 2017

yr1.jpg
Year 1 regs and modules
G100 G103 GL11 G1NC

yr2.jpg
Year 2 regs and modules
G100 G103 GL11 G1NC

yr3.jpg
Year 3 regs and modules
G100 G103

yr4.jpg
Year 4 regs and modules
G103

Archived Material
Past Exams
Core module averages