Sample · 15-Counting Principles
Chapter 15 Overview
Book 4 — Olympiad Combinatorics · CHAPTER 15: Counting Principles
"God made the integers; all else is the work of man." — Leopold Kronecker (as quoted by Heinrich Weber, 1893)
Welcome to Book 4. Combinatorics is the mathematics of counting — and counting well is a genuine skill, because the same problem can be trivial or impossible depending on how you set it up. This chapter builds the complete toolkit, from the two principles that everything rests on to the clever bijections that make hard counts easy.
Everything grows from two rules pictured in the choice tree above. The addition principle: if a task splits into disjoint cases, add the counts. The multiplication principle: if a task is a sequence of independent choices, multiply. From these come permutations (order matters), combinations (order does not), multisets (repetition allowed), stars and bars (counting integer solutions), complementary counting (count the opposite), and bijections (count one thing by matching it to another).
The single most important question in every counting problem is: does order matter, and is repetition allowed? Those two yes/no answers select the tool. The seven sections below, mapped in the menu, are organised exactly so you can find the right method fast — and the hardest olympiad problems simply combine two or three of them.
📋 How this chapter works
The usual rhythm, tuned for counting.
| Section | What it gives you |
|---|---|
| 📋 Strategy Corner | the definition, the counting formula, and the standard setup |
| Decision flowchart | the method as a procedure, with the self-check that validates the count |
| 🛠️ In Practice / 📊 Applications Spotlight | where the counting shows up in real life — marketing, IT, games, logistics |
| ⚠️ Common Trap | the specific way a good count goes wrong (usually order or repetition) |
| Worked Example | a full solution, with the check that the setup matches the question |
| 🚀 Challenge Yourself | a harder problem with a hint but no solution |
The golden rule of this chapter: before computing anything, decide whether order matters and whether repetition is allowed. Almost every wrong answer in counting comes from confusing a permutation with a combination, or from counting the same outcome twice. Set up first; compute second.
15.1 Basic Counting
15.1 Basic Counting
Two principles underlie all of counting. The addition principle says that if a task can be done in one of several mutually exclusive ways — case 1 or case 2 or ... — the total number of ways is the sum of the counts. The multiplication principle says that if a task is a sequence of independent steps — do step 1 then step 2 then ... — the total number of ways is the product of the counts.
The trigger words tell you which to use. An "or" between exclusive alternatives means add; an "and then" chain of choices means multiply. The two subtleties that cause most errors: for addition the cases must be genuinely disjoint (or you double-count the overlap, and must correct with inclusion-exclusion), and for multiplication the number of choices at each step must not depend on the earlier choices in a way you have not accounted for.
Continue reading — 5 chapters, worked examples and practice.
Sign in to buy