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.
Friday, January 16: Permutations. Section 3.2.
Wednesday, January 21: Combinations. Permutations of multisets.
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.
Friday, February 27: Bell numbers and Stirling numbers of the first kind.
Monday, March 2: Partition numbers and their generating function.
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.