Counting Principles and Factorial Arrangements | HSC Maths Ext 1

Suppose a lock needs a three-letter code made from A, B, C, and D, with no letter repeated. How many different codes are possible?

Before calculating, predict whether the answer is closer to 10 or 30.

A tempting calculation is \(4+3+2=9\), because there are four choices for the first letter, three for the second, and two for the third. But that adds the choices available at different stages. It doesn’t count the complete codes.

The trick is to organise the possibilities so that every outcome is counted exactly once. This is the foundation of counting problems in HSC Mathematics Extension 1.

01Listing outcomes systematically

Before reaching for a formula, try a smaller version of the problem.

Suppose you can use A, B, and C to make a two-letter code, without repeating a letter.

You could list the possibilities randomly, but it’s easy to miss one. Instead, fix the first letter and list every possible second letter.

There are six possible codes:

\[ AB,\ AC,\ BA,\ BC,\ CA,\ CB \]

Notice that AB and BA are different outcomes. The order of the letters matters because the first position and second position have different roles.

This is an important decision in counting: does changing the order create a different outcome?

Systematic listing is useful when there are relatively few possibilities. It helps you understand the structure of a problem and check that nothing has been missed.

However, listing every possibility quickly becomes impractical. Imagine trying to write out every three-letter code using four different letters.

We need a faster method.

02The fundamental counting principle

The fundamental counting principle gives us a way to count outcomes without listing them individually.

Suppose a task involves several consecutive decisions:

• The first decision has \(a\) possible choices.
• For each first choice, the second decision has \(b\) possible choices.
• For each combination of the first two choices, the third decision has \(c\) possible choices.

The total number of outcomes is:

\[ \boxed{a\times b\times c} \]

In other words, multiply the number of choices at each stage.

Return to the three-letter code using A, B, C, and D, with no repetition.

First position: Four letters are available.

Second position: Three letters remain.

Third position: Two letters remain.

Therefore,

\[ 4\times3\times2=24 \]

There are 24 possible codes.

The important idea is that every choice at one stage can be combined with every available choice at the next stage.

When should you multiply, and when should you add?

This distinction causes plenty of unnecessary mistakes.

• Multiply when a complete outcome requires several consecutive choices.
• Add when you are counting separate, non-overlapping cases that can each produce a valid outcome.

For example, suppose a student can choose either one of three science electives or one of two mathematics electives. If the student chooses exactly one elective, there are:

\[ 3+2=5 \]

possible choices.

If the student instead chooses one science elective AND one mathematics elective, there are:

\[ 3\times2=6 \]

possible combinations.

A useful habit is to identify exactly what makes one complete outcome before choosing your operation.

One further warning: the number of choices at each stage must be appropriate for that stage. If different earlier choices lead to different numbers of later choices, split the problem into cases and add their totals rather than blindly multiplying.

03Factorial notation and linear arrangements

Now consider a different problem.

Five different students need to stand in a line for a photograph. How many possible orders are there?

There are five choices for the first position.

Once the first student is placed, four students remain for the second position. Then three remain, followed by two, and finally one.

Using the fundamental counting principle:

\[ 5\times4\times3\times2\times1=120 \]

Writing this product every time becomes tedious, so mathematicians use factorial notation.

The factorial of a positive integer \(n\), written \(n!\), means the product of all positive integers from \(n\) down to 1.

\[ n!=n(n-1)(n-2)\cdots2\times1 \]

For example:

\[ \begin{aligned} 3!&=3\times2\times1=6\\ 4!&=4\times3\times2\times1=24\\ 5!&=5\times4\times3\times2\times1=120 \end{aligned} \]

There is also one special definition:

\[ \boxed{0!=1} \]

This makes factorial formulas work consistently. There is exactly one way to arrange zero objects: leave the arrangement empty.

Arranging all objects in a line

If you have \(n\) distinct objects and want to arrange all of them in a row, the number of arrangements is:

\[ \boxed{n!} \]

This is called a linear permutation.

Arranging only some of the objects

What if you have eight students but only need to fill three positions?

You do not need to arrange all eight.

The number of arrangements is:

\[ n(n-1)(n-2)\cdots(n-r+1) \]

where:

• \(n\) is the total number of distinct objects available.
• \(r\) is the number of positions being filled.

Using factorial notation, this becomes:

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

This is the permutation formula.

The key is that each position is different. Filling the first position with Alice and the second with Ben is a different outcome from putting Ben first and Alice second.

04Circular arrangements

A new complication appears when objects are arranged around a circle.

Suppose six students sit around a round table. How many different seating arrangements are possible?

You might initially calculate:

\[ 6!=720 \]

But this counts some arrangements multiple times.

Imagine everyone rotates one seat clockwise. Nobody has changed their relative position to anyone else. They are still sitting in exactly the same circular arrangement.

For example, these two descriptions represent the same seating:

• A, B, C, D, E, F
• B, C, D, E, F, A

The starting point has changed, but the seating has not.

For a linear arrangement, changing the starting position changes the arrangement. For a circular arrangement, it doesn’t.

The circular permutation formula

There is a simple way to avoid counting rotations repeatedly.

Fix one person in a particular seat. This removes the rotational duplication.

You can then arrange the remaining \(n-1\) people in the other seats.

Therefore, the number of distinct circular arrangements of \(n\) different people is:

\[ \boxed{(n-1)!} \]

For six students:

\[ (6-1)!=5!=120 \]

There are 120 distinct circular arrangements.

Important: For standard round-table seating problems, rotations are considered identical, but reflections are considered different.

For example, if B sits to A’s right in one arrangement, having B sit to A’s left in the reflected arrangement creates a different seating.

You should only divide by another factor of two if the question explicitly says that mirror-image arrangements are considered identical, as in certain necklace problems.

05Handling restrictions in arrangement problems

HSC questions rarely stop at asking you to arrange objects freely. They often introduce conditions that change which arrangements are allowed.

Three useful strategies are worth remembering.

The second strategy is called the complement method.

It is particularly useful when counting arrangements where two objects must not be adjacent.

For example, counting every possible way that two students can be separated might be awkward. But counting all arrangements and removing the arrangements where they stand together is often much easier.

There is another important issue when several conditions are involved: different restrictions may overlap.

If you count one condition and then another, an arrangement satisfying both conditions might be counted twice. You need to account for those overlaps.

The following questions build on these ideas.

06Questions and solutions

Question 1

A four-digit code is created using the digits 1, 2, 3, 4, and 5.

Each digit can be used at most once.

How many different four-digit codes can be formed?

Solution 1

There are 120 possible four-digit codes.

We use the fundamental counting principle because the code is formed by making four consecutive choices.

First position: Five choices.

Second position: Four choices remain.

Third position: Three choices remain.

Fourth position: Two choices remain.

Multiplying:

\[ \begin{aligned} N&=5\times4\times3\times2\\ &=120 \end{aligned} \]

Equivalently:

\[ N=\frac{5!}{(5-4)!}=120 \]

The order matters because changing the position of a digit creates a different code.

For example, 1234 and 4321 are two separate outcomes.

Question 2

Seven different students, including Alice and Ben, must stand in a straight line for a photograph.

Alice and Ben must not stand next to each other.

How many different line-ups are possible?

Solution 2

There are 3,600 valid line-ups.

The easiest method is to use the complement method: count all possible line-ups, then subtract the arrangements where Alice and Ben are together.

Step 1: Count all possible line-ups.

There are seven distinct students, so:

\[ N_{\text{total}}=7!=5040 \]

Step 2: Count the arrangements where Alice and Ben stand together.

Treat Alice and Ben as one block.

We now have six units to arrange:

• The Alice-Ben block.
• Five other students.

These six units can be arranged in:

\[ 6!=720 \]

ways.

However, Alice and Ben can swap positions within their block.

There are two internal arrangements, so:

\[ N_{\text{together}}=6!\times2 \]

\[ =720\times2=1440 \]

Step 3: Subtract the unwanted arrangements.

\[ \begin{aligned} N_{\text{separate}} &=N_{\text{total}}-N_{\text{together}}\\ &=5040-1440\\ &=\boxed{3600} \end{aligned} \]

There are 3,600 valid line-ups.

A common mistake is to count the arrangements where Alice and Ben are together and assume that this is the answer because the question mentions their relationship.

Always check whether the question asks for objects to be together or separated. These are opposite conditions, and the complement method connects them.

Question 3

Eight different people sit around a round table.

Two particular people, A and B, must sit directly opposite each other.

How many distinct seating arrangements are possible?

Rotations are considered identical, but reflections are different.

Solution 3

There are 720 distinct seating arrangements.

The important idea is to remove rotational duplication before counting the remaining positions.

Step 1: Fix person A in one particular seat.

Because rotating everyone around the table does not create a new arrangement, we can choose A’s seat as our reference position.

This leaves seven seats to fill.

Step 2: Position person B.

Since there are eight equally spaced seats, exactly one seat is directly opposite A.

Therefore, B has only one possible position.

Step 3: Arrange the remaining six people.

The other six people can occupy the remaining six seats in:

\[ 6!=720 \]

ways.

Therefore:

\[ \boxed{N=6!=720} \]

There are 720 distinct seating arrangements.

Notice that we did not multiply by eight to account for A’s possible starting positions. Doing so would count rotations as different arrangements.

We also do not divide by two for reflections. The question explicitly treats mirror-image seatings as different.

This is a useful distinction: circular arrangements remove rotational duplication, not automatically reflection duplication.

Question 4

Six different books are arranged on a shelf.

The books are labelled:

• \(M_1,M_2,M_3\): three different Mathematics books.
• \(P_1,P_2\): two different Physics books.
• \(C\): one Chemistry book.

The three Mathematics books must be together, but the two Physics books must not be next to each other.

How many different arrangements are possible?

Solution 4

There are 72 valid arrangements.

This question combines two restrictions, so we need to handle them in the correct order.

First, group the Mathematics books together. Then remove the arrangements where the Physics books are adjacent.

Step 1: Treat the three Mathematics books as one block.

The three books must remain together, so temporarily represent them as a single unit.

Our four units are now:

• The Mathematics block.
• Physics book \(P_1\).
• Physics book \(P_2\).
• Chemistry book \(C\).

Step 2: Count all arrangements of these four units.

There are:

\[ 4!=24 \]

possible arrangements.

Step 3: Subtract arrangements where the Physics books are together.

Treat \(P_1\) and \(P_2\) as another block.

We now have three units:

• Mathematics block.
• Physics block.
• Chemistry book.

The three units can be arranged in:

\[ 3!=6 \]

ways.

The Physics books can also swap positions inside their block, giving:

\[ N_{\text{Physics together}}=3!\times2=12 \]

Step 4: Calculate the valid arrangements of the four units.

\[ \begin{aligned} N_{\text{valid}} &=4!-2(3!)\\ &=24-12\\ &=12 \end{aligned} \]

Step 5: Arrange the Mathematics books inside their block.

The three different Mathematics books can be arranged in:

\[ 3!=6 \]

ways.

Therefore:

\[ \begin{aligned} N&=12\times3!\\ &=12\times6\\ &=\boxed{72} \end{aligned} \]

There are 72 valid arrangements.

The key detail is that the Mathematics block can be rearranged internally, even though it must remain together.

Also notice that we only subtract the Physics-adjacent arrangements after forming the Mathematics block. This ensures that both restrictions are satisfied simultaneously.

Question 5

Seven different people, A, B, C, D, E, F, and G, sit around a round table.

Rotations are considered identical, but reflections are different.

Exactly one of the following three pairs must sit in neighbouring seats:

• A and B.
• B and C.
• C and A.

In other words, exactly one of the pairs AB, BC, and CA must be adjacent.

How many distinct seating arrangements are possible?

Solution 5

There are 432 distinct seating arrangements.

This problem is harder because the three adjacency conditions are not independent.

For example, if A sits next to B and B sits next to C, we cannot automatically assume that A and C are separated. Their positions must be checked as well.

We need to count the possible relative positions of A, B, and C carefully.

Step 1: Fix A in one seat.

Since rotations are considered identical, fixing A removes rotational duplication.

Number the remaining six seats clockwise from A:

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

Seat 1 and seat 6 are the two seats next to A.

Step 2: Count all possible placements of B and C.

There are six available seats for B.

Once B is placed, five seats remain for C.

Therefore:

\[ N_{\text{total}}=6\times5=30 \]

These are ordered placements because B and C are different people.

We now need to identify how many of these 30 placements produce zero, one, or two adjacent pairs.

Three adjacent pairs are impossible: three people cannot occupy three pairwise neighbouring seats on a seven-seat circle.

Step 3: Count placements with no adjacent pairs.

Neither B nor C can sit next to A.

Therefore, they must occupy seats 2, 3, 4, and 5.

However, B and C cannot sit next to each other either.

The possible unordered pairs of seats are:

\[ \{2,4\},\quad\{2,5\},\quad\{3,5\} \]

There are three possible pairs.

Since B and C are different people, each pair can be occupied in two orders.

Thus:

\[ N_{\text{zero adjacent}}=3\times2=6 \]

Step 4: Count placements with exactly two adjacent pairs.

There are two ways this can happen.

Case A: Both B and C sit next to A.

They occupy seats 1 and 6.

There are two possible orders:

\[ N_A=2 \]

Case B: B and C sit next to each other, with one of them also next to A.

They can occupy:

• Seats 1 and 2.
• Seats 6 and 5.

Each pair of seats has two possible assignments of B and C.

Therefore:

\[ N_B=2\times2=4 \]

Combining both cases:

\[ N_{\text{two adjacent}}=2+4=6 \]

Step 5: Calculate placements with exactly one adjacent pair.

We have accounted for:

• 6 placements with no adjacent pairs.
• 6 placements with two adjacent pairs.

There are 30 placements in total.

Therefore:

\[ \begin{aligned} N_{\text{exactly one adjacent}} &=30-6-6\\ &=18 \end{aligned} \]

There are 18 valid relative placements of B and C.

Step 6: Arrange the remaining four people.

Once A, B, and C have been positioned, D, E, F, and G can occupy the remaining four seats in:

\[ 4!=24 \]

ways.

Hence:

\[ \begin{aligned} N&=18\times4!\\ &=18\times24\\ &=\boxed{432} \end{aligned} \]

There are 432 distinct seating arrangements.

The trap in this question is assuming that the three adjacency conditions can be counted separately without considering their overlap.

For instance, counting arrangements where AB are adjacent, then adding arrangements where BC are adjacent, and finally adding arrangements where CA are adjacent will count some seatings more than once.

The correct approach is to classify the possible relative positions of the three people and account for every overlap.

This is the deeper skill behind difficult counting problems: a correct formula is useful, but understanding how the conditions interact is what makes the formula work.

07What to recognise in your next counting problem

Before calculating, make three decisions:

1. Are you making consecutive choices? Use the fundamental counting principle and multiply the choices at each stage.
2. Are you arranging distinct objects? Use factorials or permutations. For circular arrangements, fix one object to remove rotational duplication.
3. Are there restrictions? Consider blocks for objects that must stay together, complements for objects that must stay apart, and separate cases when conditions overlap.

One final distinction will become increasingly important in Extension 1: arranging objects is different from selecting objects.

If you choose three students for a team, swapping their names does not create a new team. If you assign those same students to three different positions, it does create a new arrangement.

Recognising when order matters is the decision that leads naturally from permutations to combinations.