This webpage will not be updated during the term.
All course materials will be posted on
LEARN.
Syllabus: A tentative version is available here. The final version of the syllabus will be posted on LEARN at the beginning of the semester.
Overview: Math 249 is an introduction to combinatorics at an advanced level. This material is closely related to many of the staple puzzle book questions you may have pondered as a kid, and is also foundational to every discipline involving discrete structures. Combinatorics lies in the intersection of pure mathematics, applied mathematics, and computer science, and this course will showcase the intriguing interactions between these areas. The course is primarily theoretical and you will develop your proof-writing skills while working with interesting and useful structures.
The first portion of the course is combinatorial enumeration. If you enjoyed puzzle book questions like “how many ways can you tile a $2\times n$ board with dominoes?” or ever wondered how the number of binary trees grows, and how to prove it, then you will like this part. Practically, you will learn about generating series, which are one of the most important tools in algebraic enumeration, and see a large selection of combinatorial objects. The second portion of the course is graph theory. If you enjoyed puzzle book questions of the form “can you draw a given figure without lifting your pencil or retracing any line?” or like to think about the structures of networks then you will like this part. Practically you will learn the formal foundations of graph theory, standard results and how to prove them, and some key graph algorithms.
Because Math 249 is an advanced section, we will see all the material covered in Math 239 plus additional topics that go beyond the standard material in interesting and fun ways. These additional topics will be tailored to the interests of students in the class.
Assessment: Ten assignments (30%), enumeration exam (35%), and graph theory exam (35%)
References: David Wagner’s MATH 239/249 Course Notes and additional notes distributed on LEARN
Use of Computer Software: I will be using the (free and open source) computer algebra software Sage to illustrate some examples during lectures. Although it is not necessary to learn Sage for the course, I will release the code used to generate these examples and playing around with it yourself can greatly help your understanding.
A short tutorial on Sage can be downloaded at this link or viewed as a static HTML page here. Possibilities for running Sage yourself include