Instructor:
Sergei Korotkikh
E-mail: "last name" AT berkeley DOT edu
Office: 843 Evans Hall
Syllabus: here
Class Meetings: Mondays, Wednesdays, and Fridays. 11:00AM-11:59AM. 3109 Etcheverry.
Office Hours: 3PM-4PM Mon, 6PM-7PM Wed (via Zoom), 12:30PM-1:30PM Fri.
E-mail: All e-mail correspondence should have the subject line starting from "Math 172:".
Recommended textbook (optional, some part of the lecture material will differ from the book):
A Walk Through Combinatorics (4th Edition) by Miklós Bóna.
Grade: Homeworks (30% of the grade), Midterm (25% of the grade), Final (45% of the grade).
Homeworks: Generally, problem sets will be posted on Friday after class and will be due on Gradescope by the end of the next Friday. There will be a couple of exceptions to this schedule, due to holidays and on the week of the midterm. Feel free to work together on homework problems, but your solutions must be written up independently and reflect your own understanding of the material. The lowest homework score will be dropped in the end of the semester. No late homeworks will be accepted, unless there are specific accommodations arranged beforehand with the instructor.
Bonus problems: Majority of the homeworks will include an optional problem of increased difficulty. These problems are intended to be hard and are purely optional, but solving them will give an extra credit in the end of the semester, which will be capped at 5% of the final grade.
Schedule:
| Date | Topic | Homework | Notes |
| August 23 | Intro, pigeon-hole principle | ||
| August 25 | Weak induction | Problem Set 1 posted, due 09/01 | |
| August 28 | Strong induction, counting problems | ||
| August 30 | Counting problems (cont.) | ||
| September 1 | Binomial coefficients | Problem set 2 posted, due 09/08 | |
| September 4 | No class | Labor day | |
| September 6 | Binomial theorem | ||
| September 8 | Multinomial theorem, compositions | Problem set 3 posted, due 09/15 | |
| September 11 | Compositions (cont.), set partitions | ||
| September 13 | Partitions | ||
| September 15 | Partitions, permutations | Problem Set 4 posted, due 09/22 | |
| September 18 | Cycle types of permutations | ||
| September 20 | Stirling numbers | ||
| September 22 | Inclusion-Exclusion Principle | Problem Set 5 posted, due 09/29 | |
| September 25 | Formal power series | ||
| September 27 | Formal power series (cont.) | ||
| September 29 | Linear recurrence relations | ||
| October 2 | Generalized binomial theorem | ||
| October 4 | Binomial theorem (cont.) | ||
| October 6 | Midterm | Problem set 6 posted, due 10/13 | |
| October 9 | Catalan numbers | ||
| October 11 | Catalan numbers (cont.) | ||
| October 13 | Partitions | Problem set 7 posted, due 10/20 | |
| October 16 | Pentagonal number theorem | ||
| October 18 | Exponential generating functions | ||
| October 20 | Graphs, Eulerian trails | Problem set 8 posted, due 10/27 | |
| October 23 | Eulerian trails (cont.) | ||
| October 25 | Hamiltonian cycles | ||
| October 27 | Isomorphisms of graphs | Problem set 9 posted, due 11/03 | |
| October 30 | Trees | ||
| November 1 | Cayley's theorem | ||
| November 3 | Kruskal's algorithm | Problem set 10 posted, due 11/10 | |
| November 5 | Bipartite graphs | ||
| November 7 | Hall's theorem | ||
| November 10 | No class | Problem set 11 posted, due 11/17 | Veterans day |
| November 13 | Turan's Theorem | ||
| November 15 | Tutte's theorem, chromatic polynomial |