## MAT2348 Discrete Mathematics (winter 2015)

MCD 121 (Mac Donald Hall)

### Lectures

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.

### News

• [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.

• [March 5th] The test and its solutions are 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).

### Summary of lectures

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