Math 432 - Combinatorics - Spring 2012

General Information:

Meeting Time:MWF 11 - 11:50
Location: Jones 306
Instructor:Ryan Vinroot
Office: Jones 130
Office Hours: M 3-4, W 3-4, Th 10-11:30, F 12:30-1:30 (and Th 3-4:30 if you really can't make any of the others), or by appointment/walk-in.
Textbook:Applied Combinatorics, Fifth Edition, by Alan Tucker
Midterm - 30%, Homework - 35%, Final Exam - 35%. The grading scale will be the standard 10 percentage point scale, so that a final score of 93 or higher is an A, 90-92 is an A-, 87-89 is a B+, 83-86 is a B, 80-82 is a B-, etc.
Attendance & Lecture Policy:You are expected to attend all lectures. Attendance is crucial in order to succeed in the course. Any legitimate absence for a test must be discussed with me prior to the test date. Please do not email or text during lecture, and keep all cell phones/hand held devices/laptops put away during lecture (especially during exams).
Prerequisites: Math 214 - Foundations of Mathematics, and Math 211 - Linear Algebra. Also, as this is a 400-level class, it will be assumed that you are comfortable with mathematical proofs beyond the level of Math 214. In particular, I will lecture with the assumption that everyone has had either Math 307 or Math 311, although there is no material from these courses that will be needed for this one.
Syllabus: Combinatorics is a difficult subject to define, as it is extremely broad. The goal of the course will be to introduce you to two major topics in combinatorics: graph theory and enumerative combinatorics. Both of these topics may be applied in numerous areas, some of which are mentioned in the textbook, although we will concentrate on developing the theory behind these topics.

We will begin with Chapter 5 of the textbook, which covers some basic enumeration. Many of you may have seen some of this material in a statistics or probability course, or some other course, although we will try to understand this material from a new point of view. Following Chapter 5, we will cover topics in graph theory, begninning with an introduction in Chapter 1, circuits and coloring in Chapter 2, and a few topics on trees and algorithms in Sections 3.1, 3.2, 4.1, and 4.2. After covering graph theory, we will spend the rest of the semester learning more about enumeration, centered around the idea of generating functions in Chapter 6. We will cover topics in Chapters 7 and 8 as well, as well as some interesting topics not in the text.

Dates & Course Announcements:

Exam Calendar (Tentative):
Midterm Week of Mar 1 TBA TBA
Final Exam Thurs, May 3 9-12 TBA
  • All relevant announcements will be listed here. Check back frequently (don't forget to refresh your browser) for updates.
  • Important Dates and Class Holidays:
    • Fri, Jan 27: ADD/DROP DEADLINE
    • Sat, Mar 3 - Sun, Mar 11: NO CLASS (Spring Break)
    • Fri, Mar 16: WITHDRAW DEADLINE
    • Thurs, May 3, 9:00 - 12:00 - FINAL EXAM
  • (3/26) My regular office hours today from 3-4 are canceled.
  • (3/28) Here is a link to the page with the pdf of the free second edition of Herbert Wilf's "generatingfunctionology": Wilf.
    I will be following parts of these notes, along with parts of Chatper 6 of our text, when covering generating functions.


As is the case with all of mathematics, the only way to learn it well is to do as many problems as possible. So, homework problems will be a very important part of the course, and there will be homework assigned every week (other than the week of the midterm). Completion of all homework problems is required, and your grade on a homework assignment will be based on completeness, as well as on the details of the solutions of the problems graded. In particular, I will not necessarily grade every homework problem assigned, but part of your score for an assignment will be for the completion of all problems. Individual homework assignment should be completed by the student alone, although I am always open for questions, either in office hours or by email.

For each homework problem assigned, a complete solution with each step explained should be written up clearly and neatly. Be sure to completely explain your steps and reasoning for calculations as well as for proofs. This is especially important in enumerative problems, as there can be many ways to arrive at the same answer, and what I am interested in is your thought process.

Homework is due at the beginning of class on the due date of the assignment. Late homework will be marked off 20% for every day late. Homework turned in after class on the due date is considered one day late, and the next weekday after that 2 days late, and so on. Everything is easier, of course, if you turn in the homework on time!
Assignment Problems Due Date
1 5.1 #18, 24, 5.2 #46, 67, 5.3 #14, 19, 5.4 #14, 32 Mon, Jan 30
2 5.5 #14(d,e,f,g), 21, 26, 32, 8.1 #20, 27, 8.2 #10, 25 Mon, Feb 6
3 8.2: Finish the proof of Theorem 2, by proving the formula for Nm*, and #37,
1.1 #16, 18, 22, 1.2 #6, 11, 14
Mon, Feb 13
4 1.3 #9, 14, 15, 1.4 #8, 9, 12, 14, 20 Mon, Feb 20
5 2.1 #8, 12(a,c), 13, 14, 2.2 #4(b,h), 6, 16 Mon, Feb 27
6 2.3 #1(d,f), 2.4 #1, 2, 8(a,b), 11(a,b,c) Wed, Mar 14
7 6.1 #14, 22, 6.2 #18, 31, 6.3 #2, 15, 18, 20 Fri, Apr 6
8 6.3 #21, 6.4 #2, 12, 20, 6.5 #1(c,d,e), #2(c,d,e) Mon, Apr 16
9 7.3 #3(b,c,d), 5, 7, 7.4 #6, 9(b,c,d), 7.5 #1(b,c), #2(for #1b,c) Mon, Apr 23

Math Major Writing Requirement (Math 300):

If you are a math major, and you would like to complete your major writing requirement through a writing assignment in this class, please let me know in the first week of class. This writing assignment will not count towards your grade in this class, but will rather just serve as your Major Writing Requirement. If you decide to do this, you must write your paper on a topic in Combinatorics approved by me, and you must keep to a schedule of turning in drafts that is set at the beginning of the semester in order to get credit. You are also encouraged to sign up for Math 300 during this semester if you fulfill the writing requirement through this class.