#### Combinatorics Math 450 Fall 2007 Section 001 Class Log

 1. Aug 27, Mon. course overview and logistics; Sec 1.2: tilings of chessboards; Sec 1.7: the game of Nim 2. Aug 29, Wed. finished game of Nim; Sec 3.1-3.2: started Worksheet 1 3. Aug 31, Fri. Sec 3.3-3.4: continued Worksheet 1 Sept 3, Mon. Labor Day -- no class 4. Sept 5, Wed. Sec 3.5: finished Worksheet 1; Sec 5.1: properties of binomial coefficients; Pascal's identity; Sec 5.2: binomial theorem; combinatorial and algebraic proofs; 5. Sept 7, Fri. Sec 5.5: multinomial theorem; proof of Fermat's Little Theorem 6. Sept 10, Mon. Sec 5.3: binomial identities; committee-chair identity; weighted sums; use of differentiation 7. Sept 12, Wed. Sec 5.4: unimodality of binomial coefficients; comments on induction; Sec 4.5: relations: equivalence relations and orders 8. Sept 14, Fri. posets; Boolean lattice; antichains and chains; Sperner theorem; symmetric chain decomposition 9. Sept 17, Mon. more on symmetric chain decomposition; Sec 5.7: chains and antichains; decomposing a poset into antichains 10. Sept 19, Wed. Dilworth theorem; Sec 6.1: principle of inclusion-exclusion 11. Sept 21, Fri. applications of inclusion-exclusion; Sec 6.3: derangements; Sec 6.2: combinations of multisets with finite repetition 12. Sept 24, Mon. Sec 6.4: permutations with forbidden positions; Sec 6.5: permutations with a different constraint 13. Sept 26, Wed. discussion about Homework 5; Sec 7.1: recurrence relations; regions determined by circles; tiling nx2 chessboard with dominoes; Fibonacci recurrence 14. Sept 28, Fri. some properties of Fibonacci numbers; induction; use of recurrence; deriving a formula for fn 15. Oct 1, Mon. Sec 7.2: solving linear homogeneous recurrences with constant coefficients; distinct roots and repeated roots; Sec 7.3: Towers of Hanoi 16. Oct 3, Wed. solving linear nonhomogeneous recurrences with constant coefficients; Sec 7.4: generating functions 17. Oct 5, Fri. Test 1 18. Oct 8, Mon. making change; Sec 7.5: solving recurrences with generating functions; example with repeated roots of characteristic equation 19. Oct 10, Wed. equivalance between generating function and characteristic equation methods for homogeneous linear recurrence relations with constant coefficients; solving nonhomogeneous linear recurrence relations with generating functions; generating function for h_n=n 20. Oct 12, Fri. Sec 7.6: number of triangulations of convex polygon with n+1 sides; generating function; Taylor series for sqrt(1+x); Catalan numbers 21. Oct 15, Mon. returned Test 1; Sec 8.1: Catalan numbers; lattice paths; reflection principle 22. Oct 17, Wed. pseudo-Catalan numbers; multiplication schemes; Sec 7.7: exponential generating functions 23. Oct 19, Fri. permutations of a multiset; use of exponential generating functions; informal feedback survey Oct 22, Mon. Fall Break -- no class 24. Oct 24, Wed. informal feedback survey summary; The Twelvefold Way; Sec 8.2: Stirling numbers of the second kind; recurrence; Bell numbers 25. Oct 26, Fri. recurrence for Bell numbers; formula for Stirling numbers; sequences and difference operator; analogy to functions and differential operator; applying difference operator to sequence defined by a polynomial eventually gives 0 sequence 26. Oct 29, Mon. reconstructing polynomial for sequence from 0th diagonal; partial sums; n^p as a linear combination of [n]_k; Stirling numbers of the second kind 27. Oct 31, Wed. [n]_k as a linear combination of n^p; Stirling numbers of the first kind; combinatorial interpretation; Sec 8.3: partitions of an integer 28. Nov 2, Fri. Test 2 29. Nov 5, Mon. generating function for partitions; Ferrers diagram; conjugate partitions; # of partitions into odd parts = # of partitions into distinct parts 30. Nov 7, Wed. asymptotics of partition number; Euler's first identity and self-conjugate partitions; Bulgarian solitaire 31. Nov 9, Fri. Sec 2.1: Pigeonhole Principle; applications: subset sums; chessmaster; Chinese Remainder Thm; Sec 2.2: stronger form of Pigeonhole Principle 32. Nov 12, Mon. Erdos-Szekeres Thm; colored disks and averaging; probabilistic method; first moment method; lower bound on independence number of a graph 33. Nov 14, Wed. Sec 2.3: Ramsey Thm; diagonal Ramsey numbers; upper bound from thm; lower bound from basic probabilistic method 34. Nov 16, Fri. Ramsey numbers; recurrence; more colors; Ramsey Thm for t-uniform hypergraphs 35. Nov 19, Mon. Happy End Problem; square-free strings and Thue-Morse string; Van der Waerden Thm Nov 21-23 Thanksgiving Break -- no class 36. Nov 26, Mon. review of First Moment Method; finished proof of Van der Waerden Thm 37. Nov 28, Wed. Sec 10.1: Z mod n; finite fields; division algorithm; Euclidean algorithm; construction of finite fields of prime power order 38. Nov 30, Fri. discussion of intersecting families; finished finite fields; evaluations 39. Dec 3, Mon. Sec 10.2: block designs; parameters; incomplete block designs; number of blocks each element is contained in; Fisher's inequality 40. Dec 5, Wed. example; symmetric block designs; construction using difference sets 41. Dec 7, Fri. Test 3 42. Dec 10, Mon. returned Test 3; discussed final exam; dual of symmetric design is a design 43. Dec 12, Wed. Sec 10.3: Steiner Triple Systems; divisibility conditions; construction; affine geometry; projective geometry 44. Dec 14, Fri. finite projective planes; examples; Fano plane Dec 18, Tues, 10am-noon. Final Exam