## |

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. |

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.

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.

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 N_{m}^{*}, 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 |