Last updated 16 May 2019.
This course provides a general introduction to this beautiful subject. Students will learn both classical methods for clever counting, as well as how to apply more modern methods to analyze recursions and sequences. Students will also learn fundamental techniques in graph theory. Throughout the course, students will encounter novel challenges that blur the lines between combinatorics and other subjects, such as number theory, probability, and geometry, so that they develop the skills to creatively combine seeming disparate areas of mathematics.
This course is structured around challenge. Lecture topics are handpicked to reflect the rather advanced ability level of the general CMU student, and consequently, much of the curriculum sequence is original. Homework and exam problems are particularly difficult, and require creative problemsolving rather than application of learned techniques. To encourage students to truly develop these skills, collaboration is encouraged on homework, and exams (which are noncollaborative) will be opennotes.
The only prerequisite for the course is one of 21127 Concepts of Mathematics or 21128 Mathematical Concepts and Proofs.
In order to encourage students to experiment with the concepts taught in class, homework assignments will be given on alternate weeks. They will be due in class on Fridays, at the beginning of lecture. Each assignment will consist of four to five challenging problems, for which the proof or justification of each answer is more important than actual numerical answer.
Since homework is a learning activity, students are welcome to discuss ideas with each other, although collaboration in the writing stage is not permitted. In other words, please do not look at the actual document that another student is handing in.
Makeup exams will be given only in the case of a documented medical excuse, a universitysanctioned absence (e.g., participation in a varsity sporting event), or a family emergency. However, this must be requested before the official start time of each exam.
Attendance/Participation. Attendance and participation are not part of the course grade, but are strongly encouraged because the curriculum of this class contains many original components.
Academic Integrity and Collaboration. Collaboration as detailed above is permitted only on homework assignments, and not on exams. In the event of academic dishonesty, a score of zero will be assigned, and a communication will be sent to the academic advisor. This policy is motivated by the goal of maintaining a fair environment for all learners.
Late Work. There is no penalty for late homework, except that all homework must be submitted by the final class day of the semester. Any homework submitted after that date receives zero credit. However, students are strongly encouraged to submit homework on time, because this keeps the class in sync for healthy collaboration on homework, and homework is very helpful for exam preparation.
Regrade Requests. Regrade requests must be submitted in writing, within one week of receiving the graded assignment. They will be honored, but please note that it is possible for scores to decrease after a regrade.
Accommodations for students with disabilities. If you have a disability and require accommodations, please contact Catherine Getchell, Director of Disability Resources, 4122686121, getchell@cmu.edu. If you have an accommodations letter from the Disability Resources office, I encourage you to discuss your accommodations and needs with me as early in the semester as possible. I will work with you to ensure that accommodations are provided as appropriate.
Statement on Student Wellness. As a student, you may experience a range of challenges that can interfere with learning, such as strained relationships, increased anxiety, substance use, feeling down, difficulty concentrating and/or lack of motivation. These mental health concerns or stressful events may diminish your academic performance and/or reduce your ability to participate in daily activities. CMU services are available, and treatment does work. You can learn more about confidential mental health services available on campus at: http://www.cmu.edu/counseling/. Support is always available (24/7) from Counseling and Psychological Services: 4122682922.
Week  Topic  Alternate reference  Work due Fri 
Week 1
(Mon Jan 14) 
Basic counting; induction  Chapter 1; Fwdbackward induction  Homework 1 
Week 2
(Mon Jan 21) 
Inclusionexclusion,
pigeonhole principle (No class Mon Jan 21  MLK Day) 
Chapter 2;
Dirichlet's approximation theorem (on AoPS) 

Week 3
(Mon Jan 28) 
Homework 2  
Week 4
(Mon Feb 4) 
Binomial coefficients  Chapter 3; Lucas' Theorem  Exam 1 on Fri 
Week 5
(Mon Feb 11) 
Linear algebra and recurrences  Chapter 4; Wikipedia, Croot's notes  Homework 3 
Week 6
(Mon Feb 18) 
Generating functions  Generatingfunctionology (free book),
by H. Wilf. Sections 1.11.3, 2.12.3; notes from MIT's OpenCourseWare 

Week 7
(Mon Feb 25) 
More generating functions  Homework 4  
Week 8
(Mon Mar 4) 
Introduction to graphs
(No class Fri Mar 8) 
Chapter 7  
Spring break
(Mon Mar 11) 
Relax  
Week 9
(Mon Mar 18) 
Trees  Chapter 8 
Exam 2
on Fri
Homework 5 
Week 10
(Mon Mar 25) 
Traveling salesman problem  Chapter 9  
Week 11
(Mon Apr 1) 
Matchings  Chapter 10  Homework 6 
Week 12
(Mon Apr 8) 
Combinatorial geometry
(No class Fri Apr 12) 
Chapter 11  
Week 13
(Mon Apr 15) 
Ramsey theory  Alt refs
#1
and
#2
from B. Sudakov's
Princeton Combinatorics course. 
Homework 7 
Week 14
(Mon Apr 22) 
Planar graphs  Chapter 12  Exam 3 on Fri 
Week 15
(Mon Apr 29) 
Coloring  Chapter 13  Homework 8 
Final exam
Fri May 10 
In Porter 100, from 5:30pm8:30pm 
You are visitor number since 18 January 2019. 