Counting things without listing them
How many ways are there? Almost always more than you would guess.
Suppose you have four different books and one shelf. How many orders could you put them in? You could write them all out, and for four books that is just about bearable. For ten books there are over three and a half million orderings and listing stops being an option.
Combinatorics is the part of mathematics that answers these questions without listing anything. It sits underneath probability, underneath a lot of computer science, and underneath any puzzle that asks how many arrangements are possible.
The multiplication principle
Everything else is built on this one idea. If you make a sequence of independent choices, the total number of outcomes is the number of options at each step multiplied together.
Three shirts and four pairs of trousers gives 3 x 4 = 12 outfits. Add two pairs of shoes and it is 3 x 4 x 2 = 24. Each new independent choice multiplies rather than adds, which is why these numbers grow so much faster than people expect.
Each digit is an independent choice from ten. Four independent choices of ten options each gives ten thousand, not forty. That gap between multiplying and adding is where most wrong intuitions about counting live.
Permutations: when order matters
A permutation is an arrangement where the order counts. Gold, silver and bronze are different outcomes depending on who gets which.
Arranging all n distinct objects gives n factorial, written n!, which means n x (n-1) x (n-2) x ... x 1. The reasoning is the multiplication principle: n choices for first place, then n-1 remain for second, then n-2, and so on.
- 3 books: 3! = 3 x 2 x 1 = 6 orders
- 4 books: 4! = 24
- 6 books: 6! = 720
- 10 books: 10! = 3,628,800
Factorials grow violently. That is worth internalising, because it is why brute-force search becomes impossible so quickly - checking every arrangement of 20 items is not a slow computation, it is an impossible one.
If you are only arranging some of them - say choosing 3 from 8 for the medals - you multiply just the first three terms: 8 x 7 x 6 = 336.
Combinations: when order does not matter
A combination is a selection where order is irrelevant. Picking Ana, Ben and Chi for a team is the same team as picking Chi, Ana and Ben.
The method is to count the ordered version and then divide out the orderings you have counted more than once. Choosing 3 from 8 where order matters gave 336. Each group of 3 was counted 3! = 6 times, once per internal ordering. So the number of distinct teams is 336 / 6 = 56.
That divide-out step is the whole idea, and it is worth doing the long way a few times rather than memorising the formula, because the formula hides the reasoning.
The question to ask every time: if I swapped two of the chosen items around, would that be a different outcome? Yes means permutation. No means combination. Almost every mistake in this topic is answering that question wrongly rather than doing the arithmetic wrongly.
Why the numbers get so big
A standard deck has 52 cards, so the number of possible orders is 52!, which is roughly 8 followed by 67 zeros. That is a larger number than the estimated count of atoms in our galaxy.
A practical consequence: if you shuffle a deck properly, that exact order has almost certainly never occurred before in human history and never will again. Nothing mystical is happening - it is just the multiplication principle applied 52 times.
Where it shows up
- Probability. Almost every probability question is two counting questions: how many outcomes are there, and how many are the ones I want.
- Passwords. Length multiplies possibilities far faster than complexity does, which is why long passwords beat short weird ones.
- Computing. Knowing an approach requires checking n! possibilities tells you immediately it will not work beyond about n = 12.
- Puzzles. How many arrangements satisfy this rule is a combinatorics question wearing a picture.