A. Counting and Probability · Permutations and CombinationsPermutations with Repetition and with Identical Objects
A2.1 A2.3About 65 minutes
Learning goals- I can count arrangements when repetition is allowed, using nʳ.
- I can explain why identical objects reduce the number of distinct arrangements.
- I can use n!/(a! b! c! …) to count arrangements with identical objects.
- I can combine this formula with conditions such as fixed positions.
Words to know
repetition allowed
Each object can be used again, so every position has all n choices: nʳ arrangements of length r.
identical objects
Objects that cannot be told apart, such as the three A's in CANADA. Swapping them does not make a new arrangement.
distinguishable arrangement
An arrangement that looks different from every other one. Arrangements that differ only by swapping identical objects count once.
permutations with identical objects
n objects, of which a are alike, b are alike, and so on, can be arranged in n!/(a! b! …) distinguishable ways.
Two new twists
So far, every permutation used distinct objects, each used at most once. Two common situations break those rules:
- Repetition is allowed. A bike-lock code can be 7-7-3-7.
- Some objects are identical. The word CANADA has three A's. Swapping two of them does not create a new word.
Both situations are easy to handle once you see what changes.
Repetition allowed: nʳ
If each of r positions can be filled by any of n objects, and repeats are allowed, the multiplicative counting principle gives
n × n × … × n = nʳ
For example, 3-letter codes with repetition: 26³ = 17 576. Compare with no repetition: P(26, 3) = 26 × 25 × 24 = 15 600. Allowing repeats always gives at least as many arrangements.
You already used nʳ in lessons 1 and 2. The important skill is recognizing which situation you are in: read the problem for words like "may be repeated", "can be used more than once" or "different digits".
Identical objects: divide out the swaps
How many distinguishable arrangements does the word BOO have?
Pretend for a moment that the O's are different: B, O₁, O₂. Then there are 3! = 6 arrangements. But when the labels are erased, O₁O₂ and O₂O₁ look the same, so the 6 arrangements collapse in pairs. Each real arrangement was counted 2! times. So there are 6 ÷ 2! = 3: BOO, OBO, OOB.
The formula
The number of distinguishable arrangements of n objects, where a are alike of one kind, b are alike of another kind, c of another, and so on, is
n! / (a! × b! × c! × …)
Objects that appear only once contribute 1! = 1, so you can leave them out of the denominator.
CANADA: 6 letters with three A's: 6!/3! = 720/6 = 120.
This formula will return in lesson 11: every shortest route on a city grid is an arrangement of identical "west" and "south" moves.
Worked exampleExample 1: An Ontario place name
How many distinguishable arrangements are there of the letters of MISSISSAUGA?
- Count the letters: M, I, S, S, I, S, S, A, U, G, A = 11 letters.
- Repeated letters: S appears 4 times, I appears 2 times, A appears 2 times. M, U and G appear once.
- 11!/(4! × 2! × 2!) = 39 916 800 / (24 × 2 × 2) = 39 916 800 / 96 = 415 800.
Worked exampleExample 2: Flags on a pole
A signal is made by hanging 5 flags side by side on a rope: 3 identical green flags (G) and 2 identical yellow flags (Y). How many different signals are possible?
- 5 objects: 3 alike (G) and 2 alike (Y).
- 5!/(3! × 2!) = 120/(6 × 2) = 10.
10 signals. They are all drawn below.
All 10 signals. Each signal is fixed by choosing which 2 of the 5 places get Y flags; the other 3 get G.Worked exampleExample 3: Identical objects with a condition
How many distinguishable arrangements of TORONTO (a) are there in total, (b) begin with T, (c) begin and end with O?
- Letters: T × 2, O × 3, R, N (7 letters).
- (a) 7!/(2! × 3!) = 5040/12 = 420.
- (b) Put a T first. The other 6 letters are T, O, O, O, R, N: 6!/3! = 720/6 = 120.
- (c) Put an O at each end. The middle 5 letters are T, T, O, R, N: 5!/2! = 60.
(a) 420; (b) 120; (c) 60.
Worked exampleExample 4: Coin flips
A coin is flipped 8 times. How many sequences of results contain exactly 3 heads?
- A sequence with exactly 3 heads is an arrangement of HHHTTTTT: 8 objects, 3 alike and 5 alike.
- 8!/(3! × 5!) = 40 320/(6 × 120) = 56.
56 sequences. Notice that this also counts the ways to choose which 3 of the 8 flips are heads. That is a combination, the subject of the next lesson.
Which formula?
Distinct objects, no repeats, r of them in order: P(n, r). Any of n choices in each of r positions (repeats allowed): nʳ. Arrange all n objects, some identical: n!/(a! b! …). If a question asks for only some of a set of letters with repeats (for example 4 letters from PEPPER), none of the formulas fit directly: split into cases by which letters are repeated.
Just for funMISSISSAUGA can be rearranged in 415 800 different ways, and only one of them gets you to the right city.
Hands-on activityErasing the labels
You need: 4 small squares of paper, a pencil and an eraser.
- Write B, O, O and K on the squares. Lightly add a small 1 and 2 under the two O's so they are O₁ and O₂.
- List all arrangements of B, O₁, O₂, K. (Work systematically: start with B first, then O₁ first, and so on.) How many are there?
- Erase the little numbers. Go through your list and circle each arrangement that now looks like one you already have. How many different-looking arrangements are left?
- Explain the connection between your two counts and 2!.
- Predict, then check by listing, the number of arrangements of the letters of NOON.
What to look for: 4! = 24 labelled arrangements, but only 24 ÷ 2! = 12 distinguishable ones, because each word appears twice (O₁ and O₂ swapped). NOON has two N's and two O's: 4!/(2! × 2!) = 6 (NOON, NONO, NNOO, ONON, OONN, ONNO).
Your turn
1How many distinguishable arrangements are there of the letters of OTTAWA?
6 letters with T × 2 and A × 2: 6!/(2! × 2!) = 720/4 = 180.
2How many different 5-digit numbers can be made by arranging the digits 1, 1, 2, 2, 2?
5!/(2! × 3!) = 120/12 = 10.
3How many distinguishable arrangements are there of the letters of TORONTO?
7!/(2! × 3!) = 5040/12 = 420.
4A coin is flipped 8 times. How many sequences have exactly 3 heads?
5How many 3-letter codes can be made from the letters A, B, C, D and E if letters may be repeated?
6How many distinguishable arrangements are there of MISSISSAUGA?
11!/(4! × 2! × 2!) = 415 800.
7How many arrangements of TORONTO begin with T?
The other letters T, O, O, O, R, N: 6!/3! = 120.
More practice: warm-up
1How many distinguishable arrangements are there of AAB?
3!/2! = 3: AAB, ABA, BAA.
2How many distinguishable arrangements are there of BOOK?
3How many 3-digit codes can be made from the digits 1 to 4 if digits may repeat?
4How many distinguishable arrangements are there of AAAB?
5How many distinguishable arrangements are there of AABB?
More practice: on your own
1How many arrangements of CANADA begin and end with A?
Fix an A at each end. The middle 4 letters C, N, D, A are all different: 4! = 24.
2How many 5-digit numbers made by arranging 3, 3, 5, 5, 5 are greater than 50 000?
The first digit must be 5. Arrange the other four digits 3, 3, 5, 5: 4!/(2! × 2!) = 6.
3How many distinguishable arrangements are there of SASKATOON?
9 letters: S × 2, A × 2, O × 2, K, T, N. 9!/(2! × 2! × 2!) = 362 880/8 = 45 360.
4A 4-character password uses letters and digits (36 symbols, repeats allowed) and must start with a letter. How many passwords?
26 × 36 × 36 × 36 = 26 × 46 656 = 1 213 056.
5Seven flags are hung in a row: 4 identical green, 2 identical yellow and 1 blue. How many signals?
7!/(4! × 2!) = 5040/48 = 105.
Challenge
1How many distinguishable arrangements of BANANA have the two N's not next to each other?
Total: 6!/(3! × 2!) = 60. N's together: treat NN as one block; arrange B, A, A, A, NN: 5!/3! = 20. Apart: 60 − 20 = 40.
2How many distinguishable 4-letter arrangements can be made from the letters of PEPPER (P × 3, E × 2, R × 1)?
Cases by which letters are used. Three P's + one other (E or R): 2 × 4!/3! = 8. Two P's + two E's: 4!/(2! 2!) = 6. A pair plus two different letters: PP + E + R or EE + P + R, each 4!/2! = 12, so 24. Total 8 + 6 + 24 = 38.
3A 10-question true/false answer key has exactly 7 "true" answers. How many such keys are there? Explain why the answer also equals the number of ways to choose 7 questions out of 10.
Arrange 7 T's and 3 F's: 10!/(7! × 3!) = 120. Each key is fixed by choosing which 7 of the 10 positions are T, so the count also equals the number of ways to choose 7 of the 10 questions.
Quiz
1. How many distinguishable arrangements are there of the letters of CANADA?
2. Which expression counts the arrangements of n objects when a are alike and b are alike?
3. How many 4-digit codes (0000 to 9999) are possible if digits may repeat?
4. How many distinguishable arrangements are there of the letters of TORONTO?
5. How many different rows can be made with 3 identical green flags and 2 identical yellow flags?
6. When counting arrangements of CANADA, why do we divide 6! by 3!?
Big idea (A2.1, A2.3): with repetition allowed, multiply n by itself r times. With identical objects, count as if they were different (n!) and then divide by the number of ways to shuffle each group of identical objects. The A2.2 expectation itself is about distinct objects; this lesson extends it because identical-object arrangements are needed for grid routes (lesson 11) and connect directly to combinations (next lesson).
How to help: Use letter tiles from a word game or paper squares. Label identical letters, list arrangements, then erase the labels and watch the list shrink.
Common difficulties:
- Miscounting the repeated letters. Write a tally (e.g. MISSISSAUGA: S 4, I 2, A 2) before using the formula.
- Adding the factorials in the denominator instead of multiplying them.
- Using P(n, r) when repetition is allowed.
- Choosing only some letters from a word with repeats: no single formula works; split into cases.