- Foundation
- About 17 min
- 5 practice questions
Combinations: selections where order does not matter
Tell selections from arrangements, use nCr = n!/(r!(n − r)!), the link nPr = nCr × r!, the results nCr = nC(n − r) and nCr + nC(r − 1) = (n + 1)Cr, and count handshakes, chords, triangles and committees.
If something looks wrong, please tell us.
By the end of this lesson you can
- Decide whether a problem asks for an arrangement (order matters) or a selection (order does not matter).
- Derive nPr = nCr × r! and use nCr = n!/(r!(n − r)!), with nC0 = nCn = 1.
- Use nCr = nC(n − r) and nCₐ = nC_b ⇒ a = b or a + b = n.
- Prove and use nCr + nC(r − 1) = (n + 1)Cr.
- Count handshakes, chords, triangles and committees.
Choosing a team of two players from X, Y and Z gives only three teams: XY, YZ and ZX. The team XY is the same as the team YX, because order does not matter. A selection in which order does not matter is called a combination. Choosing a captain and a vice-captain, on the other hand, is an arrangement, because the two posts are different.
Permutation or combination?
-
Permutation (arrangement)
- Order matters
- Words, numbers, seating, posts
- AB ≠ BA
- Count nPr
-
Combination (selection)
- Order does not matter
- Teams, committees, handshakes
- AB = BA
- Count nCr
The formula for nCr
Let nCr be the number of combinations of n different objects taken r at a time. Each combination of r objects can be arranged in r! ways, and doing this for every combination produces every permutation exactly once. So nPr = nCr × r!, and therefore
nCr = n!/(r!(n − r)!), for 0 ≤ r ≤ n. Also nC0 = nCn = 1 and nCr = nC(n − r).
We define nC0 = 1: there is exactly one way to select nothing. The formula agrees, since n!/(0! n!) = 1. Selecting r objects is the same as rejecting the other n − r, which is why nCr = nC(n − r). A consequence: if nCₐ = nC_b, then a = b or a + b = n.
Pascal's rule
nCr + nC(r − 1) = (n + 1)Cr. Proof: nCr + nC(r − 1) = n!/(r!(n − r)!) + n!/((r − 1)!(n − r + 1)!). Take out n!/((r − 1)!(n − r)!): this leaves 1/r + 1/(n − r + 1) = (n − r + 1 + r)/(r(n − r + 1)) = (n + 1)/(r(n − r + 1)). Multiplying back gives (n + 1)!/(r!(n − r + 1)!) = (n + 1)Cr. Check: 8C3 + 8C2 = 56 + 28 = 84 = 9C3.
Worked example 1: handshakes and chords
(i) Six people each shake hands once with every other person. A handshake is a pair of people, and the pair (A, B) is the same as (B, A), so the count is 6C2 = (6 × 5)/2 = 15. (ii) Ten points lie on a circle. Each chord joins a pair of points: 10C2 = 45 chords. (iii) Triangles with vertices among 8 points, no three of them in a line: 8C3 = (8 × 7 × 6)/(3 × 2 × 1) = 56.
Worked example 2: using nCr = nC(n − r)
(i) 20C18 = 20C2 = (20 × 19)/2 = 190, much quicker than working out 20C18 directly. (ii) If nC5 = nC9, then 5 ≠ 9, so 5 + 9 = n and n = 14. Then nC12 = 14C12 = 14C2 = (14 × 13)/2 = 91.
Worked example 3: a committee
A committee of 2 men and 2 women is to be chosen from 5 men and 4 women. Working: choose the men in 5C2 = 10 ways and, for each choice, the women in 4C2 = 6 ways. By the multiplication principle the committee can be formed in 10 × 6 = 60 ways. Order inside the committee does not matter, so we use combinations, not permutations.
Worked example 4: diagonals of a polygon
How many diagonals does a polygon with 8 sides have? Working: any two of the 8 vertices determine a segment: 8C2 = 28 segments. Of these, 8 are sides. So the number of diagonals is 28 − 8 = 20.
| n | nC0 | nC1 | nC2 | nC3 | nC4 |
|---|---|---|---|---|---|
| 5 | 1 | 5 | 10 | 10 | 5 |
| 6 | 1 | 6 | 15 | 20 | 15 |
| 7 | 1 | 7 | 21 | 35 | 35 |
| 8 | 1 | 8 | 28 | 56 | 70 |
Key takeaways: ask whether order matters. If it does, count permutations; if not, count combinations. nCr = nPr/r! = n!/(r!(n − r)!). Use nCr = nC(n − r) to shorten calculations and Pascal's rule nCr + nC(r − 1) = (n + 1)Cr to combine terms.
Check your understanding
-
1. What is the value of 7C3?
- 210
- 35
- 21
- 42
Show answer
Answer: B. 7C3 = 7!/(3! 4!) = (7 × 6 × 5)/(3 × 2 × 1) = 210/6 = 35. 210 is 7P3, which counts arrangements.
-
2. How many chords can be drawn through 12 points on a circle?
- 132
- 144
- 66
- 24
Show answer
Answer: C. Each chord is fixed by a pair of points, and order does not matter: 12C2 = (12 × 11)/2 = 66.
-
3. If nC7 = nC4, what is nC2?
- 55
- 45
- 66
- 28
Show answer
Answer: A. 7 ≠ 4, so 7 + 4 = n and n = 11. Then 11C2 = (11 × 10)/2 = 55.
-
4. In how many ways can a team of 2 boys and 3 girls be chosen from 6 boys and 5 girls?
- 25
- 462
- 300
- 150
Show answer
Answer: D. Boys: 6C2 = 15 ways. Girls: 5C3 = 10 ways. By the multiplication principle, 15 × 10 = 150 teams.
-
5. Assertion (A): 10C4 + 10C3 = 11C4. Reason (R): nCr + nC(r − 1) = (n + 1)Cr.
- Both A and R are true, and R is the correct explanation of A.
- Both A and R are true, but R is not the correct explanation of A.
- A is true, but R is false.
- A is false, but R is true.
Show answer
Answer: A. By R with n = 10 and r = 4, 10C4 + 10C3 = 11C4. Numerically 210 + 120 = 330 = 11C4. So A is true and follows from R.
Sign in to keep track of the lessons you finish.