MATH 239: Introduction to Combinatorics
Fall 2021 Course Outline
Course format.
In Fall 2021 Math 239 will be offered using a form of flipped classroom instruction. There will be course
note readings and lecture videos made available online which you will be expected to go over, and then we
will use our time together to work through problems in small groups, mastering the techniques together.
This problem-time is marked as a tutorial in quest, but you should view it as the core learning time for
the course. Consequently, the tutorials will be run by the instructors and your attendance is expected.
We recognize that technical and life situations come up, so 100% attendance is not required for a 100%
grade, but you should plan to attend most problem sessions and to catch up with your group-mates if
you do need to miss a session. Your group-mates are counting on you and the problems you work on in
the problem sessions contribute to your grade.
The course can be taken either with in-person problem sessions or fully online with synchronous
online problem sessions. Simply choose an online or in-person tutorial section as suits your situation.
Additionally, we will have both in-person and online office hours and a discussion forum.
A student from an in-person session who is required to self-isolate can be videoed in by their group so
as to continue to participate. If the covid situation requires, the in-person problem sessions will revert to
online problem sessions in the same time slot.
Overview.
Math 239 is an introduction to combinatorics and is both fun and useful. This material is closely related
to many of the staple puzzle book questions you may have pondered as a kid, and is also foundational
to every discipline involving discrete structures including theoretical computer science. The course is
primarily theoretical and you will develop your proof-writing skills while working with interesting and
useful structures.
The first portion of the course is combinatorial enumeration. If you enjoyed puzzle book questions
like “how many ways can you tile a 2 × n board with dominoes?” then you will like this part. If you
ever wondered how the number of binary trees grows and how we know that, then you will like this
part. Practically, you will learn about generating series, which are one of the most important tools in
algebraic enumeration, particularly with a focus on classes of binary strings as examples of regular lan-
guages, and you will learn how to solve recurrence equations. You will play with combinatorial objects
like compositions of an integer.
The second portion of the course is graph theory. If you enjoyed puzzle book questions of the form
“can you draw a given figure without lifting your pencil or retracing any line?”, then you will like this
part. If you like to think about the structures of networks then you will like this part. Practically you
will learn the formal foundations of graph theory, standard results and how to prove them, and some key
graph algorithms.
Classes and instructors.
Tutorials begin on September 13 (the first full week of class). Be there!
As well as seeing your instructor in tutorial, you are encouraged to ask questions during office hours.
Answering your questions in office hours is part of our job, and we are here because we enjoy talking
math with people.
If your question is applicable to others, it is even better to ask it on our Piazza discussion forum.
1
Instructor Email (@uwaterloo.ca) Problem sessions Office hours Location
Jane Gao p3gao 102: 8:30-9:20am Wednesdays, online TBA online
105: 9:30-10:20am Mondays, online
106: 11:30am-12:20pm Fridays, online
Steve Melczer steve.melczer 101: 1:30-2:20pm Mondays, online TBA online
103: 8:30-9:20am Fridays, online
104: 6:30-7:20pm Mondays, online
Evelyne evelyne.smith-roberge 107: 9:30-10:20am Mondays, MC 4045 TBA TBA
Smith-Roberge 108: 9:30-10:20am Wednesdays, MC 2034
109: 9:30-10:20am Fridays, MC 4045
Karen Yeats kayeats 110: 1:30-2:20pm Mondays, MC 4045 TBA TBA
111: 1:30-2:20pm Wednesdays, MC 2017
112: 1:30-2:20pm Fridays, MC 4045
Assessments.
The grade breakdown will be
• 15% tutorial hand-in questions
• 10% presentations
• 25% individual assignments
• 25% enumeration exam (midterm)
• 25% graph theory exam (final exam)
To pass the course you must pass both the test portion of the assessments and the non-test portion of
the assessments.
Assignments. Assignments are to be done individually. This is in contrast to the tutorial hand-in ques-
tions which are to be done in your tutorial groups based on the work you did in tutorial.
Assignments will typically be due on Thursdays at 11am Waterloo time on Crowdmark, though the
last assignment will instead be due on a Tuesday. Assignments will be submitted using crowdmark. The
lowest assignment grade will be dropped.
Many assignment questions are proof questions and you will be evaluated on the logic and presenta-
tion of your ideas. Aim to present your proofs at a level that would be understood by an average student
in the class who has not thought about the problem yet. There is a document on how to present solutions
in Learn with further details.
Tutorial hand-in questions and presentations. The tutorial hand-in questions are to be done in your
tutorial groups based on work you did in tutorial. You should get the bulk of the work for the ques-
tion done during tutorial and then your group will only need to write it up neatly and submit it after
the tutorial time. Hand-in questions for Monday tutorials are due on Wednesday at the same time your
tutorial started, hand-in questions for Wednesday tutorials are due on Friday at the same time your tuto-
rial started, and hand-in questions for Friday tutorials are due on Monday at the same time your tutorial
started. The lowest tutorial hand-in question will be dropped.
You will also be asked to give 1-3 short informal presentations on your problem solving during tuto-
rials. These may be on the tutorial pre-questions, on previous assignment questions you have done well
on, or on the tutorial problems your group is currently working on. Presentations are a chance for you to
show your thinking, to intelligently describe the places where you’re still unsure as well as to explain the
parts you have understood.
2
Exams. The exams will be timed online tests where you have the flexibility to choose the 2 hour block
of time in which you write them, within a 24 hour window. You may not consult with any resource other
than the course notes.
The window for the enumeration exam will be from 8am Waterloo time on Tuesday October 26 to
8am Wednesday October 27. The window for the graph theory exam will be scheduled by the registrar
during the final exam period and will be announced during the term.
Schedule and material.
The course resources can be found on Learn. There are two sets of course notes that we will be using.
Part I will be used for the enumeration portion of the course and Part II will be used for the graph theory
portion of the course. Both can be found on Learn. Also on Learn are links to the video lectures.
Don’t forget, the tutorials are your main contact time and learning time. Even though the video lec-
tures are available, you are expected to attend your tutorial.
This is a tentative schedule with topics that we plan to cover. A further breakdown of the readings as
they are associated to each lecture video can be found on Learn.
Week Dates Topics Readings Assessments
1 Sept 8-10 Counting, bijections, Part I
combinatorial proofs 1.1.1-1.1.7
2 Sept 13-17 Generating series Part I tutorial 1 hand in question
formal power series 2.1-2.2.1
3 Sept 20-24 Sum, product, and string lemmas Part I tutorial 2 hand in question
integer compositions 2.2.2-2.3 assignment 1 (on week 1&2 material)
4 Sept 27-Oct 1 Binary strings Part I tutorial 3 hand in question
string decompositions 3.1-3.2.3 assignment 2 (on week 3 material)
5 Oct 4-8 String recursion, Part I tutorial 4 hand in question
recurrences 3.3.3, 4.1-4.3 assignment 3 (on week 4 material)
Oct 11-15 reading week
6 Oct 18-22 Catalan classes Part I tutorial 5 hand in question
4.4 assignment 4 (on week 5 material)
7 Oct 25-29 Introduction to graph theory Part II enumeration exam
4.1-4.5
8 Nov 1-5 Paths and cycles, Part II tutorial 6 hand in question
connectedness 4.6, 4.8
9 Nov 8-12 Eulerian circuits Part II tutorial 7 hand in question
bridges, trees 4.9, 4.10, 5.1 assignment 5 (on week 7&8 material)
10 Nov 15-19 Bipartite characterization, Part II tutorial 8 hand in question
spanning trees, TSP 5.2, 5.3, 5.6 assignment 6 (on week 9 material)
11 Nov 22-26 Planarity Part II tutorial 9 hand-in question
7.1-7.6 assignment 7 (on week 10 material)
12 Nov 29-Dec 3 colouring, Part II tutorial 10 hand-in question
matchings 7.7, 7.8, 8.1, 8.2 assignment 8 (on week 11 material)
13 Dec 6,7 König’s theorem, Part II assignment 9 (on week 12 material)
Hall’s theorem 8.3, 8.4, 8.6
TBA graph theory exam
3
Administrative policy
Academic Integrity. In order to maintain a culture of academic integrity, members of the University of
Waterloo community are expected to promote honesty, trust, fairness, respect and responsibility.
You must do individual work on your own, and you must not do other people’s individual work or
seek out other people to do yours. You must not upload course material to sharing sites such as chegg
nor seek out information there.
It is your responsibility to know the rules and follow them. For more information, check
www.uwaterloo.ca/academicintegrity.
Mental health support. Especially in these difficult times, it is important to seek out support if you are
struggling. On-campus resources include Campus Wellness, Counselling Services, and the one-on-one
peer support program MATES. Off-campus resources include Good2Talk 1-866-925-5454, EMPOWER ME
1-833-628-5589 in Canada and the US, or see http://studentcare.ca/rte/en/IHaveAPlan_WUSA_
EmpowerMe_EmpowerMe for other countries. Also OK2BME provides support services for lesbian, gay,
bisexual, transgender or questioning youth. Phone 519-884-0000 extension 213 (Waterloo Region only).
Diversity. It is our intent that students from all diverse backgrounds and perspectives be well served
by this course, and that students’ learning needs be addressed both in and out of class. We recognize the
immense value of the diversity in identities, perspectives, and contributions that students bring, and the
benefit it has on our educational environment. Your suggestions are encouraged and appreciated. Please
let us know ways to improve the effectiveness of the course for you personally or for other students or stu-
dent groups. In particular: We will gladly honour your request to address you by an alternative/preferred
name or gender pronoun. Please advise us of this preference early in the term so we may make appropri-
ate changes to our records. We will honour your religious holidays and celebrations. Please inform of us
these at the start of the course. We will follow AccessAbility Services guidelines and protocols on how to
best support students with different learning needs.
Students with disabilities. The AccessAbility Services, located in Needles Hall, Room 1401, collabo-
rates with all academic departments to arrange appropriate accommodations for students with disabili-
ties without compromising the academic integrity of the curriculum. If you require academic accommo-
dations to lessen the impact of your disability, please register with them at the beginning of each academic
term.
Grievance. A student who believes that a decision affecting some aspect of his/her university life has
been unfair or unreasonable may have grounds for initiating a grievance. Read Policy 70, Student Peti-
tions and Grievances, Section 4, http://www.adm.uwaterloo.ca/infosec/Policies/policy70.
htm. When in doubt please be certain to contact the department’s administrative assistant who will pro-
vide further assistance.
Discipline. A student is expected to know what constitutes academic integrity to avoid committing aca-
demic offenses and to take responsibility for his/her actions. A student who is unsure whether an action
constitutes an offense, or who needs help in learning how to avoid offenses (e.g., plagiarism, cheating)
or about rules for group work/collaboration should seek guidance from the course professor, academic
advisor, or the undergraduate associate dean. For information on categories of offenses and types of
penalties, students should refer to Policy 71, Student Discipline,
http://www.adm.uwaterloo.ca/infosec/Policies/policy71.htm.
For typical penalties check Guidelines for the Assessment of Penalties,
http://www.adm.uwaterloo.ca/infosec/guidelines/penaltyguidelines.htm.
Appeals. A decision made or penalty imposed under Policy 70, Student Petitions and Grievances (other
than a petition) or Policy 71, Student Discipline may be appealed if there is a ground. A student who
believes he/she has a ground for an appeal should refer to Policy 72, Student Appeals,
http://www.adm.uwaterloo.ca/infosec/Policies/policy72.htm.
4