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.
- Basic counting methods: the sum, product, and quotient principles.
- Induction and recursion.
- Distribution problems and the twenty-fold way.
- Ordinary generating functions.
- The inclusion-exclusion principle.
- Exponential generating functions.
- Group actions and Pólya enumeration.
- 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.
- Homework 1, due January 26 in class. Solutions.
- Homework 2, due February 2 in class. Solutions.
- No homework due to Midterm 1, February 9 in class. Solutions.
- Homework 3, due February 16 in class. Solutions.
- Homework 4, due February 23 in class. Solutions. Updated, fixed mistake in #1b and typo in #3.
- Homework 5, due March 2 in class. Solutions.
- Homework 6, due March 9 in class. Solutions.
- Homework 7, due March 16 in class. Solutions.
- No homework due to Midterm 2, March 23 in class. Solutions.
- Homework 8, due April 4 in class. Solutions. Note: longer than usual. Updated 11/04/17 to clarify #1.
- Homework 9, due April 11 in class. Solutions.
- Homework 10, due April 18 in class. Solutions.
- Homework 11, due April 25 in class. Solutions.
- Homework 12, not to be handed in. Solutions. Note: you are still responsible for this material.