Dr. Jim Haglund, jhaglund@math.upenn.edu
Course webpage: http://www.math.upenn.edu/~jhaglund/340/

Office hours: M 9-9:50am and W 10:30-11:30am in DRL 4E2B.
Office Phone: 215-573-9093

Office hours (up to Dec. 13): M 9-9:50am and W 10:30-11:30am in DRL 4E2B.

Office hours (week of Dec. 16): M 9-9:50am and T 10:30-11:30am in DRL 4E2B.

Grader: Logan Crew, crewl@sas.upenn.edu

Grader's Office hours: Thursday 1:00-1:50pm in DRL 3N2B.

Lecture: TR 3:00-4:20pm in DRL 3W2

Course : Discrete Mathematics I. This course is meant to be an introduction to Combinatorics. Topics will be drawn from some subjects in combinatorial analysis with applications to many other branches of math and science: Specific topics to be covered include

Proof techniques such as mathematical induction
Binomial Theorem. Permutations and binomial coefficients
Generating Functions
Partitions
Pigeonhole Principle
Basic Discrete Probability
Inclusion-Exclusion
Stirling Numbers
Rook Polynomials
Recurrence Relations
Intro to Graph Theory (planar graphs, Hamilton paths and cycles, chromatic polynomials)
Trees
Optimization and Matching

Text: The text for this course is "Applied Combinatorics", 6th edition, by Alan Tucker, available at the Penn bookstore.

Exams and Grades: There will be two midterm exams and a final exam. Each midterm exam counts 25% of your grade, and the final exam counts 40%. HW counts 10%. Midterm 1 will be on Thursday, Oct. 3 from 3-4:20pm in DRL 3W2 and Midterm 2 will be on Thursday, Nov. 14 from 3-4:20pm in DRL 3W2. The (cummulative) final exam will be on Wednesday, Dec. 18 from 12-2pm in DRLB A6.

Midterm 1: The exam will be a closed book exam. No notes, calculators, cell phones, etc. will be allowed. The exam covers sections 5.1-5.5, 6.1-6.5, 7.1 and Appendix A.2 from the book (combinatorics of permutations and arrangements, binomial coefficients and the binomial theorem, compositions, partitions, generating functions, exponential generating functions, recurrence relations and mathematical induction).

Midterm 2: The exam will be a closed book exam. No notes, calculators, cell phones, etc. will be allowed. The exam covers sections 7.1-7.5 and 8.1-8.3 from Tucker's Applied Combinatorics, 6th Edition. Topics include Solving Recurrence Relations by various methods, Counting with Venn Diagrams, Inclusion-Exclusion, and Rook Polynomials.

Final Exam Cummulative. Students are allowed a cheat sheet of (handwritten) notes, on both sides of a standard 8.5" by 11" sheet of notebook paper. No other books or calculators, cell phones, etc. are allowed. The exam covers sections 1.1-1.4, 2.1-2.4, 3.1-3.2, 5.1-5.5, 6.1-6.5, 7.1-7.5, 8.1-8.3 and Appendix A.2 from Tucker's Applied Combinatorics, sixth edition.

Lecture Notes:
Notes Lectures 1,2,3 and 4
Notes Lectures 5 and 6
Notes Lectures 7 and 8
Notes Lectures 9 and 10
Notes Lecture 11
Notes Lecture 12
Notes Lectures 13 and 14
Notes Lectures 15 and 16
Notes Lectures 17 and 18
Notes Lectures 19 and 20
Notes Lecture 21
Notes Lectures 22, 23, and 24
Notes Lectures 25 and 26

Important Dates:
Tuesday, August 27: Classes begin
Midterm 1: Thursday, Oct. 3 from 3:00-4:20pm in DRL 3W2
Last Day to Drop a Course: Oct. 7
Fall Break: Thursday, Oct. 10-Sunday, Oct. 13
Last Day to Withdraw from a course: Nov. 4
Midterm 2: Thursday, Nov. 14 from 3:00-4:20pm in DRL 3W2
Thanksgiving Break : Thursday, Nov. 28 - Sunday, Dec. 1
Last Day of Classes: Monday, Dec. 9
Final Exam: Wednesday, Dec. 18 from 12-2pm in DRLB A6

Homework Assignments:

HW1 (due Tuesday, 9/17 - hand in during lecture. Show all work, so for odd numbered exercises, although you can find the answers in the back of the book, you must still demonstrate the reasoning behind the answer). From book:
Section 5.1: Exercises 3, 6, 11, 18, 26, 29, 41,
Section 5.2: Exercises 3, 8, 13, 23, 28,
Section 5.3: Exercises 5, 8, 15, 23, 24,
Section 5.4: Exercises 5, 13, 20, 34.

HW2 (due Tuesday, 10/1 - hand in during lecture. Show all work, so for odd numbered exercises, although you can find the answers in the back of the book, you must still demonstrate the reasoning behind the answer). From book:
Section 5.5: Exercises 1, 12, 15, 21.
Section 6.1: Exercises 3, 8, 12, 27.
Section 6.2: Exercises 5, 11, 17, 28.
Section 6.3: Exercises 3, 12, 15, 17, 22.
Section 6.4: Exercises 3, 7, 10.

HW3 (due Tuesday, 10/29 - hand in during lecture. Show all work, so for odd numbered exercises, although you can find the answers in the back of the book, you must still demonstrate the reasoning behind the answer). From book:
Section 7.1: Exercises 4, 7, 8, 12, 21.
Section 7.2: Exercises 1, 3, 8.
Section 7.3: Exercises 2, 5, 11.
Section 7.4: Exercises 3, 9, 18.
Section 7.5: Exercises 3, 9, 11.

HW4 (due Tuesday, 11/12 - hand in during lecture. Show all work, so for odd numbered exercises, although you can find the answers in the back of the book, you must still demonstrate the reasoning behind the answer). From book:
Section 8.1: Exercises 5, 11, 16, 28, 34.
Section 8.2: Exercises 1, 4, 6, 17.
Section 8.3: Exercises 2, 6, 10, 15.
(Also, for a Special Challenge Problem, try 8.2 #30, due 11/19)

HW5 (Recommended Problems - not to be turned in, but should be helpful in preparing for the final exam) From book:
Section 1.1: 7, 8, 9, 10.
Section 1.2: 5, 8, 10, 11.
Section 1.3: 3, 5, 10, 16.
Section 1.4: 6, 8, 15, 17.
Section 2.1: 7, 8, 9, 10, 12 (c).
Section 2.2: 3, 4, 7, 8.
Section 2.3: 1, 3, 8.
Section 2.4: 2, 3, 5, 8.
Section 3.1: 2, 5, 11, 13.
Section 3.2: 1, 2, 7, 8.