Math 3012 (Combinatorics), Fall 1998

Course Outline

Lectures: MWF 2, Room Skiles 140

Text:Applied Combinatorics with Problem Solvingby 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:

(For the complete course outline in postscript form.)

- 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

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)

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

- Redo any two
induction proofsfrom homework 1 (or class) as aproof 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

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