• 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).

— Combinations

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.

Some values of nCr (notice nCr = nC(n − r): 7C3 = 7C4)
nnC0nC1nC2nC3nC4
51510105
616152015
717213535
818285670

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. 1. What is the value of 7C3?

    1. 210
    2. 35
    3. 21
    4. 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. 2. How many chords can be drawn through 12 points on a circle?

    1. 132
    2. 144
    3. 66
    4. 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. 3. If nC7 = nC4, what is nC2?

    1. 55
    2. 45
    3. 66
    4. 28
    Show answer

    Answer: A. 7 ≠ 4, so 7 + 4 = n and n = 11. Then 11C2 = (11 × 10)/2 = 55.

  4. 4. In how many ways can a team of 2 boys and 3 girls be chosen from 6 boys and 5 girls?

    1. 25
    2. 462
    3. 300
    4. 150
    Show answer

    Answer: D. Boys: 6C2 = 15 ways. Girls: 5C3 = 10 ways. By the multiplication principle, 15 × 10 = 150 teams.

  5. 5. Assertion (A): 10C4 + 10C3 = 11C4. Reason (R): nCr + nC(r − 1) = (n + 1)Cr.

    1. Both A and R are true, and R is the correct explanation of A.
    2. Both A and R are true, but R is not the correct explanation of A.
    3. A is true, but R is false.
    4. 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.

Privacy · Terms · Refunds · Delivery