Restricted Permutations: HSC Mathematics Extension 1 Guide

Six students are lining up for a photo. Ari and Bo must not stand next to each other. There are 720 possible line-ups before applying that rule, but how many of those need to be removed?

Imagine treating Ari and Bo as one object that moves along the row. Would you count each arrangement of that object once or twice?

Twice. The pair could stand Ari-Bo or Bo-Ari. Those are different line-ups, even though the two students occupy the same positions.

This is the central idea behind restricted permutations: change how you count so that the restriction becomes manageable, without losing or double-counting possible arrangements.

01Start with the positions, not the formula

Imagine six different name cards and six numbered spaces on a desk.

To fill the first space, you have six choices. Once you’ve used one card, there are five choices for the second space, then four for the third, and so on.

The total number of arrangements is

\[ 6!=6\times5\times4\times3\times2\times1 \]

\[ =720 \]

The symbol \(!\) means factorial. For any positive integer \(n\), \(n!\) means multiplying all the positive integers from \(n\) down to \(1\). We also define \(0!=1\).

A permutation is an arrangement in which order matters. ABC and BAC count as different arrangements.

What if we only fill some of the spaces?

Suppose we have six different cards but only three spaces.

There are six choices for the first space, five for the second, and four for the third.

That gives \(6\times5\times4=120\) possible displays.

We use the permutation formula:

\[ {}^nP_r=\frac{n!}{(n-r)!} \]

Here:

• \(n\) is the number of different objects available.
• \(r\) is the number of objects being selected and arranged.
• \({}^nP_r\) is the number of ordered arrangements of \(r\) objects selected from \(n\), without repetition.

For our cards:

\[ {}^6P_3=\frac{6!}{3!}=120 \]

The factorial in the denominator cancels the choices we never needed to make.

This distinction is useful in the HSC: \(n!\) arranges all \(n\) different objects, while \({}^nP_r\) selects and arranges only \(r\) of them.

Both formulae assume the objects being selected are distinguishable and cannot be selected more than once.

02Turn adjacency into a single block

Return to Ari and Bo.

When two particular people must stand together, temporarily treat them as one larger object.

Instead of six separate students, we now have five objects to arrange:

• The Ari-Bo block.
• Four other students.

Those five objects have \(5!\) possible orders.

But there are two arrangements inside the block: Ari-Bo and Bo-Ari.

Therefore, the number of line-ups in which they stand together is

\[ 2!\times5!=240 \]

We want the opposite: line-ups in which they are separated.

\[ \begin{aligned} N&=6!-2(5!)\\ &=720-240\\ &=480 \end{aligned} \]

Here, \(N\) is the number of valid line-ups.

So 480 arrangements satisfy the restriction.

This is called complementary counting. We count everything, subtract what is forbidden, and keep what remains.

It’s often easier than trying to place the two students separately from the start.

One important detail: a block preserves adjacency, but it doesn’t automatically preserve a particular order. If the question said Ari must stand immediately to the left of Bo, only Ari-Bo would be allowed. There would be no factor of \(2!\).

03Separation: count the gaps or subtract the neighbours

Adjacency problems often use blocks. Separation problems have two useful methods.

The first is complementary counting, as in the photo problem.

The second is the gap method.

Suppose C, D, and E are already arranged in that order. There are four available gaps:

• Before C.
• Between C and D.
• Between D and E.
• After E.

If you want to insert two identical A tiles so they cannot touch, put them in two different gaps.

There are four gaps, and we need to choose two of them. The order in which we choose the gaps doesn’t matter.

This is a combination rather than a permutation.

The number of ways to choose \(r\) objects or positions from \(n\), without caring about selection order, is

\[ \binom nr=\frac{n!}{r!(n-r)!} \]

For two gaps chosen from four:

\[ \binom42=\frac{4!}{2!2!}=6 \]

Each choice gives a different arrangement of the two identical A tiles around the fixed C, D, E sequence.

The gap method works particularly well when several objects must be kept apart.

But be careful: if you insert different types of objects, placing one type can change the available gaps for another. Restrictions don’t always behave independently.

04Repeated objects change the factorial count

Consider four tiles labelled A, A, B, and C.

If we pretended the As were different, we would get \(4!=24\) arrangements.

But swapping the two A tiles doesn’t produce a new visible arrangement.

Every arrangement has been counted twice.

Therefore:

\[ \frac{4!}{2!}=12 \]

There are only 12 distinct arrangements.

More generally, if \(n\) objects contain groups of \(a\), \(b\), \(c\), and so on identical objects, the number of distinct arrangements is

\[ \frac{n!}{a!b!c!\cdots} \]

The repeated groups account for all \(n\) objects.

This adjustment is only for genuinely identical objects. Two different students wearing the same colour shirt are still distinguishable students.

05When several restrictions overlap

One restriction is usually straightforward. Two or three interacting restrictions are where exam questions become interesting.

Consider two pairs of identical tiles: AA and BB.

Suppose neither pair is allowed to touch.

A tempting approach is:

1. Count every arrangement.
2. Subtract the arrangements containing AA.
3. Subtract the arrangements containing BB.

But what happens to an arrangement containing both AA and BB?

It gets subtracted twice.

We need to add those arrangements back once.

For two forbidden conditions, the correct count is

\[ N=N_0-N_A-N_B+N_{AB} \]

where:

• \(N_0\) counts all arrangements.
• \(N_A\) counts arrangements breaking the first condition.
• \(N_B\) counts arrangements breaking the second condition.
• \(N_{AB}\) counts arrangements breaking both conditions.

This is the inclusion-exclusion principle.

It’s especially useful when repeated objects and adjacency restrictions appear together.

A quick decision guide

One more caution about symmetry: if swapping C and D always produces another permitted arrangement, exactly half the arrangements have C before D.

But if C is forbidden from the first position while D isn’t, the swap may break the rule. You cannot automatically divide by two.

The five questions below put these methods together. Try to decide how you would count each arrangement before expanding any factorials.

06Questions and solutions

Question 1

Six different cards, A, B, C, D, E, and F, are available.

Three cards are selected and arranged in three numbered positions. Card A must occupy the middle position.

How many different arrangements are possible?

Solution 1

There are 20 possible arrangements.

Card A is fixed in the middle, leaving two positions to fill from the other five cards.

Since order matters, we use permutations:

\[ \begin{aligned} {}^5P_2&=\frac{5!}{3!}\\ &=5\times4\\ &=20 \end{aligned} \]

A common mistake is to use \({}^6P_3\), which counts arrangements where A might appear elsewhere or not appear at all.

Fixing A first ensures every counted arrangement meets the condition.

Question 2

Seven different students, A, B, C, D, E, F, and G, line up in a straight row.

The following rules apply:

• A must stand immediately to the left of B.
• C must stand somewhere to the left of D.
• Neither C nor D may occupy either end of the row.

How many valid line-ups are possible?

Solution 2

There are 144 valid line-ups.

The key is that the number of available interior positions for C and D depends on where the AB pair stands.

Step 1: Treat AB as an ordered pair.

Since A must be immediately to the left of B, the pair can occupy one of six consecutive pairs of positions:

\((1,2)\), \((2,3)\), \((3,4)\), \((4,5)\), \((5,6)\), or \((6,7)\).

We don’t multiply by two for BA, because that order is forbidden.

Step 2: Count cases where AB touches an end.

There are two possibilities: AB occupies positions 1-2 or positions 6-7.

Of the five interior positions (2 through 6), one is occupied by A or B. Four interior positions remain available for C and D.

Since C must come before D, choosing any two of those four positions determines their order.

\[ \binom42=6 \]

The remaining students E, F, and G can be arranged in \(3!=6\) ways.

For the two possible end positions of AB:

\[ 2\times6\times6=72 \]

Step 3: Count cases where AB is entirely inside the row.

AB can occupy positions 2-3, 3-4, 4-5, or 5-6.

There are four possibilities.

Now AB occupies two interior positions, leaving only three interior positions for C and D.

\[ \binom32=3 \]

The remaining E, F, and G can again be arranged in six ways.

\[ 4\times3\times6=72 \]

Step 4: Add the cases.

\[ 72+72=144 \]

The tempting mistake is to count AB as one block and assume C and D always have the same number of interior positions available.

They don’t. The block sometimes uses an endpoint and sometimes doesn’t.

That’s why the cases must be separated.

Question 3

Seven letter tiles, A, A, B, B, C, D, and E, are arranged in a row.

The two As are identical, and the two Bs are identical.

The arrangement must satisfy all these conditions:

• The two As are not adjacent.
• The two Bs are not adjacent.
• C and D are adjacent, in either order.
• Neither C nor D is at an end of the row.

How many distinct arrangements are possible?

Solution 3

There are 120 distinct valid arrangements.

We’ll first satisfy the adjacency restrictions, then remove the arrangements where C or D is at an end.

Step 1: Treat C and D as one block.

Temporarily call this block X.

We now have six objects:

A, A, B, B, E, X.

Ignoring the separation restrictions, the number of distinct arrangements is

\[ \frac{6!}{2!2!}=180 \]

Step 2: Subtract arrangements with adjacent As or adjacent Bs.

If the As are adjacent, treat AA as a block.

The objects are AA, B, B, E, and X.

\[ \frac{5!}{2!}=60 \]

Similarly, 60 arrangements have adjacent Bs.

But arrangements containing both AA and BB have been subtracted twice.

Treating both repeated pairs as blocks gives four objects: AA, BB, E, and X.

\[ 4!=24 \]

By inclusion-exclusion, the number where neither identical pair touches is

\[ \begin{aligned} N&=180-60-60+24\\ &=84 \end{aligned} \]

Step 3: Remove arrangements where the CD block is at an end.

For a fixed end position of X, the remaining objects are A, A, B, B, and E.

First count all their arrangements:

\[ \frac{5!}{2!2!}=30 \]

Subtract arrangements with AA adjacent and BB adjacent, then restore the overlap:

\[ \begin{aligned} N_{\text{end}} &=30-12-12+6\\ &=12 \end{aligned} \]

Here, each 12 comes from arranging an identical-pair block with the other identical pair and E, while the 6 comes from arranging AA, BB, and E as three distinct objects.

There are two possible ends for X, giving

\[ 2\times12=24 \]

So the number of arrangements with X away from the ends is

\[ 84-24=60 \]

Step 4: Restore the internal order of C and D.

The block X can represent CD or DC.

\[ 60\times2=120 \]

Therefore, 120 distinct rows satisfy every condition.

The main traps are forgetting to restore arrangements that violate both repeated-pair restrictions, and forgetting that the CD block contains two different letters.

Notice that we applied the end restriction after counting arrangements with neither repeated pair adjacent. Otherwise, we could subtract arrangements that were already invalid for another reason.

Question 4

A four-digit locker code is made using four different digits selected from

\[ 0,1,2,3,4,5,6 \]

The code must satisfy these conditions:

• Both 1 and 2 must appear.
• At least one digit must be between 1 and 2.
• Exactly one of 3 and 4 must appear.
• The first digit cannot be 0.

How many valid codes are possible?

Solution 4

There are 68 valid codes.

The important distinction is whether 0 is selected. The first-position restriction affects those two groups differently.

Step 1: Count arrangements for a fixed choice of four digits, ignoring the zero restriction.

We must include 1, 2, and exactly one of 3 or 4.

The fourth digit is selected from 0, 5, or 6.

For any fixed selection of four distinct digits, there are

\[ 4!=24 \]

possible orders.

We must subtract arrangements where 1 and 2 are adjacent.

Treat 1 and 2 as a block. There are \(3!\) arrangements of the block and the other two digits, with two orders inside the block.

\[ 2(3!)=12 \]

Therefore, for any fixed set of four selected digits, the number with 1 and 2 separated is

\[ 24-12=12 \]

Step 2: Count codes that don’t contain 0.

Choose exactly one of 3 and 4: two options.

Choose the remaining digit from 5 and 6: two options.

Each selection gives 12 arrangements.

\[ 2\times2\times12=48 \]

None of these codes starts with 0, so all 48 are valid.

Step 3: Count codes that contain 0.

The selected digits are 0, 1, 2, and one of 3 or 4.

There are two choices for that final digit.

For each choice, we already know there are 12 arrangements with 1 and 2 separated.

Now remove those starting with 0.

If 0 occupies position 1, the only way to keep 1 and 2 apart in the three remaining positions is to place them in positions 2 and 4.

They can occur in either order, giving two invalid codes for each choice of the fourth digit.

So the valid codes containing 0 are

\[ 2(12-2)=20 \]

Step 4: Combine both cases.

\[ 48+20=68 \]

The tempting shortcut is to take the 12 separated arrangements involving 0 and multiply by \(\frac34\), because 0 seems to have four equally likely positions.

That doesn’t work here.

Once 1 and 2 are required to be separated, the positions are no longer symmetric. Only two of the 12 arrangements start with 0, not three.

Counting the invalid first-position cases directly avoids that mistake.

Question 5

Nine letter tiles are arranged in a straight row:

• Four identical A tiles.
• Three identical B tiles.
• One C tile.
• One D tile.

The arrangement must satisfy all three conditions:

1. No two A tiles are adjacent.
2. No two B tiles are adjacent.
3. C must appear to the left of D, and C and D must not be adjacent.

How many distinct arrangements are possible?

Solution 5

There are 79 distinct valid arrangements.

The crucial idea is that C and D can separate identical letters. The A and B tiles don’t necessarily have to alternate when C and D are removed.

We’ll use that observation to count every possible arrangement exactly once.

Step 1: Temporarily remove C and D.

We are left with seven tiles:

A, A, A, A, B, B, B.

Call any arrangement of these seven tiles a skeleton.

For example:

A A B A B B A

This skeleton has two pairs of identical neighbours: AA near the start and BB near the end.

Those pairs would be forbidden in the finished row.

But inserting C between the two As and D between the two Bs repairs both problems:

A C A B A B D B A

This completed arrangement satisfies all three conditions.

So we must not discard every skeleton that contains identical neighbours.

Step 2: Work out how many forbidden joins C and D can repair.

There are eight gaps around any seven-tile skeleton:

• One before the first tile.
• Six between consecutive tiles.
• One after the last tile.

C and D must occupy different gaps. Otherwise, they would be next to each other.

Since C must appear before D, once we choose two different gaps, C must occupy the earlier one and D the later one.

Each inserted tile can break at most one adjacency between identical A or B tiles.

Therefore:

• A skeleton with no identical neighbours is usable.
• A skeleton with one identical-neighbour join is usable.
• A skeleton with two identical-neighbour joins is usable.
• A skeleton with three or more such joins is impossible to repair using only C and D.

We only need to count the first three types.

Step 3: Count skeletons with zero identical-neighbour joins.

With four As and three Bs, there is only one fully alternating arrangement:

A B A B A B A

It contains no identical neighbours.

We can insert C and D into any two different gaps from the eight available.

\[ \binom82=28 \]

The earlier gap receives C, so every choice gives exactly one valid arrangement.

This contributes 28 arrangements.

Step 4: Count skeletons with exactly one identical-neighbour join.

A skeleton with one identical join has six runs.

A run is a consecutive group of identical letters. For example, AA is one A-run, while A B A contains two separate A-runs.

With six runs, the types must alternate in one of these forms:

A B A B A B

or

B A B A B A

Each form has three A-runs and three B-runs.

The three B tiles must occupy the three B-runs individually.

The four A tiles must occupy three nonempty A-runs. Exactly one A-run must contain two As.

There are three choices for which A-run is doubled.

So the number of skeletons is

\[ 2\times3=6 \]

Each skeleton has exactly one forbidden identical-neighbour join.

One of C or D must be inserted into the gap at that join. The other must occupy one of the seven remaining gaps.

Once the two gaps are chosen, their left-to-right order determines which receives C and which receives D.

Therefore, these skeletons contribute

\[ 6\times7=42 \]

valid arrangements.

Step 5: Count skeletons with exactly two identical-neighbour joins.

These skeletons have five runs.

There are two possible alternating run structures.

Case A: The skeleton starts and ends with A.

The runs have the pattern

A B A B A

There are three A-runs containing four As. One of those A-runs must have two As, giving three choices.

There are two B-runs containing three Bs. One B-run must have two Bs, giving two choices.

Therefore:

\[ 3\times2=6 \]

Case B: The skeleton starts and ends with B.

The runs have the pattern

B A B A B

There are three B-runs, so each must contain one B.

The four As must be split into two nonempty A-runs.

The possible run sizes are

\[ (1,3),\quad(2,2),\quad(3,1) \]

There are three possibilities.

Thus, the total number of skeletons with exactly two identical joins is

\[ 6+3=9 \]

Each of these skeletons has two forbidden joins.

C and D must occupy precisely those two gaps, with C in the earlier one.

There is only one valid insertion for each skeleton.

This contributes nine arrangements.

Step 6: Add the three categories.

Therefore:

\[ 28+42+9=79 \]

There are exactly 79 distinct arrangements.

The trap is assuming that deleting C and D must leave a perfectly alternating A/B pattern.

That seems reasonable because identical letters cannot touch in the finished arrangement. But deleting a separator can make two previously separated letters appear adjacent.

C and D aren’t just extra objects to arrange. They actively change which A/B arrangements are permitted.

The deeper method is to start from an unrestricted skeleton, identify which faults the inserted objects can repair, and count only skeletons that can become valid.

That idea extends beyond restricted permutations. In probability questions, the same counting methods give the number of favourable outcomes, which can then be divided by the total number of equally likely outcomes.

The next decision is therefore not which formula to memorise. It’s identifying exactly what counts as one outcome, which restrictions interact, and whether your counting method includes each valid outcome once.