Math 432 - Combinatorics - Spring 2018

General Information:

Meeting Time:MWF 10 - 10:50
Location: Jones 302
Instructor:Ryan Vinroot
Office: Jones 100D
Office Hours: Mon 11-12, Wed 1-2, Thurs 3-5 (also by appointment)
Textbook:Introductory Combinatorics, Fifth Edition, by Richard A. Brualdi
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-, 77-79 is a C+, 73-76 is a C, 70-72 is a C-, 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, the course is taught at a level with the assumption that you have had at least one other proof-based mathematics course. It is expected that you have strong proof-writing skills.
Course Topics: Combinatorics is a difficult subject to define, as it is quite broad. The author of our textbook has given the following description of combinatorics in the introductory section of the book: "combinatorics is concerned with the existence, enumeration, analysis, and optimization of discrete structures".

We will plan to cover topics from the first 8 chapters of the textbook, in order. In particular, these chapters focus on enumerative combinatorics, and the main goal of the class will be to develop enumerative techniques. After the introductory lecture, we will cover the fundamentals of basic enumeration in Chapter 2, the Pigeonhole Principle and an introduction to Ramsey Theory in Chapter 3, Inversions (4.2) and Partial Orders (4.5), a somewhat in-depth study of binomial coefficients in Chapter 5, Inclusion-Exclusion in Chapter 6, Recursions and Generating Functions in Chapter 7, and some particularly interesting examples of sequences coming from enumeration in Chapter 8. Depending on time limits, we will then either go back and spend time on partial orders and Möbius inversion (Section 6.6) or we will cover some topics in Chapters 9 and 10.

Dates & Course Announcements:

Midterm and Final Exams:

The midterm will be a take-home exam, will cover the material up until Spring Break, and will be handed out in the week after Spring Break. You will have approximately one week to complete the take-home exam.

The final exam will be cumulative, timed, and during the scheduled final exam block on Tues, May 8, 2-5 pm.

Exam Calendar (Tentative):
Midterm Take-home Due: Mon, Mar 19, 5 PM Jones 100D
Final Exam Tues, May 8 2-5 pm Jones 302
  • 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 26: ADD/DROP DEADLINE
    • Sat, Mar 3 - Sun, Mar 11: NO CLASS (Spring Break)
    • Fri, Mar 16: WITHDRAW DEADLINE
    • Tues, May 8, 2:00 - 5:00 - FINAL EXAM
  • (1/17) My office hours during this short first week are as follows: Wed Jan 17, 11-12 and 4-5; Thurs Jan 18 3-4.
  • (1/17) I have to leave early because of the weather and kid pick-up, so I will not have my 4-5 office hours today. But I'll still have 3-4 office hours tomorrow (Thurs 1/18).
  • (1/19) The first HW assignment has been posted below, and is due Fri, Jan 26. You should also be reading the textbook, and you should in particular read Section 1.2 on Magic Squares, which we will not cover in lecture. Also be sure to read the HW policy carefully below. Note that some problems that are assigned should not be turned in, but rather are assigned for your own benefit.
  • (1/22) My office hours this week will be as follows: Mon Jan 22, 2-3; Wed Jan 24, 1:30-2:30; Thurs Jan 25, 4-5.
  • (1/29) My office hours this week will be as follows: Mon Jan 29, 1-2; Tues Jan 30, 11-12; Thurs Feb 1, 3-5.
  • (2/1) Here is a link to the paper "Small Ramsey Numbers" by S. P. Radziszowski, mentioned in the book and in class: Small Ramsey Numbers.
    This is a "Dynamic Survey" in that it is periodically updated (and has been 15 times so far since its first publication in 1994, most recently on Mar 3, 2017). It is a fantastic reference on the subject, and includes a 40+ page reference section.
  • (2/5) My office hours this week (and likely my weekly office hours for the semester) will be: Mon Feb 5, 11-12; Wed Feb 7, 1-2; Thur Feb 8, 3-5.
  • (2/13) My weekly office hours for the semester are set, and will be every week, Mon 11-2, Wed 1-2, and Thurs 3-5, unless otherwise posted.
  • (2/21) Here are two articles about unimodal and log-concave sequences which were mentioned in class: Log-Concave and Unimodal Sequences in Algebra, Combinatorics, and Geometry, by Richard P. Stanley, and Hodge Theory in Combinatorics, by Matthew Baker. You may need to be logged on to the William and Mary network to access the second one.
  • (2/26) Extra Office Hours: I will be out of town this Thurs, Mar 1, and so I will offer extra office hours during the first part of the week. My office hours this week will be as follows: Mon Feb 26, 11-12 and 1-2:30; Tues Feb 27, 11-12 and 4-5; Wed Feb 28, 11-12 and 1-2.
  • (2/28) There is a typo in the book on two problems; one to turn in and one not to turn in. In both problems 44 and 45, the exponent of -1 is not correct. In 44, it should be (-1)n1 instead of (-1)n1-n2+n3. In problem 45, it should be (-1)n1+n3 instead of (-1)n1-n2+n3-n4.
  • (3/14) The take-home midterm was handed out in class today, Wed, Mar 14. It is due on Mon, Mar 19, by 5 pm in my office Jones 100D. Please take note of the guidelines listed on the midterm.
  • (4/16) The last homework (HW #11) has been posted. Please note that the due date is the last Wednesday of classes, instead of Monday.
  • (4/25) Here is the resource for some of the material on Stirling numbers and Bell numbers that we have covered the last several days in class: generatingfunctionology, by Herbert S. Wilf.
  • (4/25) My office hours on Thurs, Apr 26, have to be shifted. Instead of 3-5, my office hours will be 2:30-4. I will post my office hours for the exam period by the end of the week.
  • (4/27) My office hours during the exam period will be as follows:
    Mon Apr 30, 1-3
    Tues May 1, 1-3
    Wed May 2, 1-4
    Thurs May 3, 9-12
    Mon May 7, 1-5.


Homework problems will be a very important part of the course, and there will be homework assigned almost every week. Proofs should be written carefully and neatly, with attention paid to the completeness of your argument. 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. The main point is: you are being graded on the presentation, clarity, and correctness of your explanation and solution.

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.

Homework is due at the beginning of class on the due date of the assignment, and if you like you may email me a pdf of your homework if you LaTex it (which is not required but welcomed). Homework that is turned in or in my email inbox 10 minutes after the beginning of the class is considered late. Everyone will be allowed exactly 1 unpenalized late-by-one-day homework (so once during the semester, a HW can be turned in one weekday late by 5 pm with no penalty). After that, late penalties are:
10% off if it is turned in after the beginning of class, but it is in my hands, or in my email inbox as a pdf by 5 pm on the day it is due.
20% off if it is turned in by 5 pm the next weekday after the due date.
20% more off for each (week)day late, turned in by 5 pm, thereafter.
Everything is easier, of course, if you turn in the homework on time!

Homework scores will each be out of 50 points. Your lowest homework score of the semester will be dropped.
Assignment Problems Due Date
1 Turn in: 1.8 #14, 18, 2.7 #2, 6, 14, 20
Don't turn in: 1.8 #22, 24, 37, 2.7 #1, 4, 9
Fri, Jan 26
2 Turn in: 2.7 #38, 45, 48, 53, 3.4 #15, 19
Don't turn in: 2.7 #19, 22, 28, 29, 3.4 #6, 11, 18
Fri, Feb 2
3 Turn in: 3.4 #20, 22, 27, 4.6 #8, 9, 58
Note: In 4.6 #58, you should also define each point to be related to itself (by default)
Don't turn in: 3.4 #23, 24, 25, 4.6 #6, 7, 45
Fri, Feb 9
4 Turn in: 4.6 #34, 35, 37, 38, 50, 59
Don't turn in: 4.6 #10, 27, 30, 49, 54, 55
Fri, Feb 16
5 Turn in: 5.7 #11, 16, 21, 25, 28, 43
Don't turn in: 5.7 #12, 13, 14, 15, 22, 27
Fri, Feb 23
6 Turn in: 5.7 #24, 30, 44, 48, 49, 50
Don't turn in: 5.7 #18, 19, 31, 37, 41, 45
Fri, Mar 2
7 Turn in: 6.7 #5, 9, 14, 16, 20, 24(a,c)
For #14, first think about #12 (look at the hint in the back)
Don't turn in: 6.7 #4, 12, 22, 23, 24(b), 26
Mon, Mar 26
8 Turn in: 7.7 #16, 17, 18, 23, 25, 28
Don't turn in: 7.7 #14, 15, 19, 24, 26, 27
Mon, Apr 2
9 Turn in: 7.7 #30, 34, 42, 40, 44, 45
Don't turn in: 7.7 #29, 31, 32, 33, 36, 43
Mon, Apr 9
10 Turn in: 7.7 #6, 46, 50, 8.6 #1, 2, 4
For 7.7 #6 and 8.6 #1, 2, the hints in the back of the book should be helpful
Don't turn in: 7.7 #1, 3, 4, 7, 8.6 #3, 36
Mon, Apr 16
11 Turn in: 8.6 #21, 24, 25, 28, 29, 30
Don't turn in: 8.6 #23, 26, 27, 11, 12, 16
Wed, Apr 25

Math Major Writing Requirement (Math 300):

If you are a senior 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.

Student Accessibility Services:

William & Mary accommodates students with disabilities in accordance with federal laws and university policy. Any student who feels they may need an accommodation based on the impact of a learning, psychiatric, physical, or chronic health diagnosis should contact Student Accessibility Services staff at 757-221-2512 or at to determine if accommodations are warranted and to obtain an official letter of accommodation. For more information, please visit the SAS webpage.