Fall 2005 Math 413 Combinatorics Class Log

1. Aug 24, Wed. course overview and logistics; Sec 1.2: cutting a cube and fault-lines in perfect covers of chessboards; Sec 1.7: the game of Nim
2. Aug 26, Fri. Sec 1.1: perfect covers of chessboards by dominoes; Sec 1.5: Latin squares
3. Aug 29, Mon. Sec 2.1: the Pigeonhole Principle and applications
4. Aug 31, Wed. Sec 2.2: the strong form of the Pigeonhole Principle; Erdos-Szekeres theorem; Quiz 1; averaging principle and example
5. Sep 2, Fri. basic probabilistic method; Sec 2.3: Ramsey's theorem
Sep 5, Mon. Labor Day - no class
6. Sep 7, Wed. proof of Ramsey's theorem; Quiz 2; Sec 3.1: basic counting principles
7. Sep 9, Fri. Sec 3.2: permutations; Sec 3.3: combinations; Sec 3.4: permutations of multisets
8. Sep 12, Mon. Sec 3.5: combinations of multisets; Sec 5.1: binomial coefficients and Pascal's triangle
9. Sep 14, Wed. lattice path problems; Quiz 3; Sec 5.2: binomial theorem
10. Sep 16, Fri. Sec 5.3: identities involving binomial coefficients
11. Sep 19, Mon. Sec 5.4: unimodality of the binomial coefficients; Sec 5.5: multinomial coefficients and the multinomial theorem; proof of Fermat's Little Theorem; Sec 5.6: extended binomial coefficients and binomial theorem
12. Sep 21, Wed. infinite geometric series; Sec 4.5: relations; posets; diagrams of posets
13. Sep 23, Fri. Test 1
14. Sep 26, Mon. Sec 5.4: Sperner's theorem; Sec 5.7: partition of poset into antichains
15. Sep 28, Wed. Dilworth's theorem; approximations to n! and Stirling's formula; Sec 6.1: example of inclusion and exclusion
16. Sep 30, Fri. Sec 6.1: inclusion-exclusion; Sec 6.2: combinations with fixed repetition; Quiz 4
17. Oct 3, Mon. Sec 6.3: derangements; counting; recurrence relation; Sec 6.4: permutations with forbidden positions; relation to rook placement
18. Oct 5, Wed. counting permutations with forbidden positions; Sec 6.5: permutations with forbidden relative positions; Quiz 5
19. Oct 7, Fri. Sec 7.1: number sequences, recurrence relations, Fibonacci sequence, properties
20. Oct 10, Mon. more properties of the Fibonacci sequence; Sec 7.2: linear homogeneous recurrence relations with constant coefficients
21. Oct 12, Wed. repeated roots of the characteristic equation; Sec 7.3: linear nonhomogeneous recurrence relations; Quiz 6
22. Oct 14, Fri. examples of linear nonhomogeneous recurrence relations; Sec 7.5: solving recurrences with generating functions
23. Oct 17, Mon. Sec 7.4: combinatorial interpretation of generating functions
24. Oct 19, Wed. more on ordinary generating functions; Sec 7.7: exponential generating functions
25. Oct 21, Fri. Test 2
26. Oct 24, Mon. more on exponential generating functions; number of n-permutations of a multiset with finite repetition
27. Oct 26, Wed. Sec 7.6: number of diagonal placements in a convex n-gon; Quiz 7
28. Oct 28, Fri. Sec 8.1: Catalan numbers; formula, recurrence, and bijection
29. Oct 31, Mon. pseudo-Catalan numbers; recurrence; Sec 8.2: difference sequences; difference sequences of sequences with a polynomial formula
30. Nov 2, Wed. Stirling numbers of the second kind; Quiz 8
31. Nov 4, Fri. combinatorial interpretation of Stirling numbers; Bell numbers
32. Nov 7, Mon. Stirling numbers of the first kind; recurrence and combinatorial interpretation; review of putting objects in boxes
33. Nov 9, Wed. Sec 8.3: partition numbers; generating functions; estimates; Quiz 9
34. Nov 11, Fri. Ferrers diagrams; triangular numbers; Euler's identity
35. Nov 14, Mon. Bulgarian solitaire; periodic cycles
36. Nov 16, Wed. Sec 8.3: counting regions formed by hyperplanes; a generating function identity involving lattice paths
37. Nov 18, Fri. Test 3
Nov 21, Mon. - Nov 25, Fri. Thanksgiving break - no class
38. Nov 28, Mon. Sec 10.1: modular arithmetic; computing multiplicative inverses mod n
39. Nov 30, Wed. construction of finite fields; Sec 10.2: block designs
40. Dec 2, Fri. parameters of block designs; relationships; Fisher's inequality
41. Dec 5, Mon. symmetric block designs; construction of symmetric block designs from difference sets; Sec 10.3: Steiner triple systems
42. Dec 7, Wed. construction of larger Steiner triple systems; Sec 10.4: Latin squares; circulant Latin squares Quiz 10
43. Dec 9, Fri. orthogonal Latin squares; existence
Dec 16, Fri. Final Exam, 1:30pm-4:30pm, Altgeld Hall Room 141

    Back This page last modified .