MATC44H3 Introduction to Combinatorics
The Complete Exam Bible · Fall 2026MATC44H3 Overview
- University of Toronto Scarborough
- Fall 2026
- Discrete mathematics
- Proof-based course
- In-person final exam
What the course covers
MATC44H3 Introduction to Combinatorics is taught by the Department of Computer and Mathematical Sciences at the University of Toronto Scarborough.
- Assessed by Five assignments, an in-class midterm and a three-hour final worth the largest share.
- Core method Name the pigeons and holes, or the cases, before computing anything.
- Hardest step Proving that nothing smaller works, not only that a value works.
- How to prepare Rework the practice-set question types by hand with new numbers.
How MATC44H3 is assessed
| Component | Weight | Format |
|---|---|---|
| Assignments | 20% | Five assignments, 4% each; posted on Quercus and submitted through Crowdmark; late work not accepted |
| Midterm | 35% | Held in class, in person, on October 22, 2026 |
| Final Exam | 45% | Three hours, in person, during the final exam period |
The Fall 2026 syllabus weights total 100%. Calculators and mathematical software are not permitted during the midterm or the final examination. A missed midterm leads to the option of a make-up midterm after an Absence Declaration on ACORN.
Assessment structure
Segment widths reproduce the three published weights, which total 100%.
Current MATC44H3 dates
| Date | Item | Control |
|---|---|---|
| Tuesday, September 29, 2026 | Assignment 1 due | By 11:59 PM, submitted through Crowdmark |
| Tuesday, October 13, 2026 | Assignment 2 due | As listed on the course schedule |
| Thursday, October 22, 2026 | Midterm | In person during lecture |
| October 26 to 30, 2026 | Reading week | No classes or office hours |
| Tuesday, November 10, 2026 | Assignment 3 due | As listed on the course schedule |
| Tuesday, November 24, 2026 | Assignment 4 due | As listed on the course schedule |
| Tuesday, December 8, 2026 | Assignment 5 due | As listed on the course schedule |
| December 10 to 22, 2026 | Final exam period | Exact date set in the exam timetable |
Dates are as published in the Fall 2026 syllabus and the tentative course schedule on Quercus. Confirm exact deadlines and submission settings in the live LMS.
What MATC44H3 covers
Eleven chapters follow the opening lectures, from proof by contradiction and the pigeonhole principle to permutations, combinatorial proofs and stars and bars.
Combinatorial Questions and Proof by Contradiction
Existence, construction, enumeration and optimization questions, the problem-solving checklist and the structure of a contradiction proofFour kinds of question
The first lecture of the course sorts combinatorics problems into four kinds. Existence problems ask whether an object with some property can be found at all.
- Existence, construction, enumeration and optimization
- Problem-solving habits from the opening lecture
- Negating statements with every and some
- Proof by contradiction in three moves
- Well-ordering and smallest counterexamples
- What full justification means on an assignment
The Pigeonhole Principle and Its Strong Form
Statement and proof, the function form, the strong and generalized forms, ceilings and sharp boundsThe statement and its proof
If n objects are placed into m boxes and n is greater than m, some box contains at least two objects.
- Pigeonhole statement and proof by contradiction
- The function form of the principle
- Strong form with mk + 1 objects
- Generalized and uneven-target versions
- The ceiling function and the ceiling form
- Sharpness of the bound
Choosing Pigeonholes and Proving Sharp Bounds
Hole designs for sums, consecutive numbers, chairs, points and residues, with the counterexample half of every answerThe design is the difficulty
After the principle itself, pigeonhole questions in this course differ only in how the holes are designed.
- Complementary pairs and singleton holes
- Blocks of consecutive numbers and chairs
- Cutting a square into equal cells
- Units digits of squares as holes
- Digit-sum classes and small classes set aside
- Counting memberships when objects are sets
The Addition and Multiplication Principles
Disjoint unions, Cartesian products, divisor counts and case splits that multiply inside and add acrossTwo rules beneath every count
The addition principle says that when the ways of several events are pairwise disjoint, the number of ways for one of them to happen is the sum of their counts; for sets, the size of a disjoint union is the sum of the sizes.
- Addition principle for disjoint events and sets
- Multiplication principle and Cartesian products
- Counting divisors from prime exponents
- Splitting a count by the value of one entry
- Disjoint digit-pattern cases
- Counting functions and bijections
Colouring Proofs and Tiling Arguments
The mutilated chessboard, colourings matched to tiles and colour-count equations for mixed tilingsThe idea of a colouring proof
A colouring proof partitions the squares of a board, or the elements of any set, into a few classes by colour, and shows that every allowed tile covers a fixed pattern of colours.
- Dominoes and the two-colour chessboard
- Removing squares of the same and opposite colours
- Fisher's count and Gomory's theorem
- Colourings designed for longer tiles
- Equations from colour counts
- Constructions for the possible cases
The Invariance Principle
Quantities preserved by repeated moves, alternating sums, sums and parities on a blackboardWhat does not change
The invariance principle applies to processes that repeat a move. Find a quantity that no move can change; if it takes different values at the start and at a desired end, the end can never be reached.
- Quantities preserved by a repeated move
- Alternating sums on a circle
- Sums on a blackboard
- Parity as a weaker invariant
- Restating colouring proofs as invariants
- Why equal invariants prove nothing
Induction and the Frobenius Coin Problem
Base cases, strong induction, coin and package amounts, closed forms proved by inductionThe course's statement of induction
The induction slide frames the method in its strong form: statements P(k) indexed by k are proved by checking a few starting cases, as many as the problem needs, and then showing that the truth of every case up to n forces the case n + 1. The first example is the formula for the sum 0 + 1 + ⋯ + n, which needs one base case.
- Induction with several base cases
- The sum of the first n integers
- Frobenius coin problem and the largest gap
- Base runs as long as the smallest pack
- Strong induction reaching several steps back
- Guessing and proving a closed form
Permutations, Combinations and the Selection Table
Factorials, ordered and unordered selections with and without repetition, committees and complementsPermutations and factorials
Any ordering of distinct objects in a row is a permutation of them; n objects have n! orderings, with 0!
- Permutations and the factorial
- Ordered selections P(n, k)
- Binomial coefficients and subsets
- The order and repetition table
- Words that signal order
- Committees with and without offices
Gluing, Interlacing and Unlabelled Partitions
Blocks that stay together, gaps that keep people apart, repeated letters and splits into unnamed partsGluing for people who stay together
To count arrangements in which certain people must be adjacent, glue them into one block, arrange the block with everyone else, and multiply by the number of orders inside the block.
- Gluing a block of adjacent people
- Nested blocks
- Interlacing in gaps between people
- End gaps and inner gaps
- Identical letters placed in gaps
- Labelled versus unlabelled partitions
Combinatorial Proofs by Double Counting
One question answered two ways, the lecture identities, Pascal's rule and chaired committeesTwo kinds of proof for one identity
The week 2 lecture contrasts an algebraic proof of a counting identity, which expands binomial coefficients as factorials and may use induction, with a combinatorial proof, which finds a question that both sides answer.
- Algebraic versus combinatorial proof
- The three-step double-counting procedure
- Symmetry of binomial coefficients
- Sums of binomial coefficients and subsets
- Splitting ordered pairs by a maximum
- Committees with a president
Stars and Bars for Selections with Repetition
The bijection behind unordered selections with repetition, integer equations and lower-bound substitutionsThe entry that needed a proof
The selection table of week 2 lists C(n + k − 1, k) as the count of selections of k objects drawn from n types when order does not matter and repetition is allowed, and marks that entry as requiring a proof.
- Unordered selections with repetition
- Stars, bars and the bijection
- Solutions of x1 + ⋯ + xn = k
- Substitutions for lower bounds
- Identical versus distinct objects
- Checking against the selection table
Its calendar description lists basic counting principles, generating functions, permutations with restrictions, the fundamentals of graph theory with algorithms and applications such as network flows, and combinatorial structures including block designs and finite geometries.
The Fall 2026 learning outcomes frame the subject around four questions about combinatorial objects: whether they exist, how to construct them, how many there are, and which of them is optimal.
How the opening weeks build the toolkit
The first two weeks of lectures set up the methods the rest of the term relies on.
On the proof side they cover proof by contradiction, the pigeonhole principle in its basic, strong and ceiling forms, colouring arguments for tiling problems, the invariance principle and induction, including the Frobenius coin problem.
On the counting side they cover the addition and multiplication principles, permutations and combinations organised by whether order matters and whether repetition is allowed, the gluing and interlacing techniques for seating problems, and combinatorial proofs that count one set in two ways. Stars and bars follows in week 4.
How the guide is organised
Eleven chapters follow that teaching order.
Each one states the rule as the course states it, draws a figure computed from its own numbers, works an original example in full and ends with practice modelled on the question types of the course practice set and first assignment, with new numbers.
Front matter sets out the assessment, the weekly route and what full-credit answers contain; a final page gathers checks for the three-hour exam.
Assessment at a glance
Five assignments count for 20%, at 4% each, an in-class midterm on October 22 for 35%, and a three-hour in-person final in the December exam period for 45%. Calculators are not permitted on either test.
Worked example · free
Shared birthdays guaranteed by the ceiling bound
- 2Pigeons are the 1,000 participants; holes are the 366 possible birthdays, including February 29.
- 2The ceiling form gives some birthday at least ⌈1000/366⌉ = ⌈2.73⌉ = 3 participants.
- 2Four is not forced: 366 × 3 = 1,098 is at least 1,000, so no birthday need hold more than three.
Key terms
- Pigeonhole Principle
- The pigeonhole principle states that if more than m objects are placed in m boxes, some box holds at least two of them.
- Ceiling Function
- The ceiling function rounds a real number x up to the nearest integer not below it, written ⌈x⌉.
- Sharp Bound
- A sharp bound is a guarantee that cannot be improved, shown by an example that just fails at the next value.
- Proof by Contradiction
- Proof by contradiction assumes the negation of a claim and derives a statement known to be false.
- Addition Principle
- The addition principle counts a choice from pairwise disjoint groups as the sum of the group sizes.
- Multiplication Principle
- The multiplication principle counts an outcome built in ordered stages as the product of the stage counts.
- Colouring Proof
- A colouring proof labels squares or elements with colours so that a forced colour count rules out an arrangement.
- Invariant
- An invariant is a quantity that a repeated move never changes, so differing start and target values prove a target unreachable.
- Strong Induction
- Strong induction proves a statement for n + 1 from the statements for all earlier values, after enough base cases.
- Binomial Coefficient
- The binomial coefficient C(n, k) counts the subsets of size k in a set of n elements and equals n!/(k!(n − k)!).
- Combinatorial Proof
- A combinatorial proof shows two expressions are equal by explaining how each counts the same set.
- Stars and Bars
- Stars and bars encodes a selection with repetition from n types as a string of stars and n − 1 bars.
MATC44H3 FAQ
What is the format of the final exam?
The course introduction slides state a three-hour final exam written in person during the exam period, and the syllabus weights it at 45% of the grade. The schedule gives the final exam period as December 10 to 22, 2026. The exact date and room come from the official exam timetable, and calculators and electronic devices are not allowed.
When is the midterm and how much is it worth?
The midterm is worth 35% and is held in class, in person, on October 22, 2026, in week 7 of the schedule. A student who misses it for reasons outside their control completes an Absence Declaration on ACORN, sends a copy to the instructor and is given the option of a make-up midterm.
How do the assignments work?
There are five assignments worth 4% each, posted on Quercus and submitted through Crowdmark by the posted deadline. Late assignments are not accepted. Discussing problems with classmates is encouraged, but each student writes up their own solutions, and generative AI may not be used to solve an assignment or to draft any part of one.
Can I use a calculator in the tests?
No. The syllabus states that calculators and mathematical software are not permitted during the midterm or the final examination, and the introduction slides add that electronic devices are not allowed. Practise factorials, binomial coefficients and ceiling divisions by hand, at the sizes the practice set uses, so that arithmetic does not slow you down.
How much proof writing does the course expect?
A great deal. The syllabus says students will reason abstractly, provide mathematical proofs and work with precise definitions, and the first assignment says full marks go only to correct solutions that are completely justified, such as a proof, a logical argument or a counter-example. A correct number without its argument is an incomplete answer.
How do I approach a pigeonhole question?
Decide what the pigeons are and design holes so that two pigeons sharing a hole gives the property you want. Count the holes carefully, including singletons, apply the matching form of the principle, and for a smallest value question exhibit an arrangement one below the answer that fails. The course solutions always give both halves.
Which counting mistakes are most common?
Three recur. Adding cases that overlap counts some outcomes twice. Choosing the required people first and then anyone else overcounts committees. Treating identical objects as distinct, or unnamed groups as named, inflates a count by a factorial. Ask what one outcome looks like and whether swapping two parts produces a different outcome.
Questions students ask in each MATC44H3 chapter
- How do I negate a statement that starts with every?
- Replace every with some and negate the property. The negation of every group of 25 students has three sharing a birth month is that some group of 25 students has no month shared by three of them. A contradiction proof assumes exactly this negated sentence. Chapter 01 · Combinatorial Questions and Proof by Contradiction
- What does it mean that the pigeonhole principle is not constructive?
- It tells you a box with two objects exists but not which box. That makes it ideal for existence questions and useless on its own for construction questions. If a problem asks you to exhibit the two objects, you need a different argument or an explicit search. Chapter 02 · The Pigeonhole Principle and Its Strong Form
- Why do singleton holes change the answer?
- Each singleton can hold only one of the chosen distinct numbers, so it absorbs a choice without creating a pair. If you forget it, your hole count is one short and your guarantee is one too small. Write all the holes, including the unpaired values, before applying the principle. Chapter 03 · Choosing Pigeonholes and Proving Sharp Bounds
- How do I know whether to add or multiply?
- Ask what one outcome looks like. If it is a single option taken from one of several separate groups, add the group sizes. If it is a sequence of decisions, one from each stage, multiply the stage counts. Most problems multiply inside each case and then add the cases. Chapter 04 · The Addition and Multiplication Principles
- Why does every domino cover one square of each colour?
- A domino covers two squares that share an edge, and on a chessboard colouring two squares sharing an edge always have different colours. So whichever way a domino is placed, it covers exactly one dark square and one light square, and any domino tiling covers equal numbers of each colour. Chapter 05 · Colouring Proofs and Tiling Arguments
- What makes a good invariant?
- A good invariant is simple to compute, unchanged by every allowed move, and different at the start and at the target. Sums, alternating sums, counts of a colour and parities are the usual candidates. Test a candidate on one move algebraically before building the argument on it. Chapter 06 · The Invariance Principle
- How many base cases does a coin problem need?
- As many as the size of the pack the inductive step removes, usually the smallest pack. If the step writes n + 1 as an amount s less plus one pack of size s, it reaches s places back, so s consecutive amounts must be verified by hand first. Chapter 07 · Induction and the Frobenius Coin Problem
- How do I decide whether order matters in a counting question?
- Ask whether two outcomes that contain the same objects in a different order are counted as different. Lists, rows, PINs, words and offices make them different. Sets, groups, committees without roles and hands of cards make them the same. When in doubt, test with a tiny case and list. Chapter 08 · Permutations, Combinations and the Selection Table
- When should I use gluing and when interlacing?
- Glue when a group must be together: the block becomes one unit and its internal orders multiply in. Interlace when a group must be kept apart: seat the others first and place the restricted people in different gaps. For exactly two people kept apart, gluing and subtracting from the total also works. Chapter 09 · Gluing, Interlacing and Unlabelled Partitions
- How do I find the question for a combinatorial proof?
- Start from the simpler side. A single binomial coefficient suggests choosing a committee or subset, a power of 2 suggests including or excluding each element, and n² suggests ordered pairs. Then read the other side for its split: a plus sign means disjoint cases and a sum over k means classifying by size. Chapter 10 · Combinatorial Proofs by Double Counting
- Why are there n − 1 bars for n types?
- Bars separate consecutive types, and n types need only n − 1 separators: the stars before the first bar belong to type 1, the stars between the first and second bars to type 2, and so on, with the stars after the last bar belonging to type n. Chapter 11 · Stars and Bars for Selections with Repetition
How to study for the exam
Revise in three passes. First, rebuild each chapter from memory: state the principle exactly as the course states it, then write the proof of the principle itself, since the pigeonhole principle, the ceiling form and Pascal's rule all have short proofs that make good exam questions.
Second, solve one new problem per chapter by hand, writing the full justification: name the pigeons and holes, the colouring, the invariant or the cases before computing, and for every smallest value question give both the guarantee and the counterexample.
Third, mix chapters, because exam questions rarely announce their tool: a seating question may need gluing and a complement, and an identity may need a story with a case split. Use the course practice set and the first assignment to learn the question types, then practise those types with your own numbers. Check every counting answer on a small case you can list by hand.
Your AI Mathematics tutor for MATC44H3
Stuck on a hard MATC44H3 question? Sia is AskSia’s AI Mathematics tutor — ask any MATC44H3 Introduction to Combinatorics question and get a clear, step-by-step explanation grounded in how the course is actually taught and assessed. Read this whole study guide free, then take your hardest questions to Sia.
