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 twohour 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:
 MA150 Algebra 2 or MA149 Linear Algebra or MA148 Vectors and Matrices
 CS137 Discrete Mathematics and its Applications 2
Synergies:
Leads to: The following modules have this module listed as assumed knowledge or useful background:
 MA252 Combinatorial Optimization
 MA3J2 Combinatorics II
 MA4L2 Statistical Mechanics
 MA4J3 Graph Theory
 MA4M4 Topics in Complexity Science
 MA4J5 Structures of Complex Systems
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, SpringerVerlag, 2000.