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 twohour 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:
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
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, SpringerVerlag, 2000.