Counting and discrete reasoning
IOQM Combinatorics: Build Reliable Counting Arguments
Learn combinatorics in the order that makes Olympiad counting dependable: basic counting rules, arrangements and selections, casework, pigeonhole principle, inclusion–exclusion, invariants and graph ideas.
Combinatorics is the mathematics of counting and finite structures. Strong solutions do more than produce a number: they define what is being counted, separate overlapping cases, decide whether order matters and prove that every object is counted exactly once.
Recommended sequence
Learn combinatorics as a chain of ideas
| Stage | Core ideas | Proof habit |
|---|---|---|
| 1. Foundations | Sum rule, product rule, factorial notation | Describe each independent choice |
| 2. Arrangements | Permutations, repeated objects, circular order | State when order matters |
| 3. Selections | Combinations and binomial coefficients | Identify an unordered choice |
| 4. Casework | Disjoint cases and complementary counting | Prove cases neither overlap nor miss objects |
| 5. Principles | Pigeonhole and inclusion–exclusion | State the boxes or overlap explicitly |
| 6. Olympiad tools | Invariants, colouring, recurrences and elementary graphs | Explain what cannot change and why |
Worked foundations
Start with objects, choices and order
Product rule
A student can choose one of 3 shirts and one of 4 pairs of trousers. Each shirt can be paired with every trouser choice, so the number of outfits is 3 × 4 = 12.
Unordered pairs
If 8 people each shake hands once with every other person, each handshake is an unordered pair. The count is C(8,2) = 8 × 7 ÷ 2 = 28.
Existence without construction
Use the pigeonhole principle with precise boxes
Thirteen people must include two whose birthdays occur in the same month. The people are the objects and the 12 months are the boxes. If every month held at most one person, there could be at most 12 people; the thirteenth forces a shared month.
For harder questions, the main work is choosing the right boxes. Residue classes, intervals, colours, sums or geometric regions often serve as boxes.
Write the maximum possible number when no box violates the desired condition. The next object is the forcing threshold.
Correct overlapping counts
Add broad sets and subtract the overlap
How many positive integers not exceeding 100 are divisible by 2 or by 3?
- There are ⌊100/2⌋ = 50 multiples of 2.
- There are ⌊100/3⌋ = 33 multiples of 3.
- The multiples of both were counted twice. These are multiples of 6: ⌊100/6⌋ = 16.
- Therefore the answer is 50 + 33 − 16 = 67.
Inclusion–exclusion is not a correction trick to memorise. It is an accounting statement about how often each object has been counted.
Control the partition
Good casework is disjoint and exhaustive
Disjoint
No valid object belongs to two cases. If cases overlap, subtract the overlap or redesign the split.
Exhaustive
Every valid object belongs to at least one case. State why the chosen cases cover all possibilities.
Efficient
Split by a property that changes the counting method, not by an arbitrary long list.
Useful splits include parity, the largest element, whether a special object is chosen, or the number of objects of a given type.
What remains unchanged
Invariants turn repeated moves into a proof
In move-based problems, test parity, residue modulo a small integer, colour balance, total sum or another quantity that changes predictably. If every legal move preserves a quantity but the target has a different value, the target is impossible.
- Define the proposed invariant.
- Check every allowed type of move.
- Compute it for the starting and target states.
- State the contradiction or the restriction it creates.
Do not call something an invariant until every legal move has been checked.
Error prevention
Five common combinatorics mistakes
Ordered versus unordered
AB and BA may be different arrangements but the same selected pair.
Hidden overlap
Adding cases that share outcomes causes overcounting.
Missing boundary cases
Zero, equality and an empty choice can change the count.
Unlabelled objects
Formulas for distinct objects fail when repetitions or identical items occur.
Pigeonhole without boxes
A claim is incomplete until the objects, boxes and forcing threshold are identified.
Formula before model
Starting with nPr or nCr can hide what an outcome actually contains.
Preparation method
Practise explanation, not just numerical answers
- Solve small cases by hand and list the objects.
- Look for a pattern, but prove it for the general case.
- Write why each case is disjoint and why all cases are covered.
- Check the result with a second count when possible.
- Keep an error log labelled order, overlap, omission, repetition or unjustified principle.
- Mix combinatorics with number theory, algebra and geometry so method recognition improves.
Resource path
Choose one primary source and solve deeply
The official HBCSE suggested reading includes combinatorics resources such as Introductory Combinatorics by Richard A. Brualdi, Discrete Mathematics: Elementary and Beyond by L. Lovász, J. Pelikán and K. Vesztergombi, Combinatorial Techniques by S. S. Sane, and A Primer in Combinatorics by S. Muralidharan.
These are not a compulsory IOQM booklist. Start at an appropriate level, finish selected chapters with written solutions, and use the complete IOQM books guide to match resources to readiness.
Questions answered
Frequently asked questions
Is combinatorics important for IOQM?
Yes. Counting, arrangements, selections, pigeonhole reasoning, casework and related discrete ideas appear naturally in Olympiad problem solving.
Should I learn permutations before combinations?
Usually yes. First understand ordered arrangements, then compare them with unordered selections and explain why division removes repeated orderings.
When should I use combinations?
Use combinations when an outcome is a selection and rearranging the selected objects does not create a new outcome.
What is the easiest way to avoid overcounting?
Define one outcome precisely, create disjoint cases and state how many times each outcome is counted.
How do I recognise a pigeonhole problem?
Look for a guarantee that two or more objects share a property, especially when the number of objects exceeds the capacity of defined categories.
Are invariants part of combinatorics?
They are a broad Olympiad technique used frequently in combinatorial processes, colouring and move-based problems.
Which combinatorics book should I start with?
Choose a source matched to your current level and use it consistently. The official HBCSE reading list offers several options rather than one compulsory text.
How should I practise IOQM combinatorics?
Combine graded topic sets with official mixed papers, write complete counting arguments and classify every error by its cause.
Next step
Build a counting argument one decision at a time.
Continue with official papers, a balanced preparation plan and the other three IOQM topic hubs.
MENTOR PERSPECTIVE
“Good counting begins by deciding what must not be counted twice or forgotten.”Meet your IOQM mentor →