How many ways can we choose, arrange or distribute objects? Combinatorics answers without listing every case. This path starts with elementary choices and reaches constraints, repetition, binomial coefficients and probability. Try each idea in the laboratory; finish with a quiz with explained answers.
1. First question: what counts as a different outcome?
With the letters A, B, C, AB and BA are different codes, but the group containing A and B is the same group whichever name comes first. This distinction comes before the formula. Always ask: does order matter? May I reuse an object? Am I using every object or only some?
2. Add alternatives, multiply stages
If I may choose either one of 3 juices or one of 2 teas, these disjoint alternatives give 3+2=5 choices. If a meal needs one of 3 main courses and one of 2 desserts, each course pairs with two desserts: 3×2=6 meals. The product also works when the number of choices changes by stage: choosing two distinct people from 5 as president and deputy gives 5×4=20 outcomes.
3. A tree diagram and the complement
Two coin tosses give HH, HT, TH, TT: each first branch has two second branches, so 2×2=4. For “at least one head”, it is quicker to exclude the only outcome without heads: 4−1=3. Three tosses give 2³−1=7. The complement is especially useful when “at least one” covers many separate cases.
4. Factorials and permutations of all objects
Arrange 4 different books on a shelf. There are 4 choices for the first place, then 3, 2 and 1: 4×3×2×1=4!=24. In general n!=n(n−1)…2×1. By convention 0!=1: there is exactly one arrangement of zero objects, the empty arrangement. If we use all n distinct objects and order matters, the number of permutations is n!.
5. Arrangements: only k objects, order matters
Award gold, silver and bronze to 3 of 5 people: 5×4×3=60. This is not simply a group of three, because swapping gold and silver changes the result. For k≤n, without repetition, D(n,k)=n!/(n−k)!. When k=n, this becomes n!.
6. Sequences with repetition
A 3-digit code permits leading zeros and repeated digits: each position has 10 choices, hence 10³=1000 codes. If instead we require a three-digit number, the first digit cannot be zero: 9×10×10=900. In general, for k positions and n reusable symbols, there are n^k sequences; apply constraints to the affected positions.
7. Combinations: choose without ordering
Choose a committee of 3 from 5 people. The ordered count is 5×4×3=60, but each committee occurs in 3!=6 orders: 60/6=10. Thus C(n,k)=n!/[k!(n−k)!]. Do not divide by k! automatically: do so only if each group was actually counted in all its k! orders. Two useful facts are C(n,0)=1 and C(n,k)=C(n,n−k): selecting who joins is equivalent to selecting who stays out.
8. The decision table
| Question | Repetition | Count | Example |
|---|---|---|---|
| Order matters, k from n | No | n!/(n−k)! | Podium |
| Order matters, k from n | Yes | n^k | Code |
| Order irrelevant, k from n | No | C(n,k) | Committee |
| Order irrelevant, k from n | Yes | C(n+k−1,k) | Repeated ice-cream flavours |
First identify distinguishable objects, then answer the two questions. “Use all?” is a special case: with order and no repetition, the result is n!.
9. Combinations with repetition
I choose 3 scoops of ice cream from 4 flavours; flavours may repeat and scoop order does not matter. Each choice corresponds to four non-negative flavour counts summing to 3. Draw 3 stars for the scoops and 3 bars to separate the 4 flavours: choose the positions of the 3 stars among 3+4−1=6 positions. This gives C(6,3)=20. In general, choosing k items from n unlimited types gives C(n+k−1,k). Items of the same type must be indistinguishable.
10. Identical objects and circular permutations
In ANNA there are 4 letters, but two As and two Ns are identical: exchanging them makes no new word. The count is 4!/(2!2!)=6. More generally, if multiplicities n₁,…,nᵣ sum to n, distinct arrangements number n!/(n₁!…nᵣ!). For 5 distinct people around a round table, if rotating the entire table changes nothing, fix one person and arrange the others: (5−1)!=24. Mirror images remain different unless the problem explicitly says otherwise.
11. Constraints: construct, subtract or split into cases
How many 4-digit codes, leading zeros permitted, contain at least one 7? All codes number 10⁴; codes without a 7 number 9⁴. The answer is 10⁴−9⁴=3439. In how many ways can 5 people line up if Anna and Bruno must stand together? Treat the pair as one block: arrange 4 objects in 4! ways, then swap the two people inside the block in 2! ways. Answer: 4!×2!=48.
12. Avoid double counting: inclusion–exclusion
In a class, 12 students play football, 9 play basketball and 4 play both. Adding 12+9 counts those 4 twice. The number playing at least one sport is 12+9−4=17. For two sets, |A∪B|=|A|+|B|−|A∩B|. With three sets, subtract the three pairwise intersections and add back the triple intersection, which would otherwise be subtracted too much.
13. Pascal, the binomial theorem and multinomials
Combinations obey C(n,k)=C(n−1,k)+C(n−1,k−1): with respect to one fixed person, either we exclude or include them. This yields Pascal’s triangle: 1; 1 1; 1 2 1; 1 3 3 1; 1 4 6 4 1. The row 1,4,6,4,1 is also the coefficient row of (a+b)⁴=a⁴+4a³b+6a²b²+4ab³+b⁴. If 7 distinct objects are distributed into three labelled groups of sizes 2, 3 and 2, the multinomial count is 7!/(2!3!2!)=210. Unlabelled groups may require a further division when equal-sized groups can be swapped.
14. From counting to probability
An urn contains 6 red and 4 blue balls; we draw 3 together, without replacement. There are C(10,3)=120 possible groups. Exactly 2 red means choosing 2 of 6 red and 1 of 4 blue: C(6,2)×C(4,1)=15×4=60. All groups are equally likely, so P=60/120=1/2. If draw order mattered to the question, we could count ordered sequences in both numerator and denominator, but we must not mix the two models.
15. Three mistakes to recognise
- Confusing a code with a number: 007 is a three-digit code, not a three-digit number.
- Dividing when order matters: president and deputy are not a committee.
- Using a formula without checking constraints:
C(n+k−1,k)does not apply if each flavour may be chosen at most once.
16. Test yourself
Before revealing a solution, write down the objects, positions, whether order matters, whether repetition is permitted, and any restrictions.
1. Five different books: how many shelf orders?
We use every distinct object and order matters: 5!=120.
2. From 8 people choose a president and deputy: how many outcomes?
The roles differ and no one fills both: 8×7=56, not C(8,2)=28.
3. From 8 people choose a committee of 2: how many groups?
Swapping the names creates no new group: C(8,2)=8×7/2=28.
4. How many distinct anagrams does MAMMA have?
There are 5 letters, with M repeated 3 times and A twice: 5!/(3!2!)=10.
5. Three scoops from 4 flavours, with repetition: how many choices?
Order is irrelevant and each flavour can repeat: C(4+3−1,3)=C(6,3)=20.
The path is complete when you can justify a formula, not merely recall it. In the laboratory, compare counts with lists of small cases; then take the quiz with explained answers.