Skip to main content Skip to navigation

MA241 Content

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.