Combinations

A school committee needs 5 members chosen from a class of 20 — does it matter whether Aditi is picked before or after Rohan? No: once the five names are on the list, the order they were chosen in is irrelevant. That single observation is the whole idea behind a combination: a selection of objects where order does not matter, as opposed to a permutation, where it does. Combinations decide committees, teams, hands of cards, and subsets of any kind, and the counting tool built for them, $^nC_r$ , turns out to be one of the most reused symbols in mathematics — it reappears almost immediately as the coefficients of the Binomial Theorem. This article builds $^nC_r$ from first principles, proves its key symmetry and recurrence properties, and drills the two skills examiners test hardest: choosing between $P$ and $C$ , and handling "at least / at most" selections by summing cases.

The core insight

The number of ways to choose $r$ objects from $n$ distinct objects when order does not matter is $^nC_r=\dfrac{n!}{r!(n-r)!}$ , obtained by dividing the ordered count $^nP_r$ by the $r!$ orderings each unordered selection can be arranged in.

The core idea

From permutations to combinations. Every ordered arrangement of $r$ objects out of $n$ (a permutation, $^nP_r$ ) can be built in two stages: first choose which $r$ objects to use, then arrange those $r$ objects in some order. Each unordered choice of $r$ objects can be arranged in exactly $r!$ different ways, so

^{n}C_r = \frac{^{n}P_r}{r!} = \frac{n!}{r!\,(n-r)!},

where: $n$ is the total number of distinct objects available, $r$ is the number chosen, $n!$ (read " $n$ factorial") is $n\times(n-1)\times\cdots\times1$ , and $^nC_r$ counts the subsets of size $r$ , with no regard for the order the members were picked in.

Two defining properties fall out immediately. Since choosing which $r$ objects to include is the same act as choosing which $n-r$ objects to exclude,

^{n}C_r = {}^{n}C_{n-r}.

And the two extreme cases — choosing nothing, or choosing everything — can each be done in exactly one way, so $^{n}C_0={}^{n}C_n=1$ , while choosing a single object can be done in $n$ ways, so $^nC_1=n$ .

Pascal's rule. A third identity links consecutive rows of choices and is the engine behind Pascal's triangle:

^{n+1}C_r = {}^{n}C_{r-1}+{}^{n}C_r.

The next section derives this rather than just stating it, since it is the one property students are asked to prove, not just apply.

Deciding $P$ versus $C$ . Ask one question of any counting problem: if two selected objects were swapped, would the outcome count as different? A podium finish, a phone PIN, or a seating plan all answer "yes" — use $^nP_r$ . A committee, a hand of cards, or a subset of questions to attempt all answer "no" — use $^nC_r$ . Getting this one question right is worth more marks than memorising either formula.

Figure

Pascal's triangle for rows zero through four with each entry equal to a value of nCr, showing the symmetric shape and the recurrence where each interior entry is the sum of the two entries above it

Worked example

Derivation goal: prove Pascal's rule $^{n+1}C_r = {}^{n}C_{r-1}+{}^{n}C_r$ by a counting argument (not by expanding factorials), so that the identity is understood as a statement about splitting a group of $n+1$ objects into "one special object" and "the rest," which is exactly the kind of reasoning ISC examiners expect for a "prove that" question on this topic.

Derivation AProving Pascal's rule by a counting argument

The goal is to show that the number of ways to choose $r$ objects from a set of $n+1$ objects can be split, without any algebra on factorials, into two mutually exclusive and exhaustive cases built around a single fixed object — and that adding those two cases reproduces $^{n+1}C_r$ exactly, which is the standard proof examiners expect for this named identity.

Step 1. Set up the split. Take the set of $n+1$ objects and mark one of them, say object $X$ , as special; the remaining $n$ objects form a second group. Any selection of $r$ objects from the full set of $n+1$ either contains $X$ or it does not — these two possibilities cannot both happen, and between them they cover every possible selection.

Step 2. Count the selections that contain $X$ . If $X$ is definitely included, the remaining $r-1$ objects of the selection must come from the other $n$ objects, and order does not matter among them. That can be done in $^nC_{r-1}$ ways.

Step 3. Count the selections that exclude $X$ . If $X$ is definitely left out, all $r$ objects of the selection must come from the other $n$ objects. That can be done in $^nC_r$ ways.

Step 4. Add the two mutually exclusive cases. Since every selection of $r$ from $n+1$ falls into exactly one of the two cases above, the total count is the sum:

^{n+1}C_r = {}^{n}C_{r-1} + {}^{n}C_r.

This matches the direct count $^{n+1}C_r$ , confirming the identity, and the same argument is exactly why each entry of Pascal's triangle equals the sum of the two entries above it.

A committee of 5 is to be formed from 7 men and 4 women, and must contain exactly 3 men and 2 women. Choosing 3 men from 7 (order irrelevant, since committee membership does not rank people):

^7C_3 = \frac{7!}{3!\,4!} = \frac{7\times6\times5}{3\times2\times1}=35.

Choosing 2 women from 4:

^4C_2 = \frac{4!}{2!\,2!} = \frac{4\times3}{2\times1}=6.

Step 1. Identify that the two selections are independent choices from disjoint groups, so the fundamental principle of counting says multiply, not add: $\text{Total} = 35\times6=210$ .

Step 2. Extend to "at least 3 men." If instead the committee of 5 needed at least 3 men from the same 7 men and 4 women, the valid case splits are 3 men/2 women, 4 men/1 woman, and 5 men/0 women — three mutually exclusive cases that must be summed, not multiplied together:

^7C_3\cdot{}^4C_2 + {}^7C_4\cdot{}^4C_1 + {}^7C_5\cdot{}^4C_0 = 35(6)+35(4)+21(1) = 210+140+21=371.

Answer: exactly 3 men and 2 women can be chosen in $\mathbf{210}$ ways; at least 3 men can be chosen in $\mathbf{371}$ ways.

Competitive stretch

Find $n$ if $^nC_5={}^nC_9$ . Using $^nC_r={}^nC_{n-r}$ , this equality holds either if $5=9$ (impossible) or if $5$ and $9$ are the complementary pair, i.e. $5+9=n$ , giving $n=14$ . Check: $^{14}C_5={}^{14}C_{14-5}={}^{14}C_9$ ✓, confirming the answer without computing either factorial value.

Common traps

Using $^nP_r$ for an unordered selection — if listing the same group in a different order should not count as a new outcome, it is a combination, not a permutation.
Forgetting the symmetry $^nC_r={}^nC_{n-r}$ and missing the second valid solution in equation-type problems, as in the competitive stretch above where $r_1+r_2=n$ is the other case to test.
In compound problems, multiplying counts from independent groups by permutations instead of combinations when the sub-selections themselves are unordered — check each stage of the problem separately before combining.
In "at least" / "at most" problems, forgetting to sum every valid case boundary, or double-counting a case that belongs to more than one split — list the cases explicitly before computing any values.

Ask the tutor: if you are unsure whether a word problem wants a permutation or a combination, ask the AI tutor to test it with "would swapping the order of two chosen items change the outcome?"

How do I quickly decide whether a word problem needs P or C?

Ask whether swapping two of the selected items would give a genuinely different outcome for the problem. Ranking, seating, passwords, and podium finishes all change when you swap — use $^nP_r$ . Committees, hands of cards, and subsets of questions to attempt do not change when you swap — use $^nC_r$ . If the question never mentions an order, position, or rank, it is almost always a combination.

Why does dividing nPr by r factorial turn an ordered count into an unordered one?

Because $^nP_r$ counts every ordered arrangement of $r$ chosen objects, and any fixed set of $r$ objects can itself be arranged in exactly $r!$ different orders. So $^nP_r$ over-counts each unordered selection $r!$ times — once for every possible ordering of that same group. Dividing by $r!$ collapses all those duplicate orderings back down to a single count per selection, which is exactly $^nC_r$ .

In at least or at most problems, how do I know I have covered every case without overlap?

List the possible values of the restricted quantity from its minimum to its maximum given the constraints, and check that each committee size or category count you need is hit exactly once. For "at least 3 men" in a 5-person committee from 7 men and 4 women, the men-count can only be 3, 4, or 5 (since only 4 women exist, 5 men and 0 women is still valid but 6 or 7 men would leave a committee larger than 5). Writing out the men/women split for each case before computing any $^nC_r$ values is the safest way to avoid missing or repeating a case.

Combinations

The core idea

Worked example

Competitive stretch

Common traps

Before this

Where this leads