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 n!n1! n2!⋯nk!\frac{n!}{n_1!\,n_2!\cdots n_k!} to count arrangements of nn 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 3!=63! = 6 ways. What about the letters of TOO? If you pretend the two Os are different, O1\text{O}_1 and O2\text{O}_2, there are again 3!=63! = 6 arrangements. But on the page you cannot tell TO1O2\text{TO}_1\text{O}_2 from TO2O1\text{TO}_2\text{O}_1.

Six labelled arrangements collapse to three different words.
With the Os labelledThe word you see
TO1O2\text{TO}_1\text{O}_2 and TO2O1\text{TO}_2\text{O}_1TOO
O1TO2\text{O}_1\text{TO}_2 and O2TO1\text{O}_2\text{TO}_1OTO
O1O2T\text{O}_1\text{O}_2\text{T} and O2O1T\text{O}_2\text{O}_1\text{T}OOT

Each word appears 2!=22! = 2 times, once for each order of the Os. So there are 3!2!=3\frac{3!}{2!} = 3 different words.

Key idea

Arrangements with repeated objects

The number of different arrangements of nn objects, where n1n_1 are identical of one kind, n2n_2 are identical of another kind, and so on, is

n!n1! n2!⋯nk!\frac{n!}{n_1!\,n_2!\cdots n_k!}

Divide by the factorial of each repeat, because swapping identical objects does not make a new arrangement.

Interactive

Arrange BANANA

Label the As and Ns to see how many labelled arrangements collapse to each word. BANANA has three As and two Ns: 6!3! 2!=60\frac{6!}{3!\,2!} = 60 arrangements.

How many different arrangements are there of the letters of the word CANBERRA?

Worked example

Arranging the letters of TOOWOOMBA

  • Simple familiar

(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?

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. List each letter and how many times it appears.

  2. Divide n!n! by the factorial of each repeat.

  3. Deal with any restriction first, then divide by the repeats among the letters that are left.

Watch out for

  • Using 9!=362 8809! = 362\,880 without dividing by 4!4!.

  • Multiplying by 4!4! 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: 4!=244! = 24 ways, with no extra factor of 2!2!.

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.

8!5! 3!=8×7×63×2×1=56 routes\frac{8!}{5!\,3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56 \text{ routes}

Worked example

Shortest routes through a street grid

  • Complex familiar
  • Technology free

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?

4 steps

Try it yourself first, then check the working one step at a time.

Method

  1. Write a route as a string of E and N moves.

  2. Count the arrangements of that string.

  3. For a route through a point, multiply the counts for the two stages.

Watch out for

  • Adding the two stages, 3+103 + 10, instead of multiplying.

  • Using 8!8! without dividing by 5! 3!5!\,3!: 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 8!8! and by 3!3!:

13!8! 3!=25 740.\frac{13!}{8!\,3!} = 25\,740.

Dividing by (8+3)!(8 + 3)!, or by 8!8! 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 ×3\times 3, N ×2\times 2". 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 n!n!.

  • nn objects with repeats n1,n2,…n_1, n_2, \ldots: n!n1! n2!⋯\frac{n!}{n_1!\,n_2!\cdots}, 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.

Lesson 5 of 80% read

Save your progress with a free account