A. Counting and Probability · Permutations and Combinations

Permutation or Combination? Choosing the Right Tool

A2.1 A2.2 A2.3About 70 minutes

Learning goals

I can decide whether a situation calls for a permutation, a combination, nʳ, n!/(a! b! …) or 2ⁿ.
I can solve problems that combine choosing and arranging.
I can check an answer by solving the problem in two different ways.
I can explain the advantages of permutations and combinations over lists and tree diagrams.

Words to know

choose, then arrange
A two-stage strategy: first select the objects with combinations, then arrange the selected objects with permutations, and multiply.

labelled vs unlabelled groups
Groups with different roles (a canoe group and a hiking group) are labelled; identical groups (two canoe teams doing the same trip) are unlabelled, and swapping them does not give a new split.

Which tool?

You now have several counting tools: the additive and multiplicative principles, n!, P(n, r), nʳ, n!/(a! b! …), C(n, r) and 2ⁿ. The hardest part of most counting problems is not the arithmetic. It is choosing the right tool.

Compared with listing outcomes, drawing a tree diagram, making a chart or drawing a Venn diagram, these formulas have one huge advantage: they count sets far too large to list (C(49, 6) is nearly 14 million) quickly and without missing or repeating outcomes. Lists and trees are still useful for small cases and for checking a formula.

The flowchart below is a good first step for any problem.

A decision flowchart. Start with "does order matter?", then check for repetition, identical objects and whether the number chosen is fixed.

Worked example

Example 1: Sorting situations

Decide which tool fits each situation, and calculate. (a) 5 starters chosen from a basketball team of 12, with no positions. (b) First, second and third place at a science fair with 20 projects. (c) A code of the form letter-digit-letter digit-letter-digit, like a Canadian postal code, if every letter and digit could be used. (d) Arrangements of the letters of ALGONQUIN.

(a) A group with no roles: order does not matter. C(12, 5) = 792.
(b) The places are different: order matters, no repeats. P(20, 3) = 20 × 19 × 18 = 6840.
(c) Order matters and repeats are allowed: 26 × 10 × 26 × 10 × 26 × 10 = 26³ × 10³ = 17 576 000. (Canada Post does not use every letter, so the real number is smaller.)
(d) Arrange all 9 letters; N appears twice: 9!/2! = 181 440.

(a) 792; (b) 6840; (c) 17 576 000; (d) 181 440.

Choose, then arrange

Many problems ask you to select some objects and then arrange them. Do it in two stages and multiply:

(ways to choose) × (ways to arrange the chosen objects)

When all the objects are distinct and you arrange every chosen object in a row, this is exactly P(n, r) = C(n, r) × r!. But the two-stage method also works when the selection has conditions that P(n, r) alone cannot handle.

Two stages: choose which 4 people sit, then arrange them. C(9, 4) × 4! gives the same answer as P(9, 4).

Worked example

Example 2: Choosing letters, then arranging them

How many 5-letter arrangements (any arrangement, real word or not) contain 2 different vowels and 3 different consonants? Use A, E, I, O, U as the 5 vowels and the other 21 letters as consonants.

Choose the vowels: C(5, 2) = 10.
Choose the consonants: C(21, 3) = 1330.
Arrange the 5 chosen letters (all different): 5! = 120.
Multiply: 10 × 1330 × 120 = 1 596 000.

1 596 000 arrangements.

Worked example

Example 3: Two methods, one answer

A 5-person committee is chosen from 12 people, and one member is named chair. How many outcomes are possible? Solve it in two ways.

Method 1: choose the committee, then the chair from its members: C(12, 5) × 5 = 792 × 5 = 3960.
Method 2: choose the chair first from all 12, then the other 4 members from the remaining 11: 12 × C(11, 4) = 12 × 330 = 3960.
The two methods agree, which is a strong check.

3960 outcomes.

Worked example

Example 4: Different jobs or identical jobs?

Ten volunteers are available for a snow-shovelling day at a community centre. How many ways can 3 of them be given (a) three different jobs (front walk, ramp, parking lot), (b) three identical jobs (general shovelling)?

(a) The jobs are different, so assigning Ana to the ramp differs from assigning her to the walk: P(10, 3) = 720.
(b) The jobs are identical, so only the group of 3 matters: C(10, 3) = 120.
Check: each group of 3 can be given the three different jobs in 3! = 6 ways, and 120 × 6 = 720 ✓.

(a) 720; (b) 120.

Common traps

Ordering a combination by accident: "choose 2 people, then 2 more people for the same committee" counts each committee several times. Choose the whole committee at once.
Labelled vs unlabelled groups: splitting 10 people into a group of 4 for canoeing and 6 for hiking is C(10, 4) = 210. Splitting them into two identical groups of 5 is C(10, 5) ÷ 2 = 126, because choosing group A = {1, 2, 3, 4, 5} is the same split as choosing group A = {6, 7, 8, 9, 10}.
Check reasonableness: a combination count is never larger than the matching permutation count.

Just for fun

Canada Post gives Santa Claus his own postal code: H0H 0H0. It fits the letter-digit-letter, digit-letter-digit pattern perfectly, and the zeros look a lot like the letter O. Ho ho ho!

Hands-on activity

Sort the situations

You need: 10 slips of paper, a pencil and three labelled areas on a table: Permutation, Combination, Other (nʳ, identical objects, or a principle).

Write one situation on each slip:

Choosing 4 friends to invite to a sleepover.
Setting a 4-digit PIN.
Electing a president and a treasurer from a club.
Arranging the letters of the word OTTAWA.
Picking 6 numbers for a lottery ticket.
Ranking your top 3 favourite movies.
Choosing 2 of 5 snacks for a road trip.
Seating 5 people in a row of 5 seats.
Choosing any number of 6 pizza toppings.
Assigning 3 different chores to 3 of your 5 family members.

Sort the slips, then calculate each count. For any slip you are unsure of, ask: "If I swap two chosen items, is it a different outcome?"

What to look for: Permutation: 3 (P(n, 2) for the club size), 6 (P(n, 3)), 8 (5! = 120), 10 (P(5, 3) = 60). Combination: 1 (C(n, 4)), 5 (C(49, 6) for Lotto 6/49), 7 (C(5, 2) = 10). Other: 2 (10⁴ = 10 000, repetition allowed), 4 (6!/(2! 2!) = 180, identical letters), 9 (2⁶ = 64 subsets).

Your turn

How many ways can 5 starters be chosen from a basketball team of 12 if positions do not matter?

How many ways can first, second and third place be awarded among 20 science fair projects?

How many codes of the form A1A 1A1 (letter, digit, letter, digit, letter, digit) are possible if every letter and digit could be used?

Choose 3 of your 8 novels and arrange them on a shelf. How many arrangements?

Choose a team of 4 from 9 people, then name one team member captain. How many outcomes?

How many distinguishable arrangements are there of the letters of ALGONQUIN?

A student chooses 4 courses from 9 electives. How many choices?

More practice: warm-up

Permutation or combination: choosing 3 friends to invite to a movie?

Which tool: setting a 4-digit PIN?

Permutation or combination: electing a president and a treasurer?

Permutation or combination: being dealt a 5-card hand?

Which tool: arranging 6 books on a shelf?

More practice: on your own

A 6-person committee is chosen from 10 people: one chair, one secretary (different people), and 4 regular members. How many committees?

How many 5-letter arrangements contain 2 different vowels and 3 different consonants?

Choose 4 of 9 people and seat them in a row of 4 chairs. Find the count two ways.

Three prizes are given to 3 of 10 people (one prize each). Find the number of ways if the prizes are (a) all different, (b) identical.

A 5-person committee with a chair is chosen from 12 people. Solve it in two different ways.

Challenge

How many distinguishable 4-letter arrangements can be made from the letters of ONTARIO (O appears twice)?

Choose 3 of 6 different math books and 2 of 5 different history books, and arrange the 5 chosen books on a shelf with the math books together. How many arrangements?

Ten people are split into two groups of 5. How many ways if (a) one group goes canoeing and the other hiking, (b) both groups do the same canoe trip (the groups are not labelled)?

Check your understanding

Quiz

Which situation is a combination?

A 5-person committee is chosen from 12 people, and one member is named chair. How many outcomes?

In how many ways can 4 of 9 people be seated in a row of 4 chairs?

How many codes of the form letter-digit-letter digit-letter-digit are possible if every letter and digit could be used?

What is the main advantage of permutation and combination formulas over tree diagrams?

Three identical gift cards are given to 3 of 10 people (one each). How many ways?

For parents and teachers

Big idea (A2.1, A2.2, A2.3): the real skill is choosing the right tool. Ask: does order matter? Can objects repeat or are some identical? Is the number chosen fixed? Then combine tools with "choose, then arrange", cases and complements. Solving a problem two ways is the best check.

How to help: Use the sorting activity: have your teen explain each choice out loud. Ask for a second method on a few questions; when two methods agree, the answer is almost certainly right.

Common difficulties:

Using P when the chosen objects have no roles (or C when they do).
Choosing a committee in pieces ("2 people, then 2 more"), which counts each committee several times.
Forgetting to divide by the number of ways to swap identical (unlabelled) groups.
Over-relying on calculator keys without thinking about the situation.