Math 456 FALL 2009, List of lectures

  • On this page I will post content of all lectures. All handouts also will be posted here.
  • Monday, January 5: Examples of combinatorial problems. Chapter 1.
  • Wednesday, January 7: The Pigeonhole Principle. Section 2.1. Please find your homework.
  • Friday, January 9: Strong form of the pigeonhole principle. Section 2.2.
  • Monday, January 12: Ramsey theory. Section 2.3.
  • Wednesday, January 14: Four counting principles. Section 3.1. New homework.
  • Friday, January 16: Permutations. Section 3.2.
  • Wednesday, January 21: Combinations. Permutations of multisets. Sections 3.3-3.4.
  • Friday, January 23: Combinations of multisets. Section 3.5. New homework (due on Friday!).
  • Monday, January 26: Pascal triangle, binomial theorem and identities for binomial coefficients. Sections 5.1-5.3.
  • Wednesday, January 28: Unimodality for binomial coefficients, Sperner's theorem. Section 5.4.
  • Friday, January 30: Multinomial theorem, general binomial theorem. Sections 5.5-5.6. New homework (due on Friday!).
  • Monday, February 2: The Inclusion-Exclusion principle. Section 6.1.
  • Wednesday, February 4: Combinations with repetitions. Section 6.2.
  • Friday, February 6: Derangements. Section 6.3.
  • Monday, February 9: Examples of recurrence relations. Section 7.1
  • Wednesday, February 11: Linear homogeneous relations with constant coefficients. Section 7.2.
  • Friday, February 13: MIDTERM.
  • Monday, February 16: Linear homogeneous relations with constant coefficients: case of multiple roots. Section 7.2.
  • Wednesday, February 18: Nonhomogeneous recurrence relations. Generating functions. Sections 7.3-7.4. New homework (due next Wednesday).
  • Friday, February 20: More on generating functions. Section 7.4.
  • Monday, February 23: Catalan numbers. Sections 7.6, 8.1.
  • Wednesday, February 25: Stirling numbers of the second kind. Section 8.2. New homework
  • Friday, February 27: Bell numbers and Stirling numbers of the first kind. Section 8.2.
  • Monday, March 2: Partition numbers and their generating function. Section 8.3.
  • Wednesday, March 4: Graphs. Section 11.1.
  • Friday, March 6: Eulerian trails in graphs. Section 11.2.
  • Monday, March 9: Trees. Section 11.5.
  • Wednesday, March 11: Euler formula and planar graphs. Section 13.2.
  • Friday, March 13: A 5-color theorem. Section 13.3.
  • Final Exam.
  • THE END