Math 432 - Combinatorics - Spring 2014

General Information:

Meeting Time:MWF 9 - 9:50
Location: Jones 306
Instructor:Ryan Vinroot
Office: Jones 130
Office Hours: Mon 10-12 and Wed 10-11, 1:30-2:30 (appointments are also OK, although I am not available on Tues/Thurs)
Textbook:Applied Combinatorics, Sixth Edition, by Alan Tucker
Class Participation - 5%, Midterm - 30%, Homework - 35%, Final Exam - 30%. 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:It is expected that you attend all lectures, with exceptions minimized. It is greatly appreciated when you are on time. Please do your best to stay awake and attentive during lecture, please do not email or text during lecture, and keep all cell phones/hand held devices/laptops put away during lecture. While it is understandable that you may miss a lecture here and there, or be sleepy in class once in awhile, repeated absences, late arrivals, naps, or general non-attentiveness will negatively affect your class participation score.
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 specific 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 by covering Chapters 1 and 2 of the textbook, which gives an overview of some of the main topics in graph theory. Following Chapters 1 and 2, we will then cover Chapter 5, which is an introduction to 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. After the introductory chapter on enumeration, we will then return to graph theory, and cover a few topics on trees and algorithms in Sections 3.1, 3.2, 4.1, and 4.2. Finally, we will return to enumeration, centered around the idea of generating functions in Chapter 6. We will then cover some sections in Chapter 7 on recurrences, inclusion-exclusion in Sections 8.1, 8.2, as well as some interesting topics not in the text, as time permits.

Dates & Course Announcements:

Midterm and Final Exams:

The midterm will be a take-home exam, and will cover Chapters 1, 2, and 5. You will have one week to complete it, and you will be given the midterm whenever we finish Chapter 5 (which will likely be either just before or just after Spring Break).

The final exam will be cummulative, and will consist of a take-home portion as well as a timed portion. Our final exam is scheduled for the very first time slot, and so you will be given the take-home portion one week prior, it will only cover material up to that point, and it will be due at the start time of the final exam slot. There will be a short timed portion of the final exam given during the final exam time slot as well, consisting of true/false and short answer/calculation problems.

Exam Calendar (Tentative):
Midterm Week of Mar 17 TBA TBA
Final Exam Mon, Apr 28 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:
    • Mon, Jan 20: NO CLASS (MLK, Jr Day)
    • Mon, Jan 27: ADD/DROP DEADLINE
    • Sat, Mar 1 - Sun, Mar 9: NO CLASS (Spring Break)
    • Fri, Mar 14: WITHDRAW DEADLINE
    • Mon, Apr 28, 9:00 - 12:00 - FINAL EXAM
  • (1/24) Because of the snow day on Wednesday, the first homework is now due on Mon, Jan 27. I will have office hours today (Fri, Jan 24), 10-12 and 2-4 for any questions about the homework or class.
  • (2/3) I have now set my regular weekly office hours: Mon 10-12 and Wed 10-11, 1:30-2:30.
  • (4/16) I will have extra office hours today. My hours will be: 10-11, 1:30-3, 4-5.
  • (4/23) My office hours today (Wed, Apr 23) will be 10-11 (regular) and 1-2 (shifted back 30 min). I will have extra office hours tomorrow (Thurs, Apr 24) 9 AM-12 Noon.


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 almost every week (other than the week of the midterm/final). 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. Working with classmates on homework is a delicate topic: it is allowed, as long as this is limited to collaborative discussion (and not someone simply telling you the solution). This is restricted to discussion only, and individual homework assignments should be completed by the student alone after such discussions take place. I am always open for questions, either in office hours or by email. You should not, under any circumstances, attempt to look up solutions or hints to problems online. I will consider this plagiarism, an honor offense.

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. When you are in doubt whether you should explain something, then explain it. If you are tempted to use words like "clearly" or "obviously", then instead explain the statement in a short sentence.

Homework is due at the beginning of class on the due date of the assignment, which will almost always be on a Friday. Late homework will be marked off 10% if it is turned in after the beginning of class, but by 5 on the due date. It will be marked 20% off if I have it by the beginning of class (or 9 AM) on the following weekday, and 20% off for each day after (with 9 AM being the cutoff time for that day). Everything is easier, of course, if you turn in the homework on time!
Assignment Problems Due Date
1Sec. 1.1 #3, 7, 18, Sec. 1.2 #5(a)-(d), #6(a)-(d) Mon, Jan 27
2Sec. 1.2 #14, Sec. 1.3 #3, 4, 6, 9 Fri, Jan 31
3Sec. 1.3 #16, Sec. 1.4 #8, 9, 12, 13, 14, 20 Fri, Feb 7
4Sec. 1.4 #27(b,c), Sec. 2.1 #2, 3, 12(a,c)
Sec. 2.2 #4(b,d)
Fri, Feb 14
5Sec. 2.2 #6, Sec. 2.3 #1(f,h,j)
Sec. 2.4 #1, 2, 11(a,b,c)
Fri, Feb 21
6Sec. 5.1 #18, 28, Sec. 5.2 #36, 42, 67, Sec. 5.3 #14, 19
For 5.3 #14, Assume that mixed partial derivatives do not depend on order.
Fri, Feb 28
7Sec. 5.4 #18, 40, Sec. 5.5 #14(d,f), 23, 26, 32 Fri, Mar 14
8Sec. 3.1 #4, Sec. 3.2 #2, Sec. 6.1 #2(c,e), 17, 20 Fri, Mar 28
9Sec. 6.2 #18, 27, Sec. 6.3 #2, 11, 15
Sec. 7.1 #6, Sec. 7.2 #7
Fri, Apr 4
10Sec. 7.3 #3(b,d), 7, Sec. 7.4 #6, 9(b,c), 10
Sec. 6.5 #1(d,e), 2(d,e)
Fri, Apr 11
11Sec. 7.5 #1(c,d), 2(for #1c,d), Sec. 8.1 #20, Sec. 8.2 #10, 25, 39 Fri, Apr 18

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 and we will discuss it. 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.