A. Counting and Probability · Permutations and Combinations

Combinations: When Order Does Not Matter

A2.1 A2.2About 70 minutes

Learning goals

I can distinguish between permutations and combinations by deciding whether order matters.
I can explain why C(n, r) = P(n, r)/r! and calculate combinations with the formula n!/(r!(n − r)!).
I can use the notation C(n, r), ₙCᵣ and the binomial coefficient "n choose r".
I can use the property C(n, r) = C(n, n − r) and verify a combination count with a different strategy.

Words to know

combination
A selection of objects in which order does not matter. {A, B, C} and {C, B, A} are the same combination.

C(n, r)
The number of combinations of r objects chosen from n distinct objects: C(n, r) = n!/(r!(n − r)!). Also written ₙCᵣ, nCr, or as a binomial coefficient with n above r in large round brackets, read "n choose r".

binomial coefficient
Another name for C(n, r), because these numbers are the coefficients in the expansion of (a + b)ⁿ (lesson 12).

subset
A selection of some (or none, or all) of the objects in a set. A combination of r objects is a subset of size r.

Two kinds of committee

The Ontario curriculum poses this problem. An organization with 10 members is considering two leadership models:

an executive committee: a president, a vice-president, a secretary and a treasurer;
a steering committee: 4 members of equal standing (no titles).

In lesson 4 you found that there are P(10, 4) = 5040 possible executive committees. How many steering committees are there? More, fewer, or the same?

From permutations to combinations

Take any one steering committee, say members A, B, C and D. How many different executive committees use exactly these four people? The 4 people can be assigned to the 4 jobs in 4! = 24 ways.

So the 5040 executive committees fall into groups of 24, and each group is one steering committee:

number of steering committees = 5040 ÷ 4! = 5040 ÷ 24 = 210

This is the key relationship:

C(n, r) = P(n, r) ÷ r! = n! / (r! (n − r)!)

The steering committee is a combination: a selection where order does not matter. Every combination of r objects can be ordered in r! ways, and each ordering is a permutation.

Each steering committee of 4 matches 4! = 24 executive committees (the same people in different jobs). Dividing the permutations by 4! counts the combinations.

	Permutation	Combination
Does order matter?	Yes	No
Example	President, VP, secretary, treasurer	Steering committee of 4
Formula	P(n, r) = n!/(n − r)!	C(n, r) = n!/(r!(n − r)!)
Value for n = 10, r = 4	5040	210
Calculator key	nPr	nCr

Permutations and combinations side by side.

Worked example

Example 1: Handshakes

The Ontario curriculum uses this example: in many Indigenous communities, it is common practice for people to shake hands when they gather. How many handshakes take place when 7 people gather and each person shakes hands once with every other person? Verify using a different strategy.

A handshake is a pair of people, and the pair (Ana, Ben) is the same handshake as (Ben, Ana). Order does not matter, so this is a combination.
C(7, 2) = 7!/(2! × 5!) = (7 × 6)/2 = 21.
Check 1: each of the 7 people shakes 6 hands, giving 7 × 6 = 42. Every handshake was counted twice (once by each person), so 42 ÷ 2 = 21. ✓
Check 2: person 1 shakes 6 new hands, person 2 then shakes 5 new ones, then 4, 3, 2, 1: 6 + 5 + 4 + 3 + 2 + 1 = 21. ✓

21 handshakes.

Seven points with every pair joined. Each segment is one handshake: there are C(7, 2) = 21.

Worked example

Example 2: Pizza toppings

A pizza shop offers 12 toppings. How many different 3-topping pizzas are possible (three different toppings)?

Pepperoni, mushrooms and peppers is the same pizza in any order: combination.
C(12, 3) = 12!/(3! × 9!) = (12 × 11 × 10)/(3 × 2 × 1) = 1320/6 = 220.

220 pizzas.

Useful properties

C(n, 0) = 1 and C(n, n) = 1: there is one way to choose nothing and one way to choose everything.
C(n, 1) = n.
Symmetry: C(n, r) = C(n, n − r). Choosing r objects to take is the same as choosing the n − r objects to leave behind. For example, choosing 2 of 9 students to stay behind decides which 7 go: C(9, 2) = C(9, 7) = 36.

Calculator tip: for C(n, r) with large n, cancel first. C(49, 6) = (49 × 48 × 47 × 46 × 45 × 44)/6! = 13 983 816.

Worked example

Example 3: Revisiting 2 boys and 2 girls

From 4 boys and 5 girls, find the number of ways to choose (a) 2 boys or 2 girls, (b) 2 boys and 2 girls.

Pairs of boys: C(4, 2) = 6. Pairs of girls: C(5, 2) = 10.
(a) Additive principle: 6 + 10 = 16.
(b) Multiplicative principle: 6 × 10 = 60.

(a) 16; (b) 60, the same answers you found by listing in lesson 2, with no listing at all.

Worked example

Example 4: Solving for n

Solve C(n, 2) = 28.

C(n, 2) = n(n − 1)/2. So n(n − 1)/2 = 28, and n(n − 1) = 56.
n² − n − 56 = 0, (n − 8)(n + 7) = 0. Reject n = −7.

n = 8. Check: C(8, 2) = 28 ✓.

Permutation or combination?

Imagine the chosen objects in a different order. Is it a different outcome? Different jobs, places, positions in a code or ranks → permutation. A group, team, committee, hand of cards, set of toppings or handshake → combination. Every combination problem can be solved as "count the permutations, then divide by r!".

Just for fun

There are 13 983 816 ways to choose 6 numbers out of 49 for Lotto 6/49. With two draws a week, a person buying one ticket per draw would wait, on average, about 134 000 years to match all six.

Hands-on activity

Committees at the kitchen table

You need: 5 slips of paper with the names of 5 people (family members, friends or fictional characters) and a pencil.

List every 2-person committee (no titles). Be systematic: pair the first name with each of the others, then the second name with each of those after it, and so on. How many?
Now list every president and vice-president pair. How many? How does this compare with step 1?
List every 3-person committee. Before you start, predict the number using symmetry: choosing 3 to serve is the same as choosing 2 to stay home.
Check all three counts with the formulas C(5, 2), P(5, 2) and C(5, 3).

What to look for: C(5, 2) = 10 committees of 2. P(5, 2) = 20 president/vice-president pairs, exactly 2! = 2 times as many, since each committee can assign the two titles in 2 ways. C(5, 3) = 10, the same as C(5, 2).

Your turn

Evaluate C(8, 3).

Evaluate C(10, 4).

A pizza shop offers 12 toppings. How many 3-topping pizzas (three different toppings) are possible?

Ten people at a meeting each shake hands once with every other person. How many handshakes?

Lotto 6/49 players choose 6 different numbers from 1 to 49. How many different selections are possible?

Show that C(9, 2) = C(9, 7) and explain why in words.

Solve C(n, 2) = 28.

More practice: warm-up

Evaluate C(5, 2).

Evaluate C(6, 6).

Evaluate C(7, 0).

Evaluate C(6, 1).

You will take 2 of your 6 books on a trip. How many choices are there? Is this a permutation or a combination?

More practice: on your own

How many 5-member committees can be chosen from 15 people?

Eight points lie on a circle. How many segments join pairs of points? How many triangles have three of the points as vertices?

How many diagonals does a 10-sided polygon have?

A teacher chooses 4 of the 25 students in a class to represent the class at a conference. How many choices are there?

Find n if C(n, 3) = C(n, 5). Then find the value of C(n, 3).

Challenge

Prove algebraically that C(n, r) = C(n, n − r).

Solve C(n + 1, 3) = 2 C(n, 2) for n ≥ 2.

In a round-robin tournament every team plays every other team once. A league schedules 66 games. How many teams are in the league?

Check your understanding

Quiz

What is C(6, 2)?

Which relationship between permutations and combinations is correct?

From 10 members, how many steering committees of 4 equal members are possible?

Seven people each shake hands once with every other person. How many handshakes?

Which situation is counted with combinations?

Which number equals C(20, 17)?

For parents and teachers

Big idea (A2.1, A2.2): a combination is a selection where order does not matter. Every combination of r objects corresponds to r! permutations, so C(n, r) = P(n, r)/r!. The curriculum's committee example (executive vs steering committee) shows this link directly.

How to help: For each problem, ask your teen to say out loud whether rearranging the chosen items gives a new outcome. Have them verify small answers by listing, as in the handshake example.

Common difficulties:

Using permutations for teams, committees or hands of cards (order does not matter).
Forgetting to divide by r! when converting from permutations.
Calculator entry: type n, then nCr, then r. Check: C(6, 2) must give 15.
Not recognizing the symmetry C(n, r) = C(n, n − r), which can make calculations shorter.