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

Office hours: Tu 3-4pm, Th 11am-12pm, F 1-2pm in DRL 4E2B.
Office Phone: 215-573-9093

Lecture: MWF 2-3pm in DRLB 3C2

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 "Discrete and Combinatorial Mathematics" by R. P. Grimaldi, Fifth Edition, available in the Penn bookstore. After an introduction to principles of counting (Part 1 Chapter 1) we will cover most of parts 2 and 3. A suppplementary text is "Applied Combinatorics" by Alan Tucker, which is on reserve in the Math/Physics Library in DRL 3N1.

Exams and Grades: There will be two hour exams and a final exam. Each hour exam counts 25% of your grade, and the final exam counts 40%. HW counts 10%. Hour exam 1 will be on Monday, Oct. 8 during lecture, and Hour exam 2 will be on Monday, Nov. 12, during lecture. The final exam is Friday, Dec. 14 from 6pm-8pm.

Midterm 1: Covers

Midterm 2: Covers sections 10.1-10.5, 11.1-11.6, 12.1, counting rooted, ordered trees or rooted, labelled trees, 13.4. In theory, some questions could also involve topics from rook polynomials covered earlier in the course.

Final Exam Cummulative. Covers

Important Dates:
Midterm 1: Oct. 8, 2-3pm
Last Day to Drop a Course: Friday, Oct. 12
Fall Break: Saturday, Oct. 13 - Tuesday, Oct.16.
Midterm 2: Nov. 12, 2-3pm
Thanksgiving Break : Thursday, Nov. 22 - Sunday. Nov. 25
Last Day of Class: Friday, Dec. 7
Final Exam: Friday, Dec. 14 from 6:00pm-8:00pm in DRLB 4C4.

Homework Assignments:
HW1 (due Monday, 9/17) From book: 4.1.1 b,c,d; 4.1.2 b,c; 4.1.12; 1.2.6; 1.2.10, 1.2.37; 1.3.8; 1.3.14; 1.3.26.
HW2 (due Monday, 9/24) From book: 1.4.8, 1.4.18, 1.4.28, 1.5.11, 5.5.6. Also, prove the n-th Catalan number counts the number of non-crossing set partitions of an n-element set (as defined in class).
HW3 (due Monday, 10/1)
Show that there is a way to connect 15 computers to 10 printers using 60 connections, so that any subset of 10 computers is connected to at least 10 printers.
Also, evaluate the sum, k going from 1 to n, of
(n)(n+1)...(n+k-1)S(n,k)(-1)^k,
where S(n,k) is the Stirling number of the second kind.
Finally, do the following problems from the book: 8.1.2, 8.1.8, 8.1.13, 8.1.16, 8.1.20, 8.2.1, 8.2.6.
HW4 (due Wednesday, 10/17)
Do problems 9.1.4, 9.1.6, 9.2.4, 9.2.6, 9.2.14, 9.2.18, 9.2.24, 9.3.8, and 9.4.6 (b) from the book.
HW5 (due Monday, 11/5)
Do problems 10.1.4, 10.2.10, 10.2.24, 10.3.8, 10.3.14, 10.4.3, 10.7.14, 10.7.28, 11.1.12, 11.2.4, 11.2.16, and 11.3.20 from the book.
HW6 (due Friday, 12/14, just before the final exam)
Do problems 17.3.6, 17.3.8, 17.4.4, 17.5.6, 17.6.8, 17.6.9, 17.6.10, 17.6.11 from the book.