Math 3012 (Combinatorics), Fall 1998

Course Outline

Lectures: MWF 2, Room Skiles 140
Text: Applied Combinatorics with Problem Solving by Jackson and Thoro
Office hours: Skiles 258, Wednesday 3-4, Thursday 2-3 (or drop by)

Important Dates:

• Midterm 1: Wednesday, October 21
  
• Midterm 2: Monday, November 9
  
• Final: Wednesday, December 9 (11:30 - 2:20)
  

(You must tell me now if you anticipate scheduling conflicts with any of the exams!)


Syllabus:

• Combinatorial problem solving Chapter 1, Sections 1.2, 1.4
  
• Basic counting principles Chapter 2
  
• Recurrence relations Chapter 8
  
• Generating functions Chapter 7
  
• Graphs Chapter 5
  
• Graph algorithms and searching Chapter 6
  

(For the complete course outline in postscript form.)

---

Homework 1 (due Friday, October 2)

• Section 1.2: 2, 4, 6, 8, 10, 19, 31
  
• Extra credit: Section 1.1: 18
  

Homework 2 (due Friday, October 9)

• Redo any two induction proofs from homework 1 (or class) as a proof by contradiction :
  (a) Negate the statement
  (b) Prove the negation could not be true.
  
• Section 1.2: 22, 24b, 26 (with proof!)
• Section 1.3: 2, 4, 6, 7

(It might help you with the first problem to look at this handout .)


Homework 3 (due Friday, October 16)

• Section 2.1: 2, 9-12
  
• Section 2.2: 2,3,5,10,16
  
• Review problems from chapter 1 (page 39): 5
  

Homework 4 (due Friday, October 23)
(***Remember the exam is Wednesday -- it will help to do this early!!***)

• Section 2.2: 8, 11
• Section 2.3: 2, 4, 5, 6, 7, 10, 11, 18, 24

Homework 5 (due Friday, October 30)

• Section 2.3: 16, 20
• Section 2.4: 1, 3, 4, 8, 10, 12
• Section 2.5: 2, 4, 8, 18

Homework 6 (due Friday, November 6)
(***Midterm 2 is Monday, November 9!!***)

• Section 2.6: 1, 2.
• Review of chapter 2 (page 85): 4, 6.
• Section 1.4: 4, 6, 9
• Section 7.1: 2, 6, 12, 14

Homework 7 (due Friday, November 13)

• Section 7.2: 2, 4, 8, 16
• Section 7.4: 2, 3, 6, 8, 13

Homework 8 (due Friday, November 20)

• Section 8.1: 3, 4, 6, 14
• Section 8.2: 3, 6, 10, 14
• Section 8.3: 1, 3, 4

Homework 9 (due *Monday*, November 30)

• Prove that the answer you got to problem 6 in section 8.2 is correct using induction.
• Section 8.3: 5, 7
• Section 8 -- Review Problems: 4(a), 8

• Extra Credit: Section 8.3: 15, 16. (Hint: It might help to define two recurrence relations!!)

Homework 10 (You do NOT have to hand this in!!!)

• Section 5.1: 9, 10, 14
• Section 5.3: 1, 4, 12, 14
• Section 5.4: 2, 3, 8