Permutations: identical objects and circular arrangements – Combinatorics (Senior 4 Mathematics) | Ganzaa

Combinatorics

Lessons

Senior 4 · Mathematics

Combinatorics

5 lessons

Lesson 3 of 5

Permutations: identical objects and circular arrangements

25 min

How many ways to spell KIGALI?

Arrange the six letters of KIGALI in a row. If all six letters were different, there would be $6! = 720$ orders. But the word has two I's, and swapping them gives back the same string: KIGALI with the I's swapped is still KIGALI. Every string has been counted twice, so there are only $\frac{720}{2} = 360$ different strings. This lesson counts arrangements of all the objects: first when they are all different, then when some are identical, and finally when they sit around a circle, where turning the whole circle changes nothing.

Definition

Permutation: an arrangement of all $n$ objects of a set in a row (a definite order). The number of permutations of $n$ different objects is

P_{n} = n!

It is the arrangement count $A_n^n = \frac{n!}{0!} = n!$ : $n$ choices for the first place, $n - 1$ for the second, and so on down to 1.

Example: 5 students can stand in a queue in $5! = 120$ ways.

Worked example 1: together and apart

(a) In how many ways can 6 different books, 3 of them mathematics books, stand on a shelf if the 3 mathematics books must be together? (b) In how many ways can 5 people sit in a row if Mugisha and Keza must not sit side by side?

Solution

Tie the 3 mathematics books into one block. Now arrange 4 items (the block and 3 other books): $4! = 24$ ways. Inside the block the 3 books can be ordered in $3! = 6$ ways. Total $24 \times 6 = 144$ .
Count the complement. All rows: $5! = 120$ . Rows with the two together: treat them as a block, $4! \times 2! = 48$ . So $120 - 48 = 72$ rows keep them apart.

Permutations with identical objects

Suppose a word has $n$ letters, with one letter appearing $n_{1}$ times, another $n_{2}$ times, and so on. Give the copies of each repeated letter temporary labels (I₁, I₂) so that all $n$ letters are different: they have $n!$ orders. Removing the labels, each real string appears $n_1! \, n_2! \cdots$ times, once for every way of ordering the copies among themselves. Dividing out the overcount gives the rule.

Important

Permutations with repetition (identical objects). The number of different rows of $n$ objects, of which $n_{1}$ are alike of one kind, $n_{2}$ alike of a second kind, …, $n_{k}$ alike of a $k$ th kind ( $n_1 + n_2 + \dots + n_k = n$ ), is

\frac{n!}{n_1!\, n_2! \cdots n_k!} .

Worked example 2: words, flags and paths

(a) How many different strings can be made from all the letters of NYABUGOGO? (b) In how many ways can 3 identical red, 2 identical blue and 1 green flag be hung in a row on a pole? (c) A delivery rider in a grid of streets must go 5 blocks east and 3 blocks north. How many shortest routes are there?

Solution

NYABUGOGO has 9 letters, with G twice and O twice (N, Y, A, B, U once each): $\frac{9!}{2!\,2!} = \frac{362\,880}{4} = 90\,720$ .
$\frac{6!}{3!\,2!\,1!} = \frac{720}{12} = 60$ .
Every shortest route is a row of 8 moves, 5 of them E and 3 of them N, such as EENENEEN. So the count is $\frac{8!}{5!\,3!} = 56$ .

Circular permutations

At a round table there is no first seat. What matters is who sits next to whom. In the picture, the four seatings are the same circular arrangement, because each is obtained from the others by turning the table:

Each circular arrangement of $n$ people corresponds to exactly $n$ rows (cut the circle at any of the $n$ places). So the number of circular arrangements is $\frac{n!}{n} = (n - 1)!$ . Another way to see it: seat one person anywhere to fix the circle, then arrange the other $n - 1$ people in the $n - 1$ seats relative to that person.

Important

Circular permutations. The number of ways to arrange $n$ different objects around a circle, when only their positions relative to each other matter, is

(n - 1)! .

If, in addition, the circle can be turned over so that clockwise and anticlockwise orders are the same (beads on a bracelet, keys on a ring), the number is

\frac{(n - 1)!}{2}, \qquad n \ge 3 .

Worked example 3: a meeting and a bracelet

(a) In how many ways can 8 members of a cell committee sit at a round table? (b) In how many of these do the chairperson and the secretary sit side by side? (c) In how many ways can 7 different beads be threaded on a bracelet?

Solution

$(8 - 1)! = 7! = 5040$ .
Treat the pair as one block: 7 items around the table, $(7 - 1)! = 720$ ways, and the pair can sit in $2! = 2$ orders inside the block: $720 \times 2 = 1440$ .
The bracelet can be turned over, so $\frac{(7 - 1)!}{2} = \frac{720}{2} = 360$ .

Warning

Is the circle really free to turn? Use $(n - 1)!$ only when the seats are not distinguished. If the seats are numbered, or one seat is special (the head of the table, the seat by the door), every seat is a definite place and the count is $n!$ again. And divide by 2 only when a mirror image really is the same arrangement: for people at a table it is not, since each person's left and right neighbours change.

Tip

Three questions decide the formula: Are all the objects different? (if not, divide by the factorials of the repeats) Is it a row or a circle? (a circle: $(n - 1)!$ ) Can the circle be flipped? (if so, divide by 2).

The Real Mr. F: Permutations with Repetitions and Circular Permutations. Watch how repeated letters are divided out, and why a round table gives (n − 1)! arrangements.

✦

Practice

Try each one before opening the answers. They get harder as you go.

In how many ways can 7 different photos be hung in a row on a wall?
How many different strings can be made from all the letters of (a) RWANDA (b) MUHANGA (c) BANANA?
A team of 4 girls and 3 boys stand in a row for a photo. In how many ways can they stand if (a) the girls stand together, (b) girls and boys alternate?
In how many ways can 6 people sit around a round table? In how many of these do two named people sit next to each other?
A key ring holds 5 different keys. In how many distinct ways can they be arranged?
How many shortest routes are there on a street grid from a corner to the corner 4 blocks east and 4 blocks north?
Five married couples sit at a round table. In how many ways can they sit if every couple sits together?

Show answersHide answers

$7! = 5040$ .
(a) RWANDA: A twice, so $\frac{6!}{2!} = 360$ . (b) MUHANGA: A twice, $\frac{7!}{2!} = 2520$ . (c) BANANA: A three times, N twice, $\frac{6!}{3!\,2!} = 60$ .
(a) Block of girls with 3 boys: $4! \times 4! = 576$ . (b) The pattern must be G B G B G B G: $4! \times 3! = 144$ .
$5! = 120$ ; together: $4! \times 2 = 48$ .
$\frac{(5 - 1)!}{2} = 12$ .
$\frac{8!}{4!\,4!} = 70$ .
Treat each couple as a block: 5 blocks around the table, $4! = 24$ ways, and each couple has 2 orders: $24 \times 2^5 = 768$ .

Quick check

Key points

$n$ different objects in a row: $n!$ .
With identical objects: $\frac{n!}{n_1!\,n_2!\cdots n_k!}$ .
Around a circle: $(n - 1)!$ ; if the circle can be turned over: $\frac{(n - 1)!}{2}$ .
"Together": make a block and multiply by its inside orders; "apart": subtract "together" from the total.

Sources and credits

Written by Ganzaa: the explanations, the diagram, the worked examples, the practice items and the questions.
Video: Permutations with Repetitions & Circular Permutations, The Real Mr. F, embedded from YouTube.

1How many ways to spell KIGALI?

2Permutations with identical objects

3Circular permutations

How many ways to spell KIGALI?

Permutations with identical objects

Circular permutations