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