AS/SC/MATH4160.03W

Combinatorial Mathematics

Combinatorics is an important branch of both pure mathematics and modern applied mathematics. Faced with finite discrete structures (such as graphs, combinatorial designs, geometric configurations, etc.) basic questions arise:

  1. Existence: given a set of prescribed properties, do any such objects exist?
  2. Enumeration: If they exist, how many are there?
  3. Algorithms: Are there efficient methods to construct some (all) such objects?

Such combinatorial questions arise in many areas, ranging through logic, algebra, geometry, probability and statistics, operations research, computer science and modeling in the social sciences, physical and natural sciences and engineering. Students have probably also encountered combinatorial questions on mathematical contests and mathematical aptitude tests!

We will study some central techniques in this field. Topics covered in this course will include introduction to enumeration; relations and partitions; combinatorial identities; algebraic counting techniques; ordered sets.

Additional topics, for projects and presentations, will be based on the interests of the students.

The text will be K. Bogart, Introductory Combinatorics, (HBJ).

The prerequisites are a solid background in linear algebra (MATH2222.03, or MATH2022.03) and mathematical maturity, indicated by completion of at least two courses at the 3rd or 4th year level and a course emphasizing mathematical or logical proofs. Students who lack this background need permission of the instructor.

The final grade will be based on assignments, class tests, and projects/presentations.