| MTH 481 | Discrete Mathematics I | Spring 2012 |
Course page. http://www.math.msu.edu/~magyar/Math481 .
The dates below are tentative. Changes will be announced in class and on our course page.
Section numbers refer to Harris, Hirst, Mossinghoff, Combinatorics and Graph Theory (2nd ed). We will cover Part 2 of the book, then selections from Part 1. Homework will be assigned weekly on the Course page.
| Week | Date | Section: Topic
| 1/9 | 2. Introduction, set notation
| 1 | 1/11 | 2.1. Some essential problems: n!, nk, (n | k), multinomial coefficients
| 1/13 | Fourth problem: multi-sets ((n | k)), stretching transformation
| 1/16 | M.L. King Day, no class
| 2 | 1/18 | 2.2. Properties of binomial coefficients, (n | k) = (n | n−k)
| 1/20 | 2.2. Pascal's triangle, binomial theorem, position transformation
| 1/23 | 2.5. Principle of inclusion-exclusion (PIE)
| 3 | 1/25 | 2.5. Examples of PIE, positive vs. negative counting
| 1/27 | 2.6. Generating functions, binomial theorem & logical algebra.
| 1/30 | 2.6.1. Generating function for double decks
| 4 | 2/1 | 2.6.2. Generating function for multi-sets: ∑k≥0 ((n | k)) xk = 1/(1−x)n
| 2/3 | 2.6.3. Changing money
| Last day to drop course with tuition refund 2/6 | 2.6.4. Fibonacci numbers
| 5 | 2/8 | 2.6.5. Recurrence relations
| 2/10 | 2.6.6. Catalan numbers and convolution
| 2/13 | 2.6.6 Catalan numbers: models
| 6 | 2/15 | 2.7.1. Groups
| 2/17 | 2.7.2. Burnside lemma
| 2/20 | Counting with symmetry examples
| 7 | 2/22 | Review
| 2/24 | Review
| 2/27 | Midterm exam
| 8 | 2/29 | Review of exam
| Last day to drop course with no grade reported 3/2 | 1.1.1. Graph definitions
| 3/3-11 | Spring Break, no classes
| 3/12 | 1.1.2. Graph basics, connectedness
| 9 | 3/14 | 1.1.3. Special graphs, bipartite graphs
| 3/16 | 1.3.1 & 1.3.2. Tree basics
| 3/19 | 1.3.4. Counting trees, Cayley theorem nn-2
| 10 | 3/21 | 1.4. Konigsberg problem and Euler circuits
| 3/23 | 1.5.1. Planar graphs
| 3/26 | 1.5.2. Euler formula n − m + r = 2; region degree inequality gr ≤ 2m
| 11 | 3/28 | 1.5.4. Kuratowski theorem
| 3/30 | 1.5.4. Kuratowski theorem
| 4/2 | 1.5.3. Platonic solids
| 12 | 4/4 | 1.5.3. Platonic solids
| 4/6 | 1.4.1, 1.4.2. Graph coloring
| 4/9 | 1.4.3. Four Color Theorem
| 13 | 4/11 | 1.4.4. Chromatic polynomial
| 4/13 | Review
| 4/16 | Unlabelled trees: ∑n≥1 rnxn = x ∏k≥1 (1−xk)−rk
| 14 | 4/18 | Unlabelled trees
| 4/20 | Unlabelled trees
| 4/23 | Review
| 15 | 4/25 | Review
| 4/27 | Review, evaluation
| 5/4 | Final exam Fri 10am-12noon, Wells C-308
| |