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 |
Grade
Breakdown: | 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:
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 sas@wm.edu to determine if accommodations are warranted
and to obtain an official letter of accommodation. For more information,
please visit the SAS webpage.
|