Topic outline
-
Instructor: Sofia Tirabassi (tirabassi@math.su.se)
Teaching assistant: Yaël Dillies (yael.dillies@math.su.se)Lectures: Every Tuesday and Friday 13:00-13:45 and 14:00-14:45 during HT25
Exercise Sessions: Every Tuesday and Friday 15:00-15:45 during HT25
Official Schedule on Time Edit
Zoom meeting for distance students: Both the lecture and the TA session will happen there.
We might need to close and reopen the meeting between the lecture and the TA sessions so that Sofia can log out from the room computer and Yaël log in.Examiner: Sofia Tirabassi
Examination form: Written
Examination date: TBA
Re-exam date: TBA
Examination Rules at the Department of MathematicsThe course will be given in English.
Textbook: R.P. Grimaldi, Discrete and combinatorial mathematics. An applied introduction, Pearson, fifth edition, ISBN 0-321-21103-0.
Note that the version with ISBN 1-292-02279-5 is of very bad quality and does not include chapter 17.
The textbook is valuable for its many examples, but it lacks the usual definition-theorem structure of mathematical writing.
Therefore Sofia provides a kompendium to help put order in the theory. See below.Video recordings: Previous instructors have put recordings of their lectures in youtube playlists.
There is the 2017 lectures by Benjamin Nill and the 2020 lectures by Boris Shapiro.-
Here you can ask for help in understanding the video and the book. I will go over the questions during the lecture time. If you want me to address the problem on Monday you have to ask before Friday at 12.
-
Here you can ask for help in solving exercises. If you have a question post it here, it is the only way you will get an answer :)
-
These lecture notes help put order in the theory of this course giving it the definition-statement-proof structure. No example are provided because they are covered in the book.
-
Basic counting principles; Functions and the pigeon-hole principle
Reading:
Counting: 1.1 - 1.4,
Basic set theory: 3.1 - 3.2,
Relations and functions: 5.1 - 5.3, 5.5
Videos: “Basic Principles of Counting” & “Functions and the Pidgeonhole Principle”
Lecture recording part 1 (HT22)
Lecture Recording part 1 (HT23)
Lecture recording part 2 (HT23)
Lecture recording H24
Exercises:
1.1+1.2: 10,16,20,22
1.3: 10,12,16,18
1.4: 2,4,8,103.1: 2,9,15
3.2: 4,13,175.3: 8,10,13
5.5: 4,8,10,12,13,20 -
Inclusion-exclusion formulae
Text: 8.1-8.3
Video: "Inclusion Exclusion Principle"
Exercises:
8.1: 4,16,20
8.2: 2,4
8.3: 4,6,10Recordig of lecture (HT23)- just second half
Recording of the lecture (H24)
-
Rook polynomials
Text: 8.4-8.5
Video: "Rook polynomials"
Exercises:
8.4 + 8.5: 4,6,9,10,12 -
Generating functions I and partitions
Text: 9.1-9.3
Video: "Generating functions"
Exercises:
9.2: 8,10,16,30
9.3: 2,3,4,5,10 -
Generating functions II
Text: 9.4-9.5
Video: "Exponential generating functions"
Exercises:
9.4: 2,4,6,7
9.5: 2,4 -
Recursions I
Text: 10.1-10.2
Video: "Homogeneous recurrence relations"
Exercises:
10.1: 2
10.2: 4,9,11,12,13,14,24, 26, 28 -
Recursions II
Text: 10.3-10.4
Video: "Non-homogeneous recurrence relations"
Lecture video(I forgot to stop the recording, so there will be a 15 minutes break in the middle)
Exercises:
10.3: 2,8,12
10.4: 1 -
Graphs I
Text: 11.1-11.2
Video: "Basics of graph theory"
Exercises:
11.1: 2,4,6,10,14
11.2: 2,6,8,10,12 -
Lecture Part 1 - unfortunately I completely forgot to press the "record button" the good news is that all the material in the first part of the lecture was more or less straightforward from the book and without any proof. I apologize for the mistake
Lecture Part 2 -
Graphs II
Text: 11.3-11.4
Video: "Planar graphs"
Lecture video (I forgot to stop the recording midways)
Exercises:
11.3: 1,2,4,6,8,10,20,22,24
11.4: 2,6,8,10,12,14,18,19,21,22 -
Graphs III
Text: 11.5 - 11.6
Video: "Hamilton paths"
Exercises:
11.5: 2,6,8,10,12,18
11.6: 2,4,6,8,9,10,14,15,16 -
Trees
Text: 12.1-12.2
Video: unfortunately no video is available from SU. Here is another link to YouTube.
Exercises:
12.1: 2,3,4,5,6,7,8,10,12,16,18
12.2: 1,7,8,10,16,17 -
Combinatorial optimization
Text: 13.1-13.2
Exercises:
13.1: 2,3
13.2: 1,2,4 -
Video part 1 https://youtu.be/gUJuc1d594E
Video part 2 https://youtu.be/WbOSJ8IlWgQ
-
Online lesson starts at 9:30 and we go forward without pause. Sorry for that.
Combinatorial optimisation II
Text: 13.3
Exercises:
13.3: 1,4,6,7 (find in 4 also the corresponding minimal cut), you can try to start with a flow with large flow value -
Finite geometry
Text: Lecture notes
Alternative text: Course book chapters 17.3–17.4
Exercises:
17.3: 1, 4, 5
17.4: 3, 5, 6Due to some issues, exercise session will be at 6 pm.
-
Review! No new material
Lecture video part 1
Lecture video part 2
Hello!
Thanks to all thos who have connected today. It was impossible to record due to way to many technical problems that occurred.
Thank you for a great )half) semester. Get rested!!! And see you at the exam -
Grade scale
<15 F
15-17.99 E
18-20.99 D
21-23.99 C
24-26.99 B
27+ A