Lesson 5 of 8 · 16 min
Arrangements with repeated objects
Count arrangements when some objects are identical, such as the letters of TOOWOOMBA or the moves of a shortest path through a street grid.
What you will be able to do
- Explain why identical objects reduce the number of different arrangements.
- Use to count arrangements of objects that include repeats.
- Count shortest paths on a grid as arrangements of repeated moves.
- Combine repeated objects with other restrictions.
The letters of CAT can be arranged in ways. What about the letters of TOO? If you pretend the two Os are different, and , there are again arrangements. But on the page you cannot tell from .
| With the Os labelled | The word you see |
|---|---|
| and | TOO |
| and | OTO |
| and | OOT |
Each word appears times, once for each order of the Os. So there are different words.
Key idea
Arrangements with repeated objects
The number of different arrangements of objects, where are identical of one kind, are identical of another kind, and so on, is
Divide by the factorial of each repeat, because swapping identical objects does not make a new arrangement.
Label the As and Ns to see how many labelled arrangements collapse to each word. BANANA has three As and two Ns: arrangements.
How many different arrangements are there of the letters of the word CANBERRA?
Worked example
Arranging the letters of TOOWOOMBA
(a) How many different arrangements are there of the letters of TOOWOOMBA?
(b) How many of these begin with T?
(c) In how many are all four Os together?
Step 1: Count the letters and the repeats
TOOWOOMBA has 9 letters: four Os, and T, W, M, B and A once each.
Step 2: Divide by the repeats
Swapping the four Os among themselves ( ways) does not change the word, so each word appears 24 times among the labelled arrangements.
Step 3: Fix the first letter
With T first, the other 8 letters (four Os, W, M, B and A) fill the remaining places: .
Step 4: Glue the Os together
Treat OOOO as one block. Now arrange 6 different units (T, W, M, B, A and the block): .
The Os are identical, so there is only one way to arrange them inside the block. There is no extra factor.
Try it yourself first, then check the working one step at a time.
Answer
(a) (b) 1680 (c) 720
Method
List each letter and how many times it appears.
Divide by the factorial of each repeat.
Deal with any restriction first, then divide by the repeats among the letters that are left.
Watch out for
Using without dividing by .
Multiplying by for the order inside the block of Os: identical objects can only be arranged one way.
Tip
Identical objects in a block
If identical objects must be together, glue them into a block as before, but they can only be arranged one way inside it. In NOOSA with the two Os together, arrange N, [OO], S and A: ways, with no extra factor of .
Paths on a grid. A courier in a city grid drives from the depot A to a customer B who is 5 blocks east and 3 blocks north, always heading east (E) or north (N). Every shortest route is a string of 5 Es and 3 Ns, such as EENENEEN. So the number of routes is the number of arrangements of EEEEENNN.
The highlighted route is EENENEEN. Every shortest route uses 5 Es and 3 Ns in some order.
There are 8 moves: 5 identical Es and 3 identical Ns.
Worked example
Shortest routes through a street grid
A courier drives from the depot A to a customer at B along the streets of the grid shown, always heading east or north.
(a) How many different shortest routes are there?
(b) How many of these pass through the intersection P?
Step 1: Describe a route as a string of moves
Every shortest route is 5 moves east (E) and 3 moves north (N) in some order, such as EENENEEN.
Any move west or south would make the route longer.
Step 2: Count the arrangements of EEEEENNN
Step 3: Split the route at P
A to P is 2 east and 1 north: routes. P to B is 3 east and 2 north: routes.
Step 4: Multiply
Each route to P can be followed by each route from P: .
The journey is two stages, so the multiplication principle applies.
Try it yourself first, then check the working one step at a time.
Answer
(a) 56 (b) 30
Method
Write a route as a string of E and N moves.
Count the arrangements of that string.
For a route through a point, multiply the counts for the two stages.
Watch out for
Adding the two stages, , instead of multiplying.
Using without dividing by : all the E moves are alike, and so are the N moves.
On the same 5 by 3 grid, how many shortest routes from A to B pass through the intersection 2 blocks east and 2 blocks north of A?
Common mistake
Divide once for each repeated letter
WOOLLOOMOOLOO has 13 letters: eight Os, three Ls, one W and one M. Divide by and by :
Dividing by , or by alone, gives the wrong count.
Exam tip
Write the letter counts
Before you write the fraction, list each repeated letter and how many times it appears, for example "A , N ". It earns method marks and stops you missing a repeat.
Summary
Swapping identical objects does not create a new arrangement, so the count is smaller than .
objects with repeats : , dividing by the factorial of each repeat.
Shortest grid routes are arrangements of repeated moves, such as 5 Es and 3 Ns.
Routes through a point are two stages, so multiply the two counts.
Identical objects glued into a block have only one internal arrangement.
Finished the lesson?
Try the 2 quick checks above and the lesson completes itself, or mark it complete now.