**Math 340, Fall 2019**

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

There will be periodic HW assignments to be turned in and graded. The assignments will be posted at the bottom of this web page.

**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.