Math 40210 - Basic Combinatorics

Spring 2014

Instructor: David Galvin


NOTE: all course policies announced here are subject to change before the first day of semester!

About the course

Combinatorics is the study of finite or countable discrete structures. ``Discrete'' here means that the structures are made up of distinct and separated parts (in contrast to ``continuous'' structures such as the real line). Combinatorics is an area of mathematics that has been increasing in importance in recent decades, in part because of the advent of digital computers (which operate and store data discretely), and in part because of the recent ubiquity of large discrete networks (social, biological, ecological, ...).

Typical objects studied in combinatorics include permutations (arrangements of distinct objects in various different orders), graphs (networks consisting of nodes, some pairs of which are joined), and finite sets and their subsets.

There are many subfields of combinatorics, such as enumerative (e.g., in how many ways can n objects in a row be rearranged, such that no object is returned to its original position?), structural (e.g., when is it possible to travel around a network, visiting each edge once and only once?), and extremal (e.g., what's the largest number of subsets of a set of size n you can choose, in such a way that any two of them have at least one element in common?). In this course, we will explore each of these aspects of combinatorics, and maybe some more as time permits.

Back to the top of the page

Basic information

Back to the top of the page


Back to the top of the page

Late assignments

All homework must be done by the due date to receive credit, and all quizzes and exams must be taken at the assigned times.

I will not consider requests for homework extensions, or make-up quizzes and/or exams, except in the case of legitimate, university-sanctioned conflicts. It is your responsibility to let me know the full details of these conflicts before they cause you to miss an assignment! Excepting university-sanctioned conflicts, it is your responsibility to be in class for all scheduled lectures.

Back to the top of the page


The bi-weekly homework is an important part of the course; it gives you a chance to think more deeply about the material, and to go from seeing (in lectures) to doing. It's also yoiur opportunity to show me that you are engaging with the course topics.

Homework is an essential part of your learning in this course, so please take it very seriously. It is extremely important that you keep up with the homework, as if you do not, you may quickly fall behind in class and find yourself at a great disadvantage during exams.

You should treat the homework as a learning opportunity, rather than something you need to get out of the way. Reread, revise, and polish your solutions until they are correct, concise, efficient, and elegant. This will really deepen your understanding of the material. I encourage you to talk with your colleagues about homework problems, but your final write-up must be your own work.

Homework solutions should be complete (and in particular presented in complete sentences), with all significant steps justified. For example, on a problem using the pigeonhole principle, you should state clearly what the pigeons are and what the pigeonholes are; and in a proof by induction you should state (and prove!) both the base case and the induction step clearly.

All homeworks will be taken from the following homework bank, which will be updated throughout the semester.

Back to the top of the page


Back to the top of the page


Nothing yet.

Back to the top of the page

Supplementary material

Here is where I will post any supplementary material for the course, such as slides that I go over in class.

Back to the top of the page


Honor code: You have all taken the Honor Code pledge, to not participate in or tolerate academic dishonesty. For this course, that means that although you may (and should) discuss assignments with your colleagues, you must write the final version of each of your assignments on your own; if you use any external sources to assist you (such as other textbooks, computer programmes, etc.), you should cite them clearly; your work on the mid-semester exam and the final exam should be your own; and you will adhere to all announced exam policies.

Class conduct: The lecture room should be a place where you should feel free to engage in lively discussion about the course topic; don't be shy! But non course related interruptions should be kept to a minimum. In particular, you should turn off or switch to silent all phones, etc., before the start of class. If for some good reason you need to have your phone on during class, please mention it to me in advance.

A general comment: Like many other endeavors (such as driving a car or mastering a piece of software), mathematics is something that you learn by doing. Attending class and reading the appropriate sections of the textbook is very important, but isn't enough to do well. After each lecture you should work through every example and proof from your class notes. Don't be perturbed if you have to re-read and re-do some topics many times before you begin to feel that you are mastering them. That is just how mathematical learning goes. It's a slow process, but a worthwhile one.

If after struggling with a topic you still feel like you are making no headway, don't give up! Leave it aside for a while to let your unconscious brain work on it. Then go back to it, and talk it over with you colleagues, and come talk to me. It's what I'm here for!

Back to the top of the page