CO 330: Combinatorial Enumeration (Fall 2021)

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 available on LEARN at the start of the semester.

Organization: Because of the ongoing pandemic, this course will meet online only. Pre-recorded lectures will be posted each Wednesday, which you will watch on your own. I highly recommend you pause the videos as you go, trying out the examples and proofs for yourself before watching how they are done. The end of each lecture will present some additional problems for you to think about (these are separate from your bi-weekly assignment questions). We will also have a live session every Tuesday from 1:30pm – 2:20pm with the instructor and TAs, where we will split into groups, go through the problems from the end of the lectures, and take your questions. I consider the live session a core component of the course, and you should plan to attend every week. We will be using Piazza as a discussion board, and all your mathematical questions about course content should be posted there.

Assessment: Final exam (40%), one midterm (30%), and weekly assignments (30%)

Topics (we may not cover all of these but we will cover most of them): Combinatorial classes and combinatorial specifications. Ordinary generating functions. Lattice paths and the q-Binomial Theorem. Recursive structure: classes of rooted trees, Dyck paths, Catalan numbers, patterned strings. Formal power series and formal Laurent series. The Lagrange Implicit Function Theorem. Integer partitions. Exponential generating function and labelled objects. Random generation of combinatorial objects.

Main Reference: CO 330 Course Notes by David Wagner available here. Many thanks to David Wagner for releasing the notes into the public domain.

Optional references with additional details include generatingfunctionology by H. Wilf and Chapter 2 of An Invitation to Analytic Combinatorics by S. Melczer.

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 run in your browser at this link (after a short load time of up to a minute) or downloaded at this link (it can also be viewed as a static HTML page here). Possibilities for running Sage yourself include

  1. Installing Sage on your computer from its website (can be surprisingly tricky)
  2. Signing up for a free account on the online browser-based CoCalc service
  3. Using Waterloo’s JupyerHub website (Requires Waterloo login)
  4. Using the cloud environment at this link (Note: this does not require any signup or download, but there is an initial load time of up to a minute. Your work does not carry over on page reload – this is very useful for some quick computations, but download anything you want to save!)