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