MAT 344 | Combinatorics
q.utoronto.ca • Text: Applied Combinatorics - Keller & Trotter
Why Combinatorics?
Combinatorics is a field of mathematics concerned with counting and finite structures. Combinatorics
is a very diverse subject that has many applications to other fields of mathematics and computer
science. The goal of this course is to introduce you to a variety of techniques and ideas that will
help you solve a wide range of problems. For example, you probably know the algebraic identity
1 + 2 + · · · + n = n+1
2 . A combinatorial proof of this identity an be given by simply counting a set of
objects in two different ways, and proofs of this form are often enlightening and even beautiful. The
topics we will cover include enumeration, pigeonhole principle, induction, recurrences, generating
functions, graphs, inclusion-exclusion, and more.
Textbook
We will use Applied Combinatorics by M.T. Keller and W.T. Trotter, 2017 edition. Available for free
at http://www.rellek.net/appcomb/. Note: for some reason the textbook .pdf and print versions
numbers differ slightly from the (more interactive) html version. When using references, we will
refer to the .pdf version.
Contact Information
Instructor Lectures Office Office Hours Email
Mon. 4-6, SS 2135
Balazs Elek BA 6256 Tue. 5-6 balazse@math.utoronto.ca
Tues. 4-5, SS 2135
Mon. 10-12, MP 102
Henry Yuen SF 2302A Mon. 1 - 2. hyuen@math.toronto.edu
Wed. 10-11, MP 102
TA Tutorials Location Email
Stanislav Balchev stanislav.balchev@math.utoronto.ca
Keegan Dasilva Barbosa keegan.dasilvabarbosa@mail.utoronto.ca
Mehmet Durlanik durlanik@math.toronto.edu
Matthew Sunohara matthew.sunohara@math.utoronto.ca
E-mail policy: Here are the guidelines for when you should use e-mail to contact the instructors and
TAs. Before e-mailing, you should first try to ask your question in class, office hours, or in tutorial.
Next, check to see if your question is answered in the syllabus or in Quercus announcements. After-
wards, use the Piazza discussion site – leverage the collective intelligence of your fellow classmates!
Many other students in the class may have the same question, and others may know the answer to
your question. Response times will be much faster, too. Otherwise, if you have a question or concern
regarding administrative aspects of the course (such as illness verification forms and other requests
for special accommodation), you may send an email to the instructor of your lecture section. E-mails
should include “MAT344” in the subject. Responses will come within 1-2 business days.
1/5
Important dates
○␣ September 18, Last day to register
○␣ October 14, Thanksgiving holiday
○␣ October 17, Midterm
○␣ November 4, Last day to drop from academic record and GPA
○␣ November 4 - 8, Fall reading week
○␣ December 2, Last week of class
Learning Outcomes
Students will demonstrate the abilities to:
○␣ Select and justify appropriate tools (induction, graphs, recurrences, complexity theory, generating
functions, probability) to analyze a counting problem.
○␣ Analyze a counting problem by proving an exact or approximate enumeration, or a method to
compute one efficiently.
○␣ Describe solutions to iterated processes by relating recurrences to induction, generating functions,
or combinatorial identities.
○␣ Identify when an exact solution is intractable, and use estimates to describe its approximate size.
○␣ Prove combinatorial identities by counting a set of objects in two ways.
○␣ Construct counting problems which show the usefulness or limitations of combinatorial tools.
Assessment
Problem sets. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
The weekly problem sets are where you will apply the material you learned in class, and develop a
deeper understanding of the material. Problem sets are released every Thursday at noon, and are
due in exactly one week. Solutions are not provided for the problem sets: this is to encourage you to
consult with TAs, your fellow students, and the instructors to identify shortcomings in your grasp of
the material.
Crowdmark. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
To help you effectively get feedback on your problem sets and midterm exam, we are using Crowd-
mark for all graded assessments, so that we can give more detailed feedback and you can easily
access it. In particular, all problem sets must be turned in via Crowdmark. Uploads to Crowdmark
must be legible - if a grader cannot read your file, it will not be marked and you will not be allowed
to resubmit it. In particular, you must ensure that all your scans/photos are rotated properly, and
the problems must be in the right order. You will receive a 0 for problems that are improperly
scanned.
If you would like to request a regrade on an assessment, you will need to make a written submission
on Crowdmark explaining what you believe was marked incorrectly. TAs will not discuss grading
in tutorials. If an assessment is regraded, it will be carefully scrutinized, and your mark may go down.
Assessments. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Attendance at tutorials
Weekly 5%
Attendance at tutorials will be taken.
Problem Sets
Weekly, due Thursday at noon 20%
2/5
10 problem sets covering the previous week’s material. Best 8 out of 10 will count.
Midterm
Wednesday, March 6, 6:10-8:00 35%
Material from the first 5 weeks
Final Exam
To be Scheduled 40%
Cumulative
Calculator policy. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Calculators are not necessary for the problem sets and the exams; for that reason, they are not allowed
during exams. We would much prefer that you write your solutions in the form of 176 rather than
24137569 (for example).
Late/Missed Assessments
Best 8 of 10 problem sets count, so missing at most two does not require a reason. Late problem sets
will not be accepted. Missing more than two assignments will require an illness verification form.
Most midterm conflicts can be resolved with an early sitting (to be scheduled). If you have an academic
conflict, email your instructor with a photo of your schedule. Missing the midterm for medical
reasons requires a verification of illness form, and the weight will be put on the final exam. The
form can be found at http://www.illnessverification.utoronto.ca, and must be filled out by a
doctor. Submitting a forged medical note is an academic offence.
Tutorials
Tutorials start the second week of classes, September 16-20. Enroll in a tutorial that does not conflict
with your lecture. Tutorials give you the opportunity to work in-depth on problems in small groups
with TA guidance. The problems will require you to apply course concepts and justify your solutions
to others. Part of your overall course mark will be determined by your attendance in tutorials.
Participation is highly recommended: tutorials are your best opportunity to practice solving novel
questions under time constraints, like you would on a test, and get immediate feedback on your
solutions from peers and TAs. Problems will be posted on Quercus before each week of tutorials,
with solutions following after all tutorials have finished.
Role in your program
Prerequisites: MAT 223. We will expect you to have a solid understanding of algebraic manipulations,
solving linear systems and set notation, as well as some familiarity with writing proofs.
Programs recommending MAT344: Applied Math Specialist, Focus in Theory of Computation, Math
Applications in Economics and Finance, Math & Applications Teaching Specialist, Math Major.
Role in your program: We hope to explain the connection between enumeration and algorithm
complexity, and motivate pedagogical questions which can be solved by combinatorial methods,
while maintaining the standards of 300-level mathematics courses. These standards include clear
communication in written proofs.
3/5
Calendar
This is a tentative schedule of topics for the term.
Strings and Sets Week 1
Chapter 2.1-2.3 Sept 9–13
Introduction to enumeration of strings of letters or numbers with restrictions, as well as permutations and
combinations
Binomial Coefficients Week 2
Chapter 2.4-2.6, PS 1 due Sept 19 Sept 16–20
Combinatorial proofs and the binomial theorem
Recurrence and Induction Week 3
Chapter 3.1-3.8, PS 2 due Sept 26 Sept 23–27
Our first look at recurrence relations, motivating the formal proof system of induction.
Pigeonhole Principle, and Introduction to Graph Theory Week 4
Chapters 4.1, 5.1-5.3, PS 3 due Nov 3 Sept 30–34
A variant of induction suitable for recurrences; a famous existence theorem. Introduction to graph theory.
Graph theory basics Week 5
Chapter 5.1-5.5, PS 4 due Oct 10 Oct 7 - 11
Basics of graph theory, colourings, Eulerian graphs, Hamiltonian tours, planar graphs
Midterm Week 6
Covers everything up to, and including Week 5 Oct 14 - 18
No class on Monday, October 14 (Thanksgiving holiday). Midterm on October 17.
Counting graphs, and graph algorithms Week 7
Chapter 5.6, 12.1-12.3, PS 5 due Oct 24 Oct 21 - 25
Both exact and asymptotic enumerations for certain graphs of given size. Minimum spanning trees, max-cut
min-flow, matchings.
Inclusion-Exclusion Week 8
Chapter 7.1-7.3, PS 6 due Oct 31 Oct 28 - Nov 1
A counting principle that applies to collections of intersecting sets.
Fall break
No class. Last day to drop this class from academic record is Nov 4. Nov 4 - 8
Generating functions Week 9
Chapter 8, PS 7 due Nov 14 Nov 11-15
A bookkeeping method to store information about sequences in a useful way.
Exponential generating functions and rerrences Week 10
Chapters 8, 9.1-9.2, PS 8 due Nov 21 Nov 18-22
An even more powerful generating function technique, and introduction to solving recurrences.
Recurrences Week 11
Chapter 9.1-9.6, PS 9 due Nov 28 Nov 25-29
Solving advancement operator equations, homogeneous equations, non-homogeneous equations.
Advanced topics Week 12
Chapter 11.1-11.5, PS 10 due Dec 5 Dec 2-6
Some advanced topic in combinatorics, such as probabilistic method, or Ramsey theory.
4/5
Collaboration Policy, and Academic Integrity
Collaboration and discussion are an important part of mathematics. A great part of having a large
group learning combinatorics is that you can help each other by discussing concepts and difficulties
you have outside of class. Naturally, this will extend to working on problem sets, so we need to
establish boundaries to let us fairly evaluate everyone. You are welcome to discuss problem set
questions together, but all work that you submit must be your own. Remember that cheating is always
possible and may increase your homework grade a bit. But it will hurt your appreciation of yourself,
your knowledge and your exam grades a lot more.
Here are some tips to avoid committing an academic offence:
○␣ Do not photograph or copy anyone’s problem set solutions.
○␣ Write your final draft alone, using only your own notes.
○␣ Do not share your drafts with any other students.
○␣ Do not ask for solutions to problem set questions online, post solutions, or look up posted solutions.
For example, if you type up your solutions using notes that anyone else wrote, or if you write your
solutions with another student looking over your shoulder, you are both committing an academic
offence.
For more information, see https://www.academicintegrity.utoronto.ca/.
Resources
We recommend LATEXfor typesetting assignments. It is the standard for mathematical writing, and
produces great looking documents (like this syllabus). If you are new to LATEX, try Overleaf for an
online editor or LyX (with TexLive or MacTex) for an introductory desktop editor.
You can find Sage Math cells at https://sagecell.sagemath.org/ for quick computations. Sage is
based on Python, and many helpful articles are available.
We hold office hours every week so that students can drop in to get advice about course material,
assessments, or you academic goals. Stop by and say hi!
You may want to learn about other combinatorial topics that we don’t have time to discuss, like Latin
squares or block designs, or more about specific topics. For related topics at a similar level, with a
traditional theorem-proof layout, try Combinatorics by Joy Morris. For a deeper look at generating
functions, try generatingfunctionology by Herbert Wilf. Both are freely available.
5/5
