Math 465: Introduction to Combinatorics

Fall 2013

Course meets: Monday and Wednesday 4:10-5:30 PM in B844 East Hall.

Instructor: Sergey Fomin, 4868 East Hall, 764-6297,

Office hours: Monday 5:40-7:00 PM and Thursday 11:40 AM-1:00 PM in 4868 East Hall.

Grader: Noah Shutty,

Course homepage:

Level: undergraduate.

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.

Student work expected: several problem sets.

Grade will be based on two 1.5-hour midterm exams, 25% each; and 50% homework. Your lowest homework set score will be dropped.

Exams will be held in the same room where the class meets. Dates of exams: October 28 and December 11.

This course will not be graded on a curve, i.e., there are not a set percentage of each grade to be given out. Every student with the total score of 90% (resp., 80%, 70%, 60%) is guaranteed the final grade of A (resp., B or higher, C or higher, D or higher).

Synopsis: This course introduces the fundamental notions, techniques, and theorems of enumerative combinatorics and graph theory.

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: M. Aigner, Discrete Mathematics, American Mathematical Society, 2007.
Where can I buy this book?

Other introductory textbooks:
M. Bóna, A walk through combinatorics, 3nd edition, World Scientific, 2011.
R. Brualdi, Introductory combinatorics, 5th edition, Pearson Prentice Hall, 2010.

More advanced undergraduate textbooks:
J. H. van Lint and R. M. Wilson, A course in combinatorics, 2nd edition, Cambridge University Press, 2001.
J. Matoušek and J. Nešetřil, Invitation to discrete mathematics, 2nd edition, Oxford University Press, 2008.

Lectures (tentative plan)

  1. The pigeonhole principle. The Erdös-Szekeres Theorem.
  2. Basic Ramsey Theory. Fundamental counting principles.
  3. Counting subsets and permutations. Binomial coefficients.
  4. Multinomial coefficients. Basic binomial identities.
  5. Finite difference operators.
  6. Binomial theorem and its generalizations.
  7. Generating functions. Multiplication principle for generating functions.
  8. Stirling numbers.
  9. Linear recurrences with constant coefficients: simple roots. Fibonacci numbers.
  10. Linear recurrences with constant coefficients: multiple roots, non-homogeneous recurrences.
  11. Catalan numbers.
  12. Integer partitions.
  13. Inclusion-exclusion principle. Derangements. Permutations with restricted positions.
  14. Applications of inclusion-exclusion.
  15. First midterm exam.
  16. Basic notions of graph theory. Trees. Independent cycles.
  17. Planar graphs. Euler's formula. Hamiltonian cycles.
  18. Eulerian paths and circuits.
  19. Chromatic number and chromatic polynomial.
  20. Minimal spanning trees.
  21. Shortest paths.
  22. Flows in networks. The Ford-Fulkerson algorithm.
  23. Menger's theorems. Bipartite networks. Hall's theorem.
  24. Birkhoff's theorem. Partially ordered sets.
  25. Chains and antichains. Minimal chain/antichain decompositions.
  26. Sperner's theorem. Symmetric chain decompositions.
  27. Review session.
  28. Second midterm exam.