Math 465 Fall 2014
Introduction to Combinatorics

Lectures: TTh 1-2:30 in 2218 SEB (School of Education Building)

Instructor: Thomas Lam, 2834 East Hall,

Office Hours: TBA.

Grader: Lian Mo,

Course Homepage:

Prerequisites: Linear algebra (Math 214, 217, 256, 286, 296, 417, 419, or equivalent) or permission of instructor.

This is a proof-based course: students are expected to understand rigorous mathematical proofs, and supply their own proofs on exams, quizzes, and in homework solutions.

Grading: There will be several problem sets, worth 50% of the grade. There will be two 1.5 hour exams, worth 25% each.

Exams: Exams are held in class, at the same time and place of the lectures. Dates of exams: October 23 and December 4.

Synopsis: This course introduces the fundamental notions, techniques, and theorems of enumerative combinatorics and graph theory. The first half of the course will focus on the former, and the second half on the latter.

Background: Combinatorics is the study of finite mathematical objects, including their enumeration, structural properties, design, and optimization. Combinatorics plays an increasingly important role in various branches of mathematics and in numerous applications, including computer science, statistics and statistical physics, operations research, bioinformatics, and electrical engineering.

Textbook: J. Matoušek and J. Nešetřil, Invitation to discrete mathematics, 2nd edition, Oxford University Press, 2008.
Errata to the book.

Other reference books:
M. Bóna, A walk through combinatorics, 3nd edition, World Scientific, 2011.
R. Brualdi, Introductory combinatorics, 5th edition, Pearson Prentice Hall, 2010.
J. H. van Lint and R. M. Wilson, A course in combinatorics, 2nd edition, Cambridge University Press, 2001.
M. Aigner, Discrete Mathematics, American Mathematical Society, 2007.

Information about the midterm:
The First Midterm covers all material up to and including the lecture given on October 21.
The exam is open book: you may bring your textbook and your notes.
There are 8 problems on the exam. The exam will be 80 minutes long. Each problem is worth 4 points. The exam is out of 30 points.

Tentative list of topics:

  1. Pigeonhole principle.
  2. Basic counting techniques and bijections.
  3. Subsets, permutations, and binomial coefficients.
  4. Multinomial coefficients.
  5. Generating functions.
  6. Stirling numbers.
  7. Fibonacci numbers.
  8. Linear recurrences.
  9. Inclusion-exclusion principle.
  10. Catalan numbers.
  11. Partition and compositions.
  12. Ramsey theory.
  13. Graphs and trees.
  14. Planar graphs.
  15. Paths and circuits.
  16. Spanning trees.
  17. Chromatic number and polynomial.
  18. Tutte polynomial.
  19. Partially ordered sets.
  20. Sperner's theorem. Dilworth's theorem.