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

    Back This page last modified .