Math 40210 – Basic Combinatorics – Spring 19
Math 40210 – Basic Combinatorics – Spring 19
NOTE: all course policies announced here are subject to change up to the first day of semester!
Instructor: Abdul Basit
Office: HAYE 248
Email: abasit@nd.edu
Office Hours: Tuesdays 5:00 pm – 6:30 pm or by appointment
Meeting Times: MWF 2:00 pm – 2:50 pm, Pasquerilla Center 112
Textbook: A Walk Through Combinatorics: An Introduction to Enumeration and Graph Theory, 3rd edition, by Miklós Bóna, World Scientific Publishing Company, 2011; ISBN-10: 9814460001, ISBN-13: 978-9814460002
I expect to cover (most of) Chapters 1 through 12, and some of the later chapters as time permits.
You can find the Table of Contents here.
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.
Mathematical preparation: We will make much use of the basic mathematical language of sets and functions, and the techniques of induction and recursion. If you have taken a course such as Math 20630 (Introduction to Reasoning), you will already be familiar with everything we will use. If not, then you will be able to pick it up as the semester progresses.
Homework: Written homework will be assigned roughly every other week (with each homework weighted equally). In total, homework will count for 150 points out of 400. Specific homework policies will be announced with the first homework.
Midterm: There will be one in-class midterm, scheduled for Wednesday, March 06. This will count for 100 out of 400 points.
Here is the exam and here are solutions.
Final: There will be (cumulative) final exam on Tuesday, May 7 4:15 PM – 6:15 PM in 112 Pasquerilla Center. This will count for 150 points out of 400. Detailed information will be announced closer to the date.
Here is a practice final exam. Here are solutions to the practice exam.
Homework 1 (updated – Jan 21, due Feb 04). Solutions.
Homework 2 (updated – Feb 11, due Feb 18). Solutions.
Homework 3 (updated – Feb 24, due March 04). Solutions.
Homework 4 (updated – March 24, due April 01). Solutions.
Homework 5 (updated – April 08, due April 15). Solutions.
Homework 6 (updated April 23, due May 01). Solutions.
All homework must be done by the due date to receive credit. I will not consider requests for homework extensions, or make-up 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.
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 programs, 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.