MCD 121 (Mac Donald Hall)
Lectures are on Mondays at 8:30–10:00 and Thursdays at 10:00–11:30.
Here is the (updated) syllabus.
Office hours are Tuesdays and Fridays 10:00–11:30 in room KED B07A (585 King Edward, basement).
The reference for this course is “Ralph Grimaldi, Discrete Combinatorial Mathematics”, 5th edition. Getting your own copy is optional.
[April 22nd] I finished grading your exams and computing your final grades. I also put online the solutions (not very polished nor detailed) of the exam in case you want to have a look.
[April 10th] Solutions to the 4th assignment. An old final exam for the same class, and its solutions (in french, sorry), for practicing.
[April 1st] Solutions to the third assignment and assignment #4 are now online.
[March 17th] The assignment #3 is now online.
[Feb 23rd] Solutions to the second assignment are now online.
[Feb 19th] Another mistake in assignment #2, exercise E: the side length of the square should be 2. Next time I'll write the solutions before giving you the assignment...
[Feb 17th] There was a mistake in assignment #2, exercise B: the relation should be symmetric. Sorry about that. The updated version is online.
[Feb 6th] Solutions to the first assignment and assignment #2 are now online.
[Jan 30th] The box for posting the assignment is open until monday evening. You can also hand them to me directly on monday's lecture.
[Jan 27th] There was a mistake in question D.2 of the assignment: it should be a sum with k varying.
[Jan 26th] My formulation of the last theorem was indeed wrong. More on that next lecture!
[Jan 21st] The first assignment is online.
[Jan 12th] There was a mistake in exercise sheet #1, A.1.3: it should read (B\A) instead of (A\B).
First assignment, due for February 2nd. (solutions)
Second assignment, due for February 23rd. (solutions)
The test was on thurday 26th, during lecture hours. (solutions)
Third assignment, due for March 26th. (solutions)
Fourth and last assignment, due for April 9th. (solutions)
| Lecture | Date | Topic | Exercices | Grimaldi |
|---|---|---|---|---|
| 1 | January 12th | reminder on sets; sum/product principles; arrangements and combinations | #1 | 1.1/1.2: 3, 5, 9, 11, 21, 31, 37 |
| 2 | January 15th | arrangements with types; combinations with repettition | #1 #2 | 1.3: 4, 13, 15, 23, 28 1.4: 1, 3, 7, 16, 18, 23 |
| 3 | January 19th | binomial theorem; examples | #2 #3 | (same as above) |
| 4 | January 22nd | catalan numbers | assignment #1 | |
| 5 | January 26th | functions: bijections, injections, surjections | #4 | 3.1: 5, 6, 9, 13, 18, 27 3.2: 1, 3, 4, 7, 13 |
| 6 | January 29th | functions; induction proofs | #4 #5 | |
| 7 | February 2nd | induction proofs; Stirling numbers | #4 #5 | |
| 8 | February 5th | (getting stuck on) Stirling numbers ; Pidgeonhole principe | assignment #2 | 5.5: 3, 5, 7, 9, 20 |
| 9 | February 9th | Stirling numbers (at last!) ; Inclusion-exclusion principe | #6 | 8.1: 2, 5, 6, 8, 16 |
| 10 | February 23rd | derangements; birthdays paradox; rooks | ||
| 11 | March 2nd | Rook polynomials; generating functions | 9.1: 1,4 | |
| 12 | March 5th | Generating functions; the "equation problem" case | #7 | 9.2: 1,2,5,9,13 |
| 13 | March 9th | Computing generating functions: operations and base cases | #7 #8 | 9.2: 3, 4, 17, 32 9.3: 4 |
| 14 | March 12th | Computing generating functions; the composition problem | #8 | (same as above) |
| 15 | March 16th | The summation operator; decomposing partial fractions | assignment #3 | |
| 16 | March 19th | Identities; exponential generating functions and arrangements | #9 | 9.4: 2, 9, 10 |
| 15 | March 23rd | Exponential generating functions; recurrence relations | #9 | 10.1: 2, 10 ; 10.2: 1, 9, 23 |
| 16 | March 26th | Linear recurrence relations and GF | #9 | 10.3: 1, 5, 7 ; 10.4: 1, 3 |
| 17 | March 30th | Graphs: basic definitions | #9 #10 | 11.1: 2, 3, 6, 7, 9, 15 |
| 18 | April 2nd | Graphs: degree, subgraphs, isomorphism | assignment #4 | |
| 19 | April 9th | Graphs: degrees and Euler trails | #10 | 11.2: 1, 8, 9, 10, 12 |