MA241/MA341 Combinatorics
Lecturer: Robert Silversmith
Term(s): Term 1
Status for Mathematics students: List A (MA241 is for 2nd years, MA341 for 3rd years provided MA241 has not been taken in a previous year).
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:
- 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, Springer-Verlag, 2000.