Difficulty: Introductory | Prerequisites: Basic set theory, familiarity with factorial notation
Tags: combinatorics, counting, product rule, sum rule, inclusion-exclusion, division rule, pigeonhole principle, discrete mathematics, CS foundations, Purdue
Combinatorics is the branch of mathematics concerned with counting, arranging, and selecting objects. It underpins algorithm analysis, probability, cryptography, and large parts of theoretical computer science. Before you can reason about how long an algorithm takes or how many outcomes an experiment has, you need to know how to count structured collections systematically. This material assumes you are comfortable with basic set operations (union, intersection) and factorial notation (n!).
There are four foundational counting rules: multiply when tasks happen in sequence, add when they are mutually exclusive, correct for overlap with inclusion-exclusion, and divide out repeated counting with the division rule. The pigeonhole principle lets you prove that crowding is unavoidable when you have more objects than containers.
Product rule (multiplication principle)
If a procedure consists of a sequence of tasks, and task 1 can be done in n₁ ways, task 2 in n₂ ways, and so on, the total number of ways to complete the full procedure is n₁ × n₂ × … × nₖ. Think of it as: every choice at one stage can pair with every choice at the next.
Sum rule (addition principle)
If there are several mutually exclusive tasks (you do exactly one of them), the total number of ways to pick one task is the sum of the individual counts. In simple terms, this means you add when the options do not overlap and you are choosing between them, not doing them all.
Inclusion-exclusion principle
For two sets A and B, |A ∪ B| = |A| + |B| − |A ∩ B|. You add the individual sizes, then subtract the overlap you double-counted. Think of it as a correction factor: adding two circles on a Venn diagram counts the overlap region twice, so you take it away once.
Division rule (overcounting correction)
If a counting procedure produces n outcomes but every distinct result appears exactly d times, the true count of distinct results is n / d. In simple terms, this means you divide out symmetry. Circular seating arrangements are the classic case.
Pigeonhole principle (Dirichlet's box principle)
If n objects are placed into k containers and n > k, at least one container holds more than one object. Think of it as: if you have 13 socks and 12 drawers, some drawer has at least two socks. The name comes from mail pigeonholes, not birds.
Generalised pigeonhole principle
If n objects are distributed among k bins, at least one bin contains at least ⌈n / k⌉ objects. This is the quantitative version: it tells you not just that crowding happens, but gives a lower bound on how crowded the fullest bin must be.
The product rule applies whenever a procedure breaks into sequential, independent stages.
Each stage's count must be independent of the choices made at other stages.
If choices at one stage depend on earlier choices, you cannot simply multiply; you need conditional counting or case analysis instead.
Example – licence plates: A plate has three letters followed by three digits. There are 26 options per letter position and 10 per digit position, giving 26³ × 10³ = 17,576,000 plates.
Example – PINs: A four-digit PIN where each digit is 0–9, chosen independently, gives 10⁴ = 10,000 possible PINs.
The sum rule applies when you are choosing exactly one option from several non-overlapping categories.
The categories must be mutually exclusive. If they overlap, you need inclusion-exclusion instead.
Example – committee representative: Choosing one representative from either 80 faculty members or 3,000 students gives 80 + 3,000 = 3,080 possible choices, because no one is both faculty and a student in this scenario.
Use this when two (or more) sets of outcomes overlap and a straight sum would double-count.
Formula for two sets: |A ∪ B| = |A| + |B| − |A ∩ B|
Extends to three or more sets by alternating addition and subtraction of intersection sizes.
Example – bit strings: How many bit strings of length 8 start with 1 OR end with 00?
Strings starting with 1: first bit fixed, remaining 7 free → 2⁷ = 128
Strings ending with 00: last two bits fixed, remaining 6 free → 2⁶ = 64
Strings that do both: first bit = 1, last two bits = 00, remaining 5 free → 2⁵ = 32
Total: 128 + 64 − 32 = 160
Useful when a straightforward count treats rotations, reflections, or relabellings as different but you want to collapse them.
Formula: Distinct outcomes = n / d, where d is the number of times each distinct outcome is repeated.
Example – circular seating: Seating 4 people around a circular table. Linear arrangements give 4! = 24, but each circular arrangement is counted 4 times (once for each rotation). Distinct circular arrangements: 24 / 4 = 6.
The pigeonhole principle does not tell you which bin is overfull; it guarantees that at least one must be.
It is a powerful tool for existence proofs in discrete maths and computer science.
Example – birthdays: Among 25 people and 12 possible birth months, at least ⌈25 / 12⌉ = 3 people share a birth month.
Example – confiscated phones: 50 bags each contain between 0 and 23 phones (24 possible values). By the generalised principle, at least ⌈50 / 24⌉ = 3 bags contain the same number of phones.
Rule | Formula |
|---|---|
Product rule | Total = n₁ × n₂ × … × nₖ |
Sum rule | Total = n₁ + n₂ + … + nₖ (mutually exclusive) |
Inclusion-exclusion (2 sets) | |A ∪ B| = |A| + |B| − |A ∩ B| |
Division rule | Distinct = n / d |
Pigeonhole (basic) | n objects, k bins, n > k → some bin has ≥ 2 |
Pigeonhole (generalised) | n objects, k bins → some bin has ≥ ⌈n / k⌉ |
The product rule is how engineers calculate the size of password spaces and the address capacity of networking protocols (e.g., IPv4 has 2³² ≈ 4.3 billion addresses because each of 32 bits is an independent binary choice). Inclusion-exclusion appears in database query optimisation when estimating the size of joined result sets. The pigeonhole principle is used in hash-function analysis to prove that collisions are inevitable once the number of inputs exceeds the number of possible hash values.
Students frequently apply the product rule when the choices are not independent. If the number of options at stage 2 depends on what was chosen at stage 1, you cannot just multiply the two maxima.
A common error with inclusion-exclusion is forgetting to subtract the intersection, or subtracting it twice when there are three sets.
Students often think the pigeonhole principle tells you which bin is overfull. It does not. It only guarantees existence.
The division rule only works when every distinct outcome is repeated the same number of times (d). If different outcomes have different repetition counts, a simple division is wrong.
⚠️ Product vs. sum rule is one of the most common exam decision points. Ask yourself: "Am I doing task A AND task B (multiply), or task A OR task B (add)?"
⚠️ Inclusion-exclusion problems are a favourite on exams because they test whether you can spot the overlap. Always identify the intersection explicitly.
⚠️ Pigeonhole questions usually ask you to prove something must happen (existence), not to find a specific example. The ceiling function ⌈n / k⌉ in the generalised version is frequently tested.
⚠️ Circular permutation questions (division rule) often trip students up because they forget to divide by the number of rotations.
True or false: If you need to pick a shirt AND trousers, you use the sum rule.
Fill in the blank: |A ∪ B| = |A| + |B| − ______
True or false: The pigeonhole principle can tell you exactly which bin has the most objects.
Fill in the blank: The number of distinct circular arrangements of n people is ______.
True or false: The sum rule requires that the categories be mutually exclusive.
Answers: 1. False (product rule). 2. |A ∩ B|. 3. False (existence only). 4. (n − 1)! or equivalently n!/n. 5. True.
Q: A password consists of two uppercase letters followed by four digits. How many possible passwords are there?
A: 26² × 10⁴ = 676 × 10,000 = 6,760,000.
Q: How many bit strings of length 10 start with 110 or end with 01?
A: Start with 110: remaining 7 bits free → 2⁷ = 128. End with 01: remaining 8 bits free → 2⁸ = 256. Both conditions: first 3 bits = 110, last 2 bits = 01, remaining 5 bits free → 2⁵ = 32. By inclusion-exclusion: 128 + 256 − 32 = 352.
Q: Five people sit around a circular table. How many distinct seating arrangements are there?
A: Linear arrangements = 5! = 120. Each circular arrangement is repeated 5 times (rotations). Distinct arrangements = 120 / 5 = 24.
Q: A lecture hall has 400 students. What is the minimum number of students who must share the same birthday (day-of-year, ignoring leap years)?
A: 365 possible birthdays. By the generalised pigeonhole principle, at least ⌈400 / 365⌉ = ⌈1.096⌉ = 2 students share a birthday.
This material connects directly to permutations and combinations (covered in Part 2 of these notes), which build on the product rule and division rule to count ordered and unordered selections. The pigeonhole principle reappears in algorithm analysis, particularly in proving lower bounds on sorting algorithms and hash collisions. Inclusion-exclusion extends into probability theory when computing the probability of unions of events.
counting principles, multiplication principle, addition principle, mutually exclusive, Venn diagram, overcounting, circular permutation, Dirichlet box principle, pigeonhole, generalised pigeonhole, ceiling function, discrete maths, combinatorics basics, CS 182, foundations of computer science