---

MAT 378 - Discrete Mathematics - Spring 2007

---

Week 1: 1/23

• Chapter 1: What is Combinatorics?

Week 2: 1/28 -- 1/30

• 2.1 & 2.2: The pigeonhole principle
• 2.3: Ramsey's theorem

Week 3: 2/4 -- 2/6

• 3.1 Four basic counting principles
• 3.2 Permutations of sets
• 3.3 Combinations of sets

Week 4: 2/11 -- 2/13

• 3.4 Permutations of multisets
• 3.5 Combinations of multisets
• 4.1 Generating permutations

Week 5: 2/18 -- 2/20

• 4.2 Inversions in permutations
• 4.3 Generating combinations
• 4.4 Generating r-combinations

Week 6: 2/25 -- 2/27

• 4.5 Partial orders and equivalence relations
• 5.1 Pascal's formula
• 5.2 The binomial theorem

Week 7: 3/3 -- 3/5

• 5.3 Binomial identities
• Review
• Exam I

Week 8: 3/10 -- 3/12 (Midterm grades on Wednesday)

• 5.5 The multinomial theorem
• 5.6 Newton's binomial theorem
• 6.1 The inclusion/exclusion principle

Week 9: 3/17 -- 3/19

• Spring Break

Week 10: 3/24 -- 3/26

• 6.2 Combinations with repetition
• 6.3 Derangements
• 7.1 Some number sequences

Week 11: 3/31 -- 4/2

• 7.2 Linear Homogeneous Recurrence Relations
• 7.3 Nonhomogeneous recurrence relations
• 7.4 Generating functions

Week 12: 4/7 -- 4/9

• 11.1 Introduction to graph theory
• Review for exam II
• Exam II

Week 13: 4/14 -- 4/16

• 11.2 Eulerian trails
• 11.3 Hamiltonian chains and cycles
• 11.4 Bipartite multigraphs

Week 14: 4/21 -- 4/23

• 11.5 Trees
• 11.7 More on trees
• 13.1 Chromatic number

Week 15: 4/28 -- 4/30

• 13.2 Plane and planar graphs
• 13.3 The 5-color theorem
• 13.4 Independence and Clique numbers

Week 16: 5/5 -- 5/7

• 13.5 Connectivity
• Review for final.

Week 17: 5/12 -- 5/14

• Final Exams
  (Our exam is scheduled for Wednesday, May 14th at 12:45 PM.)