5.2 Permutations with Restrictions

AHL 1.10 Extension

In this section you will learn

• a strategy for arrangements with conditions: deal with the special conditions first
• how to count arrangements where objects must be together or separated
• (Extension) arrangements with identical objects, and arrangements in a circle

The IB syllabus says that permutations with identical objects and circular arrangements are not required. They are included here, marked Extension, because they appear in many problems.

Strategy

Arrangements with conditions

1. Fill the restricted places first (for example the first letter, or the last digit).
2. Together: glue the objects into one block, arrange the blocks, then arrange inside the block.
3. Separated: either (total) \(-\) (together), or arrange the others first and put the separated objects into the gaps.
4. If the cases overlap or differ, split into cases and add.

Example 1 In how many ways can the letters of the word PLANET be arranged if

(a) the first letter is a vowel,

(b) L is next to A,

(c) L and A are separated?

Solution

PLANET has 6 different letters, so with no condition there are \(6! = 720\) arrangements.

(a) First letter: A or E (2 ways). Then the other 5 letters: \(5! = 120\). Total \(2 \times 120 = 240\).

(b) Glue L and A into one block. Now arrange 5 items (the block, P, N, E, T): \(5! = 120\). Inside the block: LA or AL, 2 ways. Total \(120 \times 2 = 240\).

(c) Separated = total \(-\) together \(= 720 - 240 = 480\).

Example 2 How many 4-digit even numbers greater than 3000 can be made from the digits \(0, 1, 2, 3, 4, 5\), without repetition?

Solution

The first digit must be 3, 4 or 5, and the last digit must be 0, 2 or 4. The digit 4 is in both lists, so split into cases.

Case 1: first digit 3 or 5 (2 ways). Last digit: 0, 2 or 4 (3 ways). Middle two digits from the 4 left: \(4 \times 3 = 12\). \(\;2 \times 3 \times 12 = 72\).

Case 2: first digit 4 (1 way). Last digit: 0 or 2 (2 ways). Middle: \(4 \times 3 = 12\). \(\;1 \times 2 \times 12 = 24\).

Total: \(72 + 24 = 96\).

Example 3 Four boys and two girls stand in a row. In how many ways can they stand if

(a) a boy is at each end,

(b) the two girls are not next to each other?

Solution

(a) Ends first: \(4 \times 3 = 12\) ways. The other 4 people in the middle: \(4! = 24\). Total \(12 \times 24 = 288\).

(b) Arrange the boys: \(4! = 24\). This makes 5 gaps (including both ends):

\[ \_\;B\;\_\;B\;\_\;B\;\_\;B\;\_ \]

Put the two girls into two different gaps: \({}^5\mathrm{P}_2 = 20\). Total \(24 \times 20 = 480\).

(Check: total \(6! = 720\); girls together \(5! \times 2 = 240\); \(720 - 240 = 480\) ✓.)

Extension — identical objects

Extension Arrangements with identical objects

If 3 of 4 letters are the same, such as A, A, A, D, many of the \(4! = 24\) arrangements look identical. Only \(\frac{4!}{3!} = 4\) are different: AAAD, AADA, ADAA, DAAA.

Rule. The number of different arrangements of \(n\) objects, of which \(p\) are alike of one kind, \(q\) alike of another kind, and so on, is

\[ \frac{n!}{p!\,q!\,\cdots} \]

Example A. The letters of BANANA: \(\dfrac{6!}{3!\,2!} = 60\) arrangements (3 A’s, 2 N’s).

Example B. The six letters of PEPPER are written on cards and arranged in a row.

• Number of arrangements: \(\dfrac{6!}{3!\,2!} = 60\).
• The two middle cards are both P: the other four cards (P, E, E, R) fill the other places in \(\dfrac{4!}{2!} = 12\) ways.
• The two E’s are next to each other: treat EE as one block; arrange P, P, P, EE, R: \(\dfrac{5!}{3!} = 20\) ways.

Extension — circular arrangements

Extension Arrangements in a circle

At a round table, only the positions relative to each other matter: if everyone moves one seat to the left, the arrangement is the same. So fix one person and arrange the others.

\[ \text{$n$ different objects in a circle: } (n - 1)! \text{ ways.} \]

If clockwise and anticlockwise count as the same (for example beads on a necklace, which can be turned over), divide by 2: \(\dfrac{(n - 1)!}{2}\).

If the seats are numbered, they are different places, so there are \(n!\) ways, just like a row.

Example C. 8 people sit at a round table: \(7! = 5040\) ways. If two particular people must sit together: glue them, giving 7 “items” in a circle: \(6! \times 2 = 1440\) ways.

Example D. 4 men and 4 women sit at a round table, alternating. Fix one man; the other men: \(3! = 6\) ways; the women fill the 4 gaps: \(4! = 24\) ways. Total \(144\).

Example E. 6 different beads on a necklace: \(\dfrac{5!}{2} = 60\) ways.

Common errors

✗ Wrong	✓ Right	Why
Filling the free places first	Fill restricted places first	Otherwise the choices for the restricted place change.
Gluing a block but not arranging inside it	Multiply by the arrangements inside	LA and AL are different.
Using 3 gaps for 4 boys	5 gaps (ends included)	The ends are gaps too.
Overlapping cases counted twice	Split into separate cases	e.g. digit 4 in Example 2.

Exercises

1 In how many ways can the letters of the word FRIEND be arranged if it must start with F?

Solution

F fixed; the other 5 letters: \(5! = 120\).

2 In how many ways can the letters of FRIEND be arranged if the vowels I and E are together?

Solution

Block (IE): 5 items, \(5! = 120\); inside the block 2 ways. \(240\).

3 In how many ways can the letters of FRIEND be arranged if the vowels are separated?

Solution

\(6! - 240 = 720 - 240 = 480\).

4 Five different maths books and three different science books are put on a shelf. In how many ways can this be done if all the maths books are together?

Solution

Maths block + 3 science books = 4 items: \(4! = 24\); inside the block \(5! = 120\). Total \(2880\).

5 How many 3-digit numbers less than 500 can be made from \(1, 2, 3, 4, 5, 6\) without repetition?

Solution

First digit 1–4: 4 ways; then \(5 \times 4 = 20\). Total \(80\).

6 Five boys and three girls stand in a row so that no two girls are next to each other. In how many ways can this be done?

Solution

Boys: \(5! = 120\), making 6 gaps. Girls into 3 different gaps: \({}^6\mathrm{P}_3 = 120\). Total \(14\,400\).

7 How many even 4-digit numbers can be made from \(1, 2, 3, 4, 5\) without repetition?

Solution

Last digit 2 or 4: 2 ways; first three: \({}^4\mathrm{P}_3 = 24\). Total \(48\).

8 Three friends and four strangers stand in a queue. In how many ways can they queue if the three friends stand together?

Solution

Block + 4 = 5 items: \(5! = 120\); inside the block \(3! = 6\). Total \(720\).

9 Extension How many different arrangements are there of the letters of COMMITTEE?

Solution

9 letters: M×2, T×2, E×2. \(\;\dfrac{9!}{2!\,2!\,2!} = \dfrac{362\,880}{8} = 45\,360\).

10 Extension Seven people sit at a round table. In how many ways can they sit if two particular people must not sit next to each other?

Solution

Total: \(6! = 720\). Together: \(5! \times 2 = 240\). Not together: \(720 - 240 = 480\).