Math 145: Combinatorics, Winter 2009

Instructor: Brant Jones
Email: brant at math dot ucdavis dot edu
Office: Mathematical Sciences Building 3147
Office hours: Monday noon - 1:00 pm and Wednesday 3:00 - 4:00 pm in MSB 3147, or by appointment.
Class meetings: MWF 2:10 pm - 3:00 pm in Hutchison Hall Room 115
Class webpage: http://www.math.ucdavis.edu/~brant/145/
TA: Ben Fineman (fineman at math dot ucdavis dot edu)
TA Office hours: Tuesday noon - 1:00 pm and Thursday noon - 1:00 pm in MSB 3123.
Final exam: Thursday Mar. 19, 3:30 pm - 5:30 pm in our usual room.

The final grades have been posted, and solutions to the final exam are available. I thank each of you for all of your hard work this quarter!

The final exam is scheduled for March 19. As we discussed in lecture, the exam will cover all of the post-midterm graph theory material with the following exceptions:

• Adjacency matrix / generating functions for walks on a directed graph.
• Prufer codes / Cayley's Theorem.
• TSP and the tree-shortcut algorithm.
• Four color theorem.

The midterm exam is scheduled for February 9. The exam will cover Chapters 1-4 from the book and homeworks 1-3, as well as the lecture material. The exam will focus on the main proof techniques we have learned (Bijections, Induction, Inclusion-Exclusion, Pigeonhole Principle, Generating Functions) and you should be able to carefully write a standard argument using these. Some review problems from the book (that I am not collecting, but I am happy to talk about) are: 1.8.26, 2.5.1, 2.5.7, 3.8.11, 4.3.10.

Our TA Ben Fineman has offered some general feedback about homework:

• Try to be careful about all the details of your arguments, such as the base case of an induction.
• Try to streamline your proofs, so that they do not contain unnecessary statements that just talk around the problem. Every sentence in your proof should advance the argument.
• An example is not a proof. You must give an argument that does not rely on specific choices or constructions. Your argument should use only the hypotheses given in the problem.
• If you use TeX, you might consider adding a page of handwritten figures, or learning some of the LaTeX environments for drawing. Often a diagram or drawing can help explain the argument concisely and precisely without having to introduce new notation that might be ambiguous.

January 5:	Discuss 1.1-1.3.
January 7:	Discuss 1.4-1.6.
January 9:	Discuss 1.7-1.8.
January 12:	Homework 1 (solutions) due! Discuss 2.1-2.2.
January 14:	Discuss 2.3-2.4.
January 16:	Discuss 2.5.
January 19:	No class.
January 21:	Homework 2 (solutions) due! Discuss 3.1 - 3.3 and generating functions.
January 23:	Discuss 3.4 - 3.7.
January 26:	Discuss 3.8, 5.3.
January 28:	Discuss 4.1, 4.3, and using generating functions to solve recurrences (see also generatingfunctionology Ch. 1).
January 30:	Discuss 4.2.
February 2:	Homework 3 (solutions) due! Discuss 7.1 - 7.2.
February 4:	Discuss 7.3.
February 6:	Discuss 7.3.
February 9:	Midterm exam.
February 11:	Discuss the adjacency matrix of a graph.
February 13:	Discuss 8.1 - 8.2.
February 16:	No class.
February 18:	Discuss 8.3 - 8.5.
February 20:	Homework 4 (solutions) due! (Note: For problems 1-3, the term "graph" means undirected simple graph without loops.) Discuss 9.1.
February 23:	Discuss 9.2.
February 25:	Discuss 10.1 - 10.3.
February 27:	Discuss 10.3.
March 2:	Discuss 10.4.
March 4:	Homework 5 (solutions)due!. Discuss the stable marriage problem.
March 6:	Discuss 11.3 (The happy ending problem).
March 9:	Discuss 12.1 - 12.2.
March 11:	Discuss 13.2 - 13.3.
March 13:	Discuss 13.4.
March 16:	Homework 6 (solutions) due! Review for final exam.

This class is an introduction to Combinatorics. Over the course of the quarter, we'll discuss methods for counting sets of discrete structures with finitely many objects, such as graphs and trees. The course will also develop skills in problem solving and proof writing. The required text Discrete Mathematics: Elementary and Beyond by Lovász, Pelikán, and Vesztergombi is available at the University Bookstore.

There are no formal prerequisites for this class, but students should be prepared to work on constructing logical arguments (proofs) and writing them carefully. In particular, this course will not focus very much on memorizing a set of standard formulas or techniques, which may be different from other math courses you have taken. Rather, the goal of the course is to develop problem-solving skills that can be used in many mathematical settings.

There are several components to the grade you will receive in this class:

• Homework will be assigned periodically, and is worth 40% of your grade. Most of the problems will be from the text. These problems will be good study material for the exams. Doing the homework is very important so that you can practice using the results that we learn in this class by solving problems. Late homework will not be accepted for grading however.
• One midterm exam will be given in class, and is worth 30% of your grade.
• One final exam will be given during exam week, and is worth 30% of your grade.

No books, notes or calculating devices will be allowed during the exams. There will be no exam makeups.

Any student with a documented disability (e.g. physical, learning, psychiatric, vision, hearing, etc.) who needs to arrange reasonable accommodations must contact the Student Disability Center (SDC). Faculty are authorized to provide only the accommodations requested by the SDC. If you have any questions, please contact the SDC at 530/752-3184 or sdc@ucdavis.edu."

Topics covered in Math 145
Time schedule page for 145