Arrangements with Repeated Objects | HSC Maths Extension 1

Three tiles sit on a desk: A, A, and B. How many different ways can you arrange them in a row?

If you temporarily label the A tiles as \(A_1\) and \(A_2\), there are \(3!=6\) possible arrangements. But look at the actual rows you can make:

• AAB
• ABA
• BAA

There are only three. Swapping the two A tiles doesn’t create a new arrangement because they’re identical.

This is the problem you need to solve whenever a permutation question contains repeated objects: how do you count genuinely different arrangements without counting identical ones multiple times?

01Why ordinary factorials overcount

Suppose you have six objects to arrange in a line. If every object is different, there are

\[ 6! \]

possible arrangements.

But what happens if three objects are identical?

Imagine temporarily giving them labels: \(A_1\), \(A_2\), and \(A_3\). The factorial \(6!\) counts arrangements in which these labels can occupy different positions.

However, swapping \(A_1\), \(A_2\), and \(A_3\) doesn’t change the actual arrangement. Each visible arrangement has been counted \(3!\) times.

If another two objects are identical, swapping those objects creates another \(2!\) duplicate arrangements.

Therefore, we need to divide by both sources of overcounting.

The general formula for arranging \(n\) objects in a line, where:

• \(a\) objects are identical,
• \(b\) objects are identical,
• \(c\) objects are identical,

and so on, is:

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

Here, \(a+b+c+\cdots=n\).

The numerator counts all arrangements as though every object were different. The denominator removes the repeated arrangements caused by swapping identical objects.

02What changes when there are restrictions?

The repeated-object formula handles arrangements without restrictions. HSC questions often add another condition.

For example:

• Two identical letters must be together.
• Two identical letters cannot be adjacent.
• A particular letter must occupy an end position.
• The first and last objects must be different.

The key is to decide what to count first. Two particularly useful techniques are the block method and the gap method.

When objects must stay together: the block method

Suppose two identical letters must be adjacent.

Instead of treating them as separate objects, combine them into a single block.

Consider BALLOON. It contains two L’s and two O’s.

Suppose the two L’s must be together.

Treat LL as one object:

\[ [LL], B, A, O, O, N \]

You now have six objects to arrange, with the two O’s still identical.

Therefore:

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

\[ \boxed{N=360} \]

The important detail is that the LL block has only one internal arrangement. There is no need to multiply by \(2!\).

If the block contained two different letters, such as AB, its internal arrangements AB and BA would be different. You would need to account for both if both were permitted.

When objects must stay apart: the gap method

Now suppose two identical objects must not be adjacent.

Instead of placing them first, arrange all the other objects.

These objects create gaps between them, including a gap at each end.

For example, if five objects are arranged in a row:

\[ \square \quad X \quad \square \quad X \quad \square \quad X \quad \square \quad X \quad \square \quad X \quad \square \]

There are six gaps.

To prevent two identical objects from being adjacent, place at most one in each gap.

If there are \(m\) objects in the original row, the number of available gaps is:

\[ m+1 \]

If you need to place \(k\) identical objects without any two being adjacent, you choose \(k\) different gaps:

\[ \boxed{\binom{m+1}{k}} \]

You then multiply this by the number of distinct arrangements of the original objects.

This method works particularly well when the objects you’re separating are identical.

03A useful distinction: end positions and fixed positions

The gap method includes both end gaps. This matters when a question adds conditions about the first or last object.

Suppose the repeated objects you’re inserting are A’s.

• If you select both outer gaps, the arrangement begins and ends with A.
• If you select exactly one outer gap, exactly one end contains A.
• If you select neither outer gap, both ends are occupied by objects from the original arrangement.

You can use these cases to enforce conditions about the ends of a row.

For restrictions involving odd positions, even positions, or specific numbered positions, a different approach is often cleaner: choose the positions first, then arrange the remaining objects.

Here is a quick guide:

The following questions put these methods together. Pay attention to what each restriction actually changes.

04Questions and solutions

Question 1

How many distinct linear arrangements can be made using all the letters in LEVEL?

Solution 1

There are 30 distinct arrangements.

LEVEL contains five letters:

• L appears twice.
• E appears twice.
• V appears once.

We begin with \(5!\) arrangements and divide by the factorial of each repeated group.

\[ \begin{aligned} N&=\frac{5!}{2!2!}\\ &=\frac{120}{4}\\ &=\boxed{30} \end{aligned} \]

The two L’s and two E’s are indistinguishable, so swapping either pair does not create a new arrangement.

Question 2

How many distinct arrangements of the letters in COMMITTEE have the following properties?

• The two E’s must be adjacent.
• The two M’s must not be adjacent.

Solution 2

There are 7,560 valid arrangements.

This is a block-method question involving complementary counting.

The important point is that we must count arrangements where the E’s are together, then subtract the arrangements where the M’s are also together.

Step 1: Combine the two E’s into one block.

COMMITTEE contains:

• One C.
• One O.
• Two M’s.
• One I.
• Two T’s.
• Two E’s.

Treat EE as a single object.

We now arrange:

\[ [EE], C, O, I, M, M, T, T \]

There are eight objects, with two identical M’s and two identical T’s.

The number of arrangements is:

\[ \begin{aligned} N_{\text{EE together}} &=\frac{8!}{2!2!}\\ &=\boxed{10\,080} \end{aligned} \]

Step 2: Subtract arrangements where the M’s are also together.

Treat MM as another block.

The objects are now:

\[ [EE], [MM], C, O, I, T, T \]

There are seven objects, with two identical T’s.

Therefore:

\[ \begin{aligned} N_{\text{both pairs together}} &=\frac{7!}{2!}\\ &=\boxed{2\,520} \end{aligned} \]

Step 3: Subtract the unwanted arrangements.

\[ \begin{aligned} N&=10\,080-2\,520\\ &=\boxed{7\,560} \end{aligned} \]

The subtraction works because every arrangement with the M’s together is included in our original count, provided the E’s are also together.

A tempting mistake is to subtract every arrangement where the M’s are together, regardless of the E positions. That would remove arrangements that were never included in the original count.

Question 3

A collection contains four identical red counters, three identical blue counters, and two identical green counters.

The nine counters are arranged in a straight line.

How many distinct arrangements are possible if:

• No two red counters are adjacent.
• The first and last counters must be different colours?

Solution 3

There are 86 valid arrangements.

We will use the gap method, but we need to pay particular attention to the two end gaps.

Step 1: Arrange the non-red counters first.

We have three blue counters and two green counters.

The number of distinct base arrangements is:

\[ \begin{aligned} N_{\text{base}} &=\frac{5!}{3!2!}\\ &=\boxed{10} \end{aligned} \]

Step 2: Identify the gaps.

Each base arrangement contains five counters, creating six gaps.

We must place the four red counters in four different gaps.

Without the endpoint restriction, the number of ways would be:

\[ \binom{6}{4}=15 \]

However, not all 15 choices satisfy the endpoint condition.

Step 3: Consider the two outer gaps.

There are three possibilities.

Case A: Both outer gaps are selected.

The first and last counters would both be red.

This violates the condition that the end colours must be different.

Therefore, none of these arrangements are allowed.

Case B: Exactly one outer gap is selected.

The row begins or ends with red, but not both.

The other end must be occupied by a blue or green counter.

Therefore, the endpoint condition is automatically satisfied.

There are two choices for which outer gap is selected.

We then choose three of the four internal gaps:

\[ 2\binom{4}{3}=2\times4=8 \]

So every base arrangement produces eight valid choices in this case.

Case C: Neither outer gap is selected.

All four red counters must occupy the four internal gaps.

There is exactly one way to do this.

The first and last counters are now the first and last counters of the original blue-green arrangement.

We need these colours to be different.

Step 4: Count the base arrangements with different endpoint colours.

There are ten base arrangements.

Count the arrangements with matching endpoints first.

If both ends are blue, the remaining counters are one blue and two green:

\[ \frac{3!}{2!}=3 \]

If both ends are green, the remaining counters are three blue:

\[ \frac{3!}{3!}=1 \]

Therefore:

\[ N_{\text{same ends}}=3+1=4 \]

The number with different endpoints is:

\[ 10-4=6 \]

Step 5: Combine the cases.

For each of the ten base arrangements, Case B contributes eight valid arrangements.

Case C contributes one additional arrangement for each of the six base arrangements with different endpoints.

Thus:

\[ \begin{aligned} N&=10\times8+6\times1\\ &=80+6\\ &=\boxed{86} \end{aligned} \]

The subtlety is that the end gaps are not ordinary internal gaps. Selecting both forces the same colour at both ends, while selecting exactly one automatically gives different endpoint colours.

Question 4

Consider the word MISSISSIPPI.

How many distinct arrangements of its letters satisfy both conditions?

• All four I’s must occupy positions of the same parity. In other words, they must all be in odd-numbered positions or all be in even-numbered positions.
• The first and last letters must be different.

Number the positions from left to right, starting at position 1.

Solution 4

There are 1,260 valid arrangements.

This question is best approached by choosing the positions of the I’s first.

MISSISSIPPI contains:

• Four I’s.
• Four S’s.
• Two P’s.
• One M.

Once the four I positions have been selected, the remaining seven letters can be arranged in:

\[ \frac{7!}{4!2!}=105 \]

ways before applying the endpoint condition.

We consider two separate cases.

Case A: All four I’s occupy even positions.

There are five even positions:

\[ 2,4,6,8,10 \]

We must choose four of them:

\[ \binom{5}{4}=5 \]

The first and last positions are both odd, so neither can contain an I.

The remaining letters are M, S, S, S, S, P, P.

There are 105 arrangements without the endpoint restriction.

Now subtract arrangements where the first and last letters are identical.

Both ends cannot be M because there is only one M.

If both ends are S, the remaining five letters contain two S’s, two P’s, and one M:

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

If both ends are P, the remaining letters contain four S’s and one M:

\[ \frac{5!}{4!}=5 \]

Therefore, the number of arrangements with different endpoints is:

\[ 105-30-5=70 \]

There are five choices of I positions, giving:

\[ N_{\text{even}}=5\times70=\boxed{350} \]

Case B: All four I’s occupy odd positions.

There are six odd positions:

\[ 1,3,5,7,9,11 \]

We choose four of these six positions:

\[ \binom{6}{4}=15 \]

However, we cannot simply multiply 15 by 105.

The first and last positions are also odd. If both contain I’s, the endpoint condition is automatically broken.

We therefore divide this case into three possibilities.

Possibility 1: Both end positions contain I.

We have already used two of the four I’s.

We must choose the remaining two positions from the four internal odd positions:

\[ \binom{4}{2}=6 \]

All six choices are invalid because the first and last letters are both I.

Possibility 2: Exactly one end position contains I.

There are two choices for which endpoint contains I.

We then choose three of the four internal odd positions for the remaining I’s.

\[ 2\binom{4}{3}=8 \]

In every one of these eight selections, one endpoint is I and the other is a non-I letter.

The endpoints must therefore be different.

Each selection allows 105 arrangements of the remaining letters:

\[ N_1=8\times105=840 \]

Possibility 3: Neither end position contains I.

All four I’s must occupy the four internal odd positions.

There is only one possible selection.

Both endpoints must now contain letters from M, S, S, S, S, P, P.

As calculated in Case A, there are 70 arrangements with different endpoints:

\[ N_2=1\times70=70 \]

Therefore, the odd-position case contributes:

\[ N_{\text{odd}}=840+70=910 \]

Step 3: Combine the two parity cases.

The cases are mutually exclusive, so we add them:

\[ \begin{aligned} N&=N_{\text{even}}+N_{\text{odd}}\\ &=350+910\\ &=\boxed{1\,260} \end{aligned} \]

The main trap is treating all 15 selections of odd positions as equivalent. Some force identical letters at both ends, while others don’t. The position of the I’s changes which endpoint arrangements are possible.

Question 5

A collection contains four identical A counters, three identical B counters, and two identical C counters.

All nine counters are arranged in a straight line.

How many distinct arrangements satisfy all three conditions?

• No two A counters are adjacent.
• No two C counters are adjacent.
• The first and last counters must be different colours.

Solution 5

There are 78 valid arrangements.

This question combines the gap method, repeated-object arrangements, and endpoint restrictions.

The important detail is that inserting an A can separate two C’s that were originally adjacent. We need to account for that rather than simply excluding every base arrangement containing adjacent C’s.

Step 1: Arrange the B’s and C’s first.

There are three identical B counters and two identical C counters.

The number of distinct base arrangements is:

\[ \begin{aligned} N_{\text{base}} &=\frac{5!}{3!2!}\\ &=\boxed{10} \end{aligned} \]

Every base arrangement has six gaps:

• One at the beginning.
• Four between consecutive counters.
• One at the end.

We need to place four A counters into four different gaps.

This guarantees that no two A counters are adjacent.

Step 2: Understand the restriction on the C counters.

There are two possibilities.

If the C counters are not adjacent in the original B-C arrangement, at least one B lies between them.

They cannot become adjacent when we insert A’s.

If the C counters are adjacent in the original arrangement, however, we must insert an A into the gap between them.

This separates the C counters.

Step 3: Classify the ten base arrangements.

First, count the arrangements in which the C’s are adjacent.

Treat CC as one block. We have:

\[ [CC],B,B,B \]

The block can occupy four different positions:

\[ N_{\text{adjacent C}}=4 \]

The four arrangements are:

• CCBBB
• BCCBB
• BBCCB
• BBBCC

Two have different endpoint colours, and two have matching endpoint colours.

Now consider the remaining six arrangements, where the C’s are not adjacent.

We can determine their endpoint distribution by counting matching endpoints across all ten base arrangements.

If both ends are B, the number of arrangements is:

\[ \frac{3!}{1!2!}=3 \]

If both ends are C, there is only one arrangement.

Therefore, four of the ten base arrangements have matching endpoints, and six have different endpoints.

Of the four adjacent-C arrangements, two have matching endpoints and two have different endpoints.

The remaining six arrangements must therefore contain:

• Two with matching endpoints.
• Four with different endpoints.

We can summarise this classification:

Step 4: Count valid A placements when the C’s are adjacent.

The gap between the C’s must be selected.

We also need to consider the two outer gaps.

If both outer gaps are selected, the arrangement begins and ends with A. This is invalid.

There are two remaining possibilities.

Exactly one outer gap is selected.

We have two choices for the outer gap.

The gap between the C’s is already selected, so we need two more of the remaining three internal gaps.

The number of choices is:

\[ 2\binom{3}{2}=6 \]

These six arrangements all have different endpoint colours: one end is A, and the other is B or C.

Neither outer gap is selected.

All four internal gaps must be selected.

There is exactly one such choice.

The endpoints are now the original endpoints of the base arrangement.

This is valid only when those endpoints have different colours.

Therefore:

• A base arrangement with matching endpoints gives 6 valid placements.
• A base arrangement with different endpoints gives 7 valid placements.

There are two of each type, so the adjacent-C arrangements contribute:

\[ \begin{aligned} N_{\text{adjacent C}} &=2(6)+2(7)\\ &=\boxed{26} \end{aligned} \]

Step 5: Count valid A placements when the C’s are not adjacent.

In this case, we don’t need to select any particular internal gap to separate the C’s. There is already at least one B between them.

Again, selecting both outer gaps would make the endpoints both A, so that case is excluded.

Exactly one outer gap is selected.

There are two choices for the outer gap.

We then choose three of the four internal gaps:

\[ 2\binom{4}{3}=8 \]

All eight arrangements have different endpoint colours.

Neither outer gap is selected.

All four internal gaps must be selected.

There is one possible choice.

It is valid only when the original base arrangement has different endpoint colours.

Therefore:

• A base arrangement with matching endpoints gives 8 valid placements.
• A base arrangement with different endpoints gives 9 valid placements.

There are two base arrangements with matching endpoints and four with different endpoints.

Their contribution is:

\[ \begin{aligned} N_{\text{non-adjacent C}} &=2(8)+4(9)\\ &=16+36\\ &=\boxed{52} \end{aligned} \]

Step 6: Combine both cases.

The two cases cover every possible base arrangement, so:

\[ \begin{aligned} N&=N_{\text{adjacent C}}+N_{\text{non-adjacent C}}\\ &=26+52\\ &=\boxed{78} \end{aligned} \]

There are 78 distinct arrangements satisfying all three conditions.

The biggest trap is assuming that adjacent C’s in the base arrangement must remain adjacent in the final row. They don’t. An inserted A can separate them, and that changes which gap selections are valid.

This is why it pays to remove one type of repeated object at a time and examine what the remaining objects actually allow.

05Where to use these techniques next

Repeated-object arrangements are also useful in probability questions.

If every distinct arrangement is equally likely, you can calculate a probability by dividing the number of valid arrangements by the total number of distinct arrangements:

\[ P(\text{event})= \frac{\text{valid arrangements}} {\text{total arrangements}} \]

The important thing is to use the repeated-object formula in both counts and apply any restrictions consistently.

When you meet a new arrangement problem, make your first decision about the structure: are objects unrestricted, required to stay together, required to stay apart, or restricted to particular positions? Choosing that method before calculating is often the difference between a clean solution and a page of unnecessary counting.