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 |
Grade
Breakdown: | 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.
Homework:
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.
|