This is an approximate, provisional schedule. As always, topics may be added, deleted, or rearranged during the course of the semester. Any changes will be announced in class and here.
| Date | Class Topic | Reading (from Brualdi) |
|---|---|---|
| 1/19 | Course introduction -- What is combinatorics? | Chapter 1 |
| 1/21 | What is combinatorics?, continued | Chapter 1 |
| 1/24 | The pigeonhole principle | 2.1 |
| 1/26 | More on the pigeonhole principle | 2.2 |
| 1/28 | Four basic counting principles | 3.1 |
| 1/31 | Permutations and combinations of sets | 3.2,3 |
| 2/2 | Permutations and combinations of multisets | 3.4,5 |
| 2/4 | Listing all permutations or combinations | 4.1,2 |
| 2/7 | Applications | |
| 2/9 | Spare day 1 | |
| 2/11 | Pascal's triangle and the Binomial Theorem | 5.1,2 |
| 2/14 | Identities for binomial coefficients | 5.3, 4 |
| 2/16 | Multinomial coefficients | 5.5, 5.6 |
| 2/18 | Inclusion-exclusion | 6.1,2 |
| 2/21 | Derangements of a set | 6.3 |
| 2/23 | Permutations with forbidden positions (``rook placements'') | 6.4,5 |
| 2/25 | Midterm Exam I | Chapters 1 - 5 |
| 2/28 | More on forbidden positions | 6.5 |
| 3/2 | Additional examples | 6.5 |
| 3/4 | Spare day 2 | |
| 3/7, 9, 11 | No class -- Spring Break | |
| 3/14 | Number sequences and recurrences | 7.1 |
| 3/16 | Solving linear recurrences | 7.2 |
| 3/18 | Solving linear recurrences, cont. | 7.3 |
| 3/21 | Generating functions | 7.4 |
| 3/23 | More on generating functions | 7.5 |
| 3/25, 28 | No class -- Easter Break | |
| 3/30 | Bipartite graphs and matchings | 9.1,2 |
| 4/1 | The ``marriage theorem'' | 9.3,4 |
| 4/4 | General graphs | 11.1 |
| 4/6 | Euler paths | 11.2 |
| 4/8 | Hamilton cycles | 11.3 |
| 4/11 | Trees | 11.5 |
| 4/13 | More on trees | 11.7 |
| 4/15 | Midterm Exam II | Chapters 6,7,9,11 |
| 4/18 | Permutation and symmetry groups | 14.1 |
| 4/20 | More on group actions | 14.1 |
| 4/22 | Burnside's Theorem | 14.2 |
| 4/25 | Polya's counting formula | 14.3 |
| 4/27 | Applications | 14.3 |
| 4/29 | Spare day 3 | |
| 5/2 | Semester wrap-up |
The final exam for this course will be given at 8:30am on Thursday, May 12.
Last modified: January 11, 2005