Math 172: Introduction to Combinatorics

UC Berkeley, Spring 2017

Lectures: TTh 11:00 -- 12:30. Lectures are in 9 Evans Hall.

Office Hours: M 5:00 -- 6:00, T 12:30 -- 1:30. Further office hours available by appointment.

  • During RRR week there will be office hours during the regular class time. Regular office hours will occur as well, and there will be an extra office hour Friday, May 5 from 5:00 -- 6:00.

Textbook: Enumerative Combinatorics through Guided Discovery by Kenneth P. Bogart. Freely available via this link. Suggestions for further resources are listed in the class policies.

Prerequisites: Math 55. Contact me if you have questions about your preparedness.

Course Outline: This is a first course in enumerative combinatorics, taught via a guided problem set. A majority of class time will be spent on active learning in small groups. Each topic below will be illustrated with several applications. Often these applications will introduce fundamental notions in combinatorics, e.g., integer partitions, Catalan objects, Ramsey numbers, graphs and graph algorithms, tree enumeration, and more.

  1. Basic counting methods: the sum, product, and quotient principles.
  2. Induction and recursion.
  3. Distribution problems and the twenty-fold way.
  4. Ordinary generating functions.
  5. The inclusion-exclusion principle.
  6. Exponential generating functions.
  7. Group actions and Pólya enumeration.
  8. Additional topics as time permits. Possible topics include:
    • an introduction to probabilistic combinatorics and random graphs ,
    • applications of combinatorics in statistical mechanics and theoretical polymer chemistry,
    • an introduction to approximate counting and Markov Chain Monte Carlo methods.

See here for a list of class policies, including the grading scheme. Familiarizing yourself with these policies is part of the expectations of this course. An approximate schedule, in the form of textbook problems that we will cover, can be found here (updated 26/04/17).

Homework: Homework is due at the beginning of most Thursday lectures; due dates are listed below. See the class policies for further details regarding homework.