Permutations and Combinations
Counting Principle and Factorials
Counting sounds like the most elementary thing in mathematics, yet beyond a handful of objects, listing every possibility by hand becomes hopeless. The whole of this chapter exists to count without listing. Two principles do the heavy lifting, and almost every counting question reduces to deciding which one applies.
Multiplication Principle (Fundamental Principle of Counting, FPC): If one task can be done in $m$ ways and, after it is done, a second independent task can be done in $n$ ways, then the two tasks together can be done in $m \times n$ ways. The phrase that signals multiplication is "and then" — a sequence of choices made one after another.
Addition Principle: If a task can be done by method A in $m$ ways or by method B in $n$ ways, and the two methods cannot happen together, then the task can be done in $m + n$ ways. The signal word here is "or" — a choice between mutually exclusive alternatives.
| Situation | Signal word | Principle | Operation |
|---|---|---|---|
| Do step 1, then step 2 | and / then | Multiplication | $m \times n$ |
| Pick option A or option B | or | Addition | $m + n$ |
Factorial. Counting arrangements forces us to multiply long descending strings of integers, so we give that product a name. For a positive integer $n$, $n$ factorial is the product of all positive integers up to $n$:
Factorials grow ferociously fast: $5! = 120$ but $10! = 3{,}628{,}800$. Two facts must be memorised. First, the recursive relation $n! = n \times (n-1)!$, which lets you simplify ratios of factorials without ever expanding them fully. Second, by convention:
Why is $0! = 1$? It is not a fudge. The recursion $n! = n \times (n-1)!$ at $n = 1$ gives $1! = 1 \times 0!$, which forces $0! = 1$. There is also a combinatorial reason: there is exactly one way to arrange nothing — the empty arrangement — so the count of arrangements of zero objects must be $1$, not $0$.
Deeper Insight — one decision tree, two operations: Beginners treat the multiplication and addition principles as separate tricks to memorise, but they are really two readings of the same picture: a decision tree. When choices happen in sequence — first this, then that — the branches multiply, because each early branch splays into a full fan of later ones. When choices are alternatives — this route or that route — the branches add, because you travel down only one of them. The single most reliable habit in counting is to narrate the problem to yourself in plain words and listen for "and" versus "or"; the arithmetic then writes itself. Factorial is simply what the multiplication principle produces when you arrange all of a set's objects in a row — $n$ choices for the first slot, $n-1$ for the next, and so on down to $1$ — which is why it sits at the root of both permutations and combinations.
- The choices are made in sequence: pick a sandwich and a drink and a dessert — the word "and" signals the multiplication principle.
- Sandwich: $3$ ways. Drink: $4$ ways. Dessert: $2$ ways.
- Total $= 3 \times 4 \times 2 = 24$.
Answer: $24$ different combo meals.
- There are three ordered positions to fill: hundreds, tens, units.
- Hundreds place: any of $5$ digits.
- Tens place: any of the remaining $4$ digits (one is used up).
- Units place: any of the remaining $3$ digits.
- Total $= 5 \times 4 \times 3 = 60$.
Answer: $60$ three-digit numbers.
- The student picks a science elective or a humanities elective — the alternatives are mutually exclusive, so use the addition principle.
- Science: $5$ ways. Humanities: $3$ ways.
- Total $= 5 + 3 = 8$.
Answer: $8$ ways.
- Use $8! = 8 \times 7 \times 6 \times 5!$, so $\dfrac{8!}{5!} = \dfrac{8 \times 7 \times 6 \times 5!}{5!}$.
- The $5!$ cancels: $\dfrac{8!}{5!} = 8 \times 7 \times 6$.
- $8 \times 7 = 56$, and $56 \times 6 = 336$.
Answer: $\dfrac{8!}{5!} = 336$.
- Write $(n+1)! = (n+1) \times n \times (n-1)!$.
- Substitute: $(n+1) \times n \times (n-1)! = 12 \times (n-1)!$.
- Cancel $(n-1)!$ from both sides: $(n+1)\,n = 12$, i.e. $n^2 + n - 12 = 0$.
- Factorise: $(n+4)(n-3) = 0$, giving $n = 3$ or $n = -4$.
- A factorial needs a non-negative integer, so reject $n = -4$.
Answer: $n = 3$.
- Thousands place cannot be $0$, so it has $5$ choices (any of $1,2,3,4,5$).
- Hundreds place: $0$ is now allowed again, but one non-zero digit is used — $5$ choices remain ($0$ plus the four unused).
- Tens place: $4$ choices remain. Units place: $3$ choices remain.
- Total $= 5 \times 5 \times 4 \times 3 = 300$.
Answer: $300$ four-digit numbers.
- Multiplication principle: choices in sequence ("and / then") multiply — $m_1 \times m_2 \times \cdots$.
- Addition principle: mutually exclusive alternatives ("or") add — $m + n$.
- Factorial: $n! = n \times (n-1) \times \cdots \times 1$, with the recursion $n! = n \times (n-1)!$.
- By convention $0! = 1$ — forced by the recursion and the single empty arrangement.
- Simplify factorial ratios by cancelling, e.g. $\dfrac{8!}{5!} = 8 \times 7 \times 6$ — never expand fully.
Permutations
A permutation is an arrangement of objects in a definite order. The instant the question cares about which object goes where — first place versus second, captain versus vice-captain, the order of letters in a word — you are counting permutations.
The number of permutations of $n$ distinct objects taken $r$ at a time is written ${}^{n}P_{r}$ (read "$n$ permute $r$"). By the multiplication principle, the first slot has $n$ choices, the second $n-1$, and so on for $r$ slots:
Two special cases fall straight out of the formula. Arranging all $n$ objects gives ${}^{n}P_{n} = \dfrac{n!}{0!} = n!$, and arranging none gives ${}^{n}P_{0} = 1$.
Permutations with repetition allowed. If each of the $r$ positions may use any of the $n$ objects again, every slot independently has $n$ choices, so the count is simply $n^r$. This is the rule for things like PIN codes or number plates where digits may repeat.
Permutations of objects not all distinct. When the collection contains repeated objects, swapping two identical objects produces the same arrangement, so the plain $n!$ overcounts. If among $n$ objects one kind repeats $p$ times, another $q$ times, another $s$ times, the distinct arrangements number:
Restrictions are the heart of exam permutation problems — "vowels together", "begins with a consonant", "two particular people not adjacent". The reliable strategy: fix the restricted positions first, count the freedom that remains, and for "together" conditions glue the bound objects into a single block, arrange the blocks, then multiply by the internal arrangements of the block.
| Scenario | Condition | Count |
|---|---|---|
| $r$ from $n$, no repetition | order matters | $\dfrac{n!}{(n-r)!}$ |
| $r$ slots, repetition allowed | order matters | $n^{r}$ |
| All $n$, some alike | $p,q,\dots$ identical | $\dfrac{n!}{p!\,q!\cdots}$ |
Deeper Insight — every permutation rule is really a correction to $n!$: It helps to see all three formulas as one idea under three conditions. The starting point is $n!$, the count of arrangements when every object is distinct and all are used. From there you adjust. If you only fill $r$ of the slots, you divide away the arrangements of the $n-r$ leftovers, giving $\dfrac{n!}{(n-r)!}$. If objects may repeat, you abandon the descending product entirely and use $n^r$, because nothing is ever "used up". If some objects are identical, you divide out the $p!,\,q!,\dots$ ways those clones could swap among themselves without changing what you see. Recognising which adjustment a problem demands — and resisting the urge to plug into the first formula you remember — is the skill that separates a confident solver from a guesser. The single question that settles it every time: does order matter, and are the objects truly distinct?
- The three offices are distinct, so order matters — this is a permutation of $10$ taken $3$ at a time.
- ${}^{10}P_{3} = \dfrac{10!}{(10-3)!} = \dfrac{10!}{7!} = 10 \times 9 \times 8$.
- $10 \times 9 = 90$, and $90 \times 8 = 720$.
Answer: $720$ ways.
- MATHEMATICS has $11$ letters. Count repeats: M appears $2$ times, A appears $2$ times, T appears $2$ times; H, E, I, C, S appear once each.
- With objects not all distinct, the count is $\dfrac{11!}{2!\,2!\,2!}$.
- $11! = 39{,}916{,}800$ and $2!\,2!\,2! = 8$.
- $\dfrac{39{,}916{,}800}{8} = 4{,}989{,}600$.
Answer: $4{,}989{,}600$ distinct arrangements.
- Repetition is allowed, so each of the $4$ positions independently has all $26$ letters available.
- By the multiplication principle the count is $26 \times 26 \times 26 \times 26 = 26^{4}$.
- $26^2 = 676$, and $676^2 = 456{,}976$.
Answer: $26^{4} = 456{,}976$ codes.
- EQUATION has $8$ distinct letters. The vowels are E, U, A, I, O (five vowels); the consonants are Q, T, N (three consonants).
- Glue the five vowels into a single block. We now arrange this block together with the $3$ consonants — that is $4$ items in a row: $4! = 24$ ways.
- Within the block, the $5$ vowels can be ordered among themselves in $5! = 120$ ways.
- Multiply: $4! \times 5! = 24 \times 120 = 2{,}880$.
Answer: $2{,}880$ arrangements.
- Write each side out: ${}^{n}P_{4} = n(n-1)(n-2)(n-3)$ and ${}^{n}P_{2} = n(n-1)$.
- The equation becomes $n(n-1)(n-2)(n-3) = 20\,n(n-1)$.
- Since $n \ge 4$, divide both sides by $n(n-1)$: $(n-2)(n-3) = 20$.
- Expand: $n^2 - 5n + 6 = 20 \Rightarrow n^2 - 5n - 14 = 0 \Rightarrow (n-7)(n+2) = 0$.
- So $n = 7$ or $n = -2$; reject the negative root.
Answer: $n = 7$.
- For the number to be even, the units digit must be one of $2, 4, 6$ — that is $3$ choices for the last position.
- The remaining $4$ positions are filled from the $6$ digits left, in order, without repetition: ${}^{6}P_{4} = 6 \times 5 \times 4 \times 3 = 360$.
- Multiply by the choices for the units digit: $360 \times 3 = 1{,}080$.
Answer: $1{,}080$ even numbers.
- A permutation is an ordered arrangement; use it whenever position matters.
- ${}^{n}P_{r} = \dfrac{n!}{(n-r)!}$; in particular ${}^{n}P_{n} = n!$ and ${}^{n}P_{0} = 1$.
- With repetition allowed, $r$ slots from $n$ objects give $n^{r}$ arrangements.
- Objects not all distinct: divide by the factorials of each repeat — $\dfrac{n!}{p!\,q!\cdots}$.
- "Together" restrictions: treat the bound group as one block, then multiply by its internal arrangements.
Combinations
A combination is a selection of objects where order does not matter. Choosing a committee, a hand of cards, a set of questions to attempt — in each case the group $\{A, B, C\}$ is the same group however you write it. This is the single distinction that separates combinations from permutations.
The number of combinations of $n$ distinct objects taken $r$ at a time is written ${}^{n}C_{r}$ or $\binom{n}{r}$:
The formula is no accident. To arrange $r$ objects you could first select them ($\binom{n}{r}$ ways) and then order them ($r!$ ways), so ${}^{n}P_{r} = \binom{n}{r} \times r!$. Rearranging gives the combination formula directly — a combination is a permutation with the $r!$ internal orderings divided out.
The clearest way to keep the two ideas apart is a side-by-side comparison:
| Aspect | Permutation ${}^{n}P_{r}$ | Combination ${}^{n}C_{r}$ |
|---|---|---|
| Order | matters | does not matter |
| Keyword | arrange, line up, rank | select, choose, committee |
| Formula | $\dfrac{n!}{(n-r)!}$ | $\dfrac{n!}{r!\,(n-r)!}$ |
| Relation | ${}^{n}P_{r} = {}^{n}C_{r} \times r!$ | |
Key properties. Two identities recur throughout the syllabus and are worth knowing by sight. The symmetry property:
Choosing $r$ objects to keep is the same act as choosing the $n-r$ objects to leave behind, so the two counts must agree. This also gives the boundary values ${}^{n}C_{0} = {}^{n}C_{n} = 1$. The Pascal identity:
This is the rule behind Pascal's triangle and a stepping stone to the Binomial Theorem: it says that selections of $r$ from $n+1$ objects split cleanly into those that include a fixed object and those that exclude it.
Deeper Insight — "order matters" is the only question you must answer: Nearly every mistake in this chapter comes from confusing a selection with an arrangement, so train yourself to ask one thing before reaching for any formula: if I shuffle the chosen objects, is it a different outcome? If yes, it is a permutation; if no, it is a combination. A committee of three from ten is $\binom{10}{3} = 120$, but if those three become President, Secretary and Treasurer the answer jumps to ${}^{10}P_{3} = 720$ — exactly $3! = 6$ times larger, because each committee can be ranked in $6$ ways. The symmetry ${}^{n}C_{r} = {}^{n}C_{n-r}$ is more than a shortcut for arithmetic; it reflects a genuine duality between what you take and what you leave, and it is why $\binom{n}{r}$ peaks in the middle and tapers symmetrically. Master the order question and the rest of combinatorics — binomial coefficients, probability, even basic statistics — rests on solid ground.
- A committee has no internal ranking, so order does not matter — this is a combination.
- ${}^{8}C_{3} = \dfrac{8!}{3!\,5!} = \dfrac{8 \times 7 \times 6}{3 \times 2 \times 1}$.
- $8 \times 7 \times 6 = 336$ and $3! = 6$, so $\dfrac{336}{6} = 56$.
Answer: $56$ committees.
- Choose the men and the women separately, then combine the choices (the two selections happen together, so multiply).
- Men: ${}^{6}C_{3} = \dfrac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20$.
- Women: ${}^{4}C_{2} = \dfrac{4 \times 3}{2 \times 1} = 6$.
- Total $= 20 \times 6 = 120$.
Answer: $120$ ways.
- By symmetry, ${}^{n}C_{r} = {}^{n}C_{n-r}$, so ${}^{12}C_{10} = {}^{12}C_{2}$.
- ${}^{12}C_{2} = \dfrac{12 \times 11}{2 \times 1}$.
- $\dfrac{132}{2} = 66$.
Answer: ${}^{12}C_{10} = 66$.
- The order of cards in a hand does not matter, so this is a combination from the $13$ spades.
- ${}^{13}C_{5} = \dfrac{13!}{5!\,8!} = \dfrac{13 \times 12 \times 11 \times 10 \times 9}{5 \times 4 \times 3 \times 2 \times 1}$.
- Numerator: $13 \times 12 \times 11 \times 10 \times 9 = 154{,}440$. Denominator: $5! = 120$.
- $\dfrac{154{,}440}{120} = 1{,}287$.
Answer: $1{,}287$ five-spade hands.
- If ${}^{n}C_{a} = {}^{n}C_{b}$ with $a \ne b$, then by symmetry the indices must satisfy $a + b = n$.
- Here $8 \ne 12$, so $n = 8 + 12$.
- $n = 20$.
Answer: $n = 20$.
- The first $3$ questions must be attempted, so they are fixed — no choice there.
- That leaves $7 - 3 = 4$ more questions to choose from the remaining $10 - 3 = 7$ questions.
- Order of selection does not matter: ${}^{7}C_{4} = {}^{7}C_{3} = \dfrac{7 \times 6 \times 5}{3 \times 2 \times 1}$.
- $\dfrac{210}{6} = 35$.
Answer: $35$ ways.
- A combination is a selection where order is irrelevant; ${}^{n}C_{r} = \dfrac{n!}{r!\,(n-r)!}$.
- Permutation and combination are linked: ${}^{n}P_{r} = {}^{n}C_{r} \times r!$.
- Symmetry: ${}^{n}C_{r} = {}^{n}C_{n-r}$, with ${}^{n}C_{0} = {}^{n}C_{n} = 1$.
- Pascal identity: ${}^{n}C_{r} + {}^{n}C_{r-1} = {}^{n+1}C_{r}$ — the rule behind Pascal's triangle.
- Always ask first: does order matter? Yes → permutation; no → combination.