## MAT 344, Introduction to Combinatorics, Winter 2023

#### Instructor

Prof. Kasra Rafi
Office: BA 6236 (Bahen Centre)
Email: rafi@math.toronto.edu

#### Meetings

Tuesdays 12-2 pm in MP 202.
Thursdays 12-1 pm in MP 202.

#### Office Hours

Tuesdays and Thursdays 11 am-12 pm,
or by appointment.

#### Course Syllabus

A PDF of the course syllabus can be found here.

#### Textbook

We will use Applied Combinatorics by M.T. Keller and W.T. Trotter, 2017 edition as our main textbook. Available for free at here.

You may want to learn about other combinatorial topics that we do not have time to discuss, like Latin squares or block designs, or more about specific topics. Some other books you may find relevant are:

• Combinatorics Through Guided Discovery by K. P. Bogart is an inquiry-based learning book that covers many of the topics of the course, and is a great source for insightful problems. Available for free here.

• Combinatorics by J. Morris is a more traditional theorem-proof style textbook that includes topics like Latin squares and designs. Available for free at: here.

• Combinatorics and Graph Theory by D. Guichard is another more traditional style textbook with an emphasis on Graph theory. Available for free ati: here.

• Generatingfunctionology by H. S. Wilf is a book focused on generating functions and their applications. Available for free at: here.

#### Course Description

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 may know the algebraic identity 1 + 2 + . . . + n =n(n+1)/2. A combinatorial proof of this identity can be given by simply counting a set of objects in two different ways, and proofs of this sort are very transparent and enlightening. The topics we will cover include graphs, recurrences, induction, generating functions, inclusion-exclusion and probability.

#### Quizzes and Homework

Problem Sets will be assigned Weekly. In mathematics, one learns through practice, i.e. by doing lots of problems. There are several other books noted at the end of this syllabus where you can find more problems, if the ones in the main text are not enough. There will be a weekly quiz in the tutorial which will consist of one of the assigned problems.

#### Assessment

• Quizzes 25%, The three lowest quizzes will be dropped
• Midterms 30%, Two 1hr midterms to take place on Feb 16 and Mar 9. Midterm grade will be max of the two.
• Final Exam 45%, A 3hr exam to take place on April 26, 2--5 pm at BN 210N.

If you would like to request a regrade on an assessment, you will need to make a written submission 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.

#### Tutorials

Tutorials start the second week of classes. They 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. You must attend the tutorials because there will be a quiz each week which counts 25% towards your final grade. Tutorials will be 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. Solutions will be posted on Quercus after all tutorials have finished.

#### Prerequisites

MAT 223.

You need to be comfortable with proofs and with using the language of set theory, like defining a set, function, relation, etc.

#### Course Calendar

Dates Sections Covered Homework assignments
January 9-13 Sections 2.1-2.6: Odd Exercises in Section 2.9
January 16-20 Sections 3.1-3.8 Odd Exercises in Section 3.11
January 23-27 Section 3.9 and Chapter 4 Excercise 1-3 in Section 4.6 and this Problem Set
January 30-February 3 Sections 5.1-5.4 Section 5.9: 1, 3, 5, 7, 9, 11, 13, 15
February 6-10 Sections 5.5-5.7 Section 5.9: 2, 4, 6, 8, 10, 14, 24, 26, 28, 30
February 13-17 Chapter 7 Section 7.7: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24
February 27-March 3 Chapter 8 Section 8.8: 3, 5, 7, 9, 17, 19, 23
March 6-10 Chapter 9 Section 9.9: 2, 4, 6a, b, c, 8b, 10, 16
March 13-17 Section 10.1-10.3 All Exercises in Section 10.8
March 20-24 Section 10.4-10.6 Probability Homework Set
March 27-31 Chapter 12 Section 12.5: 3,4,7,9,11,13,14
April 3-6 Chapter 13 Even Exercises in Section 13.7

#### Study Hints

Before each class, you should both review the material from recent sections and read the section to be discussed that day. This will allow you to both understand the presentation of new material and identify questions that you need to resolve during class.

All students, faculty and staff are expected to follow the University's guidelines and policies on academic integrity. For students, this means following the standards of academic honesty when writing assignments, collaborating with fellow students, and writing tests and exams. Ensure that the work you submit for grading represents your own honest efforts. Plagiarism -- representing someone else's work as your own or submitting work that you have previously submitted for marks in another class or program -- is a serious offence that can result in sanctions. Speak to me or your TA for advice on anything that you find unclear. To learn more about how to cite and use source material appropriately and for other writing support, see the U of T writing support website here. Consult the Code of Behaviour on Academic Matters for a complete outline of the University's policy and expectations. For more information, please look here and here.

#### Policy on Missed Work or Class Participation

Verification of Illness forms (also known as a doctor's note) are temporarily not required. Students who are absent from class for any reason (e.g., COVID, cold, flu and other illness or injury, family situation) and who require consideration for missed academic work should report their absence through the online absence declaration. The declaration is available on ACORN under the Profile and Settings menu.

#### Accessibility Needs

The University of Toronto is committed to accessibility. If you require accommodations for a disability, or have any accessibility concerns about the course, the classroom or course materials, please contact Accessibility Services as soon as possible: email accessibility.services@utoronto.ca or visit here.

#### Mental Health Care

The Health and Wellness Centre offers mental health services to students. To get more information, visit their website here.