2. Permutations

Permutations

Introduction to Permutations

Many situations involve arranging objects, people, numbers, or letters in a particular order. For example, students may line up for a photograph, runners may finish a race in different positions, or letters may be arranged to form different codes.

In mathematics, these arrangements are called permutations.

A permutation is an arrangement of objects in which the order matters.

For example, consider the letters A, B, and C.

They can be arranged in six different ways:

• ABC

• ACB

• BAC

• BCA

• CAB

• CBA

Although the same three letters are used, changing their order produces a different permutation.

Permutations are closely related to the Fundamental Counting Principle and provide an efficient way to calculate the number of possible arrangements without listing every outcome.

Understanding Why Order Matters

The defining feature of a permutation is that changing the order creates a different outcome.

Consider three students: Alex, Ben, and Chloe.

If they stand in a line, the arrangement:

Alex – Ben – Chloe

is different from:

Chloe – Ben – Alex

The students are the same, but their positions have changed.

However, if these three students are simply selected to form a committee, their order does not matter.

This distinction separates permutations from combinations.

• Permutation: An arrangement where order matters.

• Combination: A selection where order does not matter.

Examples of Permutations

• Arranging books on a shelf.

• Assigning first, second, and third place.

• Creating an ordered password.

• Seating people in numbered chairs.

• Arranging letters to form codes.

• Choosing a president, vice-president, and secretary.

Examples Where Order Does Not Matter

• Selecting three students for a committee.

• Choosing five lottery numbers when their order is irrelevant.

• Selecting two pizza toppings.

• Choosing four books to borrow without arranging them.

The first question to ask in any counting problem is:

Does changing the order produce a different outcome?

If the answer is yes, permutations may be appropriate.

Permutations and the Fundamental Counting Principle

The Fundamental Counting Principle states that when a process contains several stages, the total number of outcomes can be found by multiplying the number of choices available at each stage.

Suppose four students must stand in a line.

For the first position, there are 4 choices.

After one student is selected, 3 remain for the second position.

Then 2 remain for the third position.

Finally, 1 student remains.

Total arrangements:

4 × 3 × 2 × 1 = 24

Therefore, four different students can stand in a line in 24 different ways.

This process introduces factorial notation.

Factorials

A factorial is the product of all positive integers from 1 up to a given positive integer.

The symbol ! represents a factorial.

For example:

5! = 5 × 4 × 3 × 2 × 1 = 120

4! = 4 × 3 × 2 × 1 = 24

3! = 3 × 2 × 1 = 6

2! = 2 × 1 = 2

1! = 1

By definition:

0! = 1

Why Is 0! Equal to 1?

There is exactly one way to arrange zero objects: the empty arrangement.

Defining 0! = 1 also makes permutation and combination formulas work consistently.

Factorial Examples

Factorials grow very quickly as the number of objects increases.

Arranging All Objects Without Repetition

When n distinct objects are arranged in a line and each object is used exactly once, the number of permutations is:

P = n!

Worked Example: Arranging Books

Six different books are placed on a shelf.

How many arrangements are possible?

Step 1: Identify the number of objects.

n = 6

Step 2: Apply the factorial formula.

P = 6!

Step 3: Calculate.

P = 6 × 5 × 4 × 3 × 2 × 1

Final answer:

720 arrangements

Worked Example: Students in a Line

Five students must stand in a line for a photograph.

How many arrangements are possible?

P = 5!

P = 5 × 4 × 3 × 2 × 1

P = 120

Final answer: 120 arrangements.

Permutations of Some Objects Without Repetition

Sometimes only some of the available objects are arranged.

For example, suppose eight runners compete for three medals:

• Gold

• Silver

• Bronze

The first-place position has 8 possible runners.

The second-place position has 7 remaining runners.

The third-place position has 6 remaining runners.

Total arrangements:

8 × 7 × 6 = 336

There are 336 possible medal arrangements, assuming no ties.

The Permutation Formula

When selecting and arranging r objects from n distinct objects without repetition:

P(n, r) = n!/(n − r)!

This is also written as:

nPr

where:

• n is the total number of available objects.

• r is the number of objects selected and arranged.

• n! is the factorial of n.

• (n − r)! accounts for the objects not selected.

For this formula, n and r are whole numbers satisfying 0 ≤ r ≤ n.

Worked Example: Selecting Three Officers

A club has 10 members.

Three different positions must be filled:

• President

• Vice-president

• Secretary

How many arrangements are possible?

Step 1: Identify n and r.

n = 10

r = 3

Step 2: Apply the formula.

P(10, 3) = 10!/(10 − 3)!

P(10, 3) = 10!/7!

Step 3: Simplify.

P(10, 3) = 10 × 9 × 8

Final answer:

720 arrangements

The positions are different, so assigning the same three people to different roles creates different permutations.

Understanding Permutations Visually

A permutation can be represented using positions or slots.

Suppose five different objects are available and three must be arranged.

The number of choices decreases after each selection because repetition is not allowed.

Permutations With Repetition Allowed

In some arrangements, objects or symbols may be used more than once.

For example, consider a four-digit PIN code.

Each digit may be selected from 0 to 9.

If repetition is allowed, each position has 10 choices.

Total possible PIN codes:

10 × 10 × 10 × 10

= 10⁴

= 10,000

The general formula for arranging r positions using n possible symbols, when repetition is allowed, is:

P = nʳ

Worked Example: Three-Letter Codes

A code contains three letters selected from A, B, C, D, and E.

Letters may be repeated.

How many codes are possible?

Step 1: Identify the number of choices.

n = 5

Step 2: Identify the number of positions.

r = 3

Step 3: Apply the formula.

P = 5³

P = 5 × 5 × 5

Final answer:

125 possible codes

Examples include AAA, ABC, EED, and CBA.

Comparing Repetition Rules

Suppose three-letter codes are created from five available letters.

Allowing repetition increases the number of possible arrangements.

Permutations With Identical Objects

Another type of permutation problem involves objects that are not all distinguishable.

For example, consider the word:

LEVEL

It contains five letters:

L, E, V, E, L

However:

• L appears twice.

• E appears twice.

• V appears once.

If all letters were different, there would be:

5! = 120 arrangements

But exchanging the two Ls does not create a new arrangement. The same is true for the two Es.

To correct for this, divide by the factorials of the repeated counts.

P = n!/(a!b!c!...)

where a, b, c, ... represent the numbers of identical objects of each type.

Worked Example: Arranging LEVEL

Step 1: Count all letters.

n = 5

Step 2: Identify repeated letters.

L appears twice.

E appears twice.

Step 3: Apply the formula.

P = 5!/(2! × 2!)

Step 4: Calculate.

P = 120/(2 × 2)

P = 30

Final answer:

30 distinct arrangements

Worked Example: Arranging BANANA

The word BANANA contains six letters.

• A appears three times.

• N appears twice.

• B appears once.

P = 6!/(3! × 2!)

P = 720/(6 × 2)

Final answer:

60 distinct arrangements

Distinguishing Permutations from Combinations

Permutations and combinations are closely related, but they answer different questions.

Permutations: Order Matters

Suppose five students are available for two positions:

• Captain

• Vice-captain

The number of possible arrangements is:

P(5, 2) = 5 × 4 = 20

Choosing Alex as captain and Ben as vice-captain is different from choosing Ben as captain and Alex as vice-captain.

Combinations: Order Does Not Matter

Suppose five students are available and two must be selected for a committee.

The number of combinations is:

C(5, 2) = 5!/(2! × 3!)

C(5, 2) = 10

There are only 10 possible pairs because the order of selection does not matter.

Comparing the Methods

A useful relationship is:

P(n, r) = C(n, r) × r!

This means that each selection of r distinct objects can be arranged in r! different orders.

Solving Ordering Problems with Restrictions

Some permutation problems include additional conditions.

These restrictions must be considered before calculating the number of arrangements.

Worked Example: Two Students Must Stand Together

Five students are standing in a line.

Alex and Ben must stand next to each other.

How many arrangements are possible?

Step 1: Treat Alex and Ben as one group.

Instead of five separate objects, there are now four objects:

• (Alex, Ben)

• Student C

• Student D

• Student E

Step 2: Arrange the four objects.

4! = 24

Step 3: Arrange Alex and Ben within their group.

They can stand as:

Alex–Ben

or:

Ben–Alex

There are 2! = 2 internal arrangements.

Step 4: Multiply.

24 × 2 = 48

Final answer:

48 arrangements

Worked Example: Two Students Must Not Stand Together

Five students stand in a line.

Alex and Ben must not stand next to each other.

Step 1: Count all possible arrangements.

5! = 120

Step 2: Count arrangements where they stand together.

4! × 2! = 48

Step 3: Subtract.

120 − 48 = 72

Final answer:

72 arrangements

This demonstrates the usefulness of the complementary counting method:

Valid arrangements = Total arrangements − Invalid arrangements

Circular Permutations

Sometimes objects or people are arranged around a circle rather than in a straight line.

For example, six people may sit around a round table.

In a circular arrangement, rotating everyone together does not usually create a new arrangement because the relative positions remain unchanged.

For n distinct objects arranged around a circle, when rotations are considered equivalent but reflections are distinct:

P = (n − 1)!

Worked Example: Round Table Seating

Six people sit around a circular table.

How many different seating arrangements are possible?

P = (6 − 1)!

P = 5!

P = 120

Final answer:

120 circular arrangements

Important Distinction

For circular arrangements:

• Rotations are usually treated as the same arrangement.

• Clockwise and counterclockwise orderings are generally considered different.

• If mirror-image arrangements are also considered identical, additional adjustments may be required.

The interpretation depends on the context of the problem.

Permutations in Real-World Situations

Passwords and Security Codes

Permutations are important in digital security.

Suppose a password consists of:

• 3 uppercase letters

• Followed by 2 digits

Repetition is allowed.

Each letter has 26 choices.

Each digit has 10 choices.

Total passwords:

26³ × 10²

= 17,576 × 100

= 1,757,600

Final answer: 1,757,600 possible passwords.

This illustrates how password length and the number of available characters affect the size of the possible password space.

Sports Competitions

Suppose 12 runners compete in a race.

How many possible arrangements are there for the first three finishers?

P(12, 3) = 12 × 11 × 10

Final answer: 1,320 arrangements, assuming no ties.

Scheduling Presentations

Seven students must give presentations, one after another.

How many possible presentation orders are there?

P = 7!

P = 5,040

Final answer: 5,040 possible schedules.

Product Displays

A shop has eight different products but only four display positions.

How many different arrangements can be created?

P(8, 4) = 8 × 7 × 6 × 5

Final answer: 1,680 arrangements.

Computer Science

Permutations are used in computer science when working with:

• Sorting algorithms.

• Search problems.

• Scheduling systems.

• Cryptography.

• Route planning.

• Data organization.

For example, a computer program may need to evaluate different task orders to identify the most efficient schedule.

Choosing the Correct Permutation Method

Different permutation problems require different approaches.

Before using a formula, always identify the conditions of the problem.

Common Mistakes

Confusing permutations with combinations

Permutations involve order. Combinations involve selection without regard to order.

Using n! when only some objects are arranged

If only r objects are selected from n, use P(n, r) rather than n!.

Ignoring repetition rules

Repetition allowed and repetition not allowed produce different totals.

Confusing repeated selection with identical objects

Selecting the same symbol multiple times is different from arranging a fixed collection containing identical objects.

Forgetting to divide for identical objects

Repeated letters or identical items reduce the number of distinct arrangements.

Treating circular arrangements like linear arrangements

For circular arrangements where rotations are equivalent, use (n − 1)! rather than n!.

Ignoring restrictions

Conditions such as two people standing together or certain digits being excluded must be incorporated.

Forgetting that a number cannot begin with zero

A four-digit number cannot begin with zero, although a four-digit code may.

Counting the same arrangement more than once

This can happen when objects are identical or when circular rotations are considered equivalent.

Applying formulas without checking whether order matters

The structure of the problem should determine the method, not simply the presence of numbers.

Key Terms

• Permutation: An arrangement of objects in which order matters.

• Arrangement: A particular ordering of objects.

• Factorial: The product of all positive integers from 1 to a given positive integer.

• Fundamental Counting Principle: A rule used to calculate total outcomes by multiplying the choices available at each stage.

• Permutation Formula: The expression P(n, r) = n!/(n − r)! for arranging r distinct objects from n without repetition.

• Repetition Allowed: A condition where an object or symbol may be selected more than once.

• Repetition Not Allowed: A condition where an object or symbol may be selected only once.

• Distinct Objects: Objects that can be distinguished from one another.

• Identical Objects: Objects that cannot be distinguished from one another.

• Linear Permutation: An arrangement of objects in a straight line or ordered sequence.

• Circular Permutation: An arrangement around a circle, where rotations may be considered equivalent.

• Combination: A selection of objects in which order does not matter.

• Selection: The process of choosing objects from a larger set.

• Restriction: A condition that limits the possible arrangements.

• Block Method: A counting technique in which objects that must remain together are treated as one group.

• Complementary Counting: A method that subtracts invalid arrangements from the total number of arrangements.

• Position: A particular place within an ordered arrangement.

• Sample Space: The set of all possible outcomes of an experiment or process.

• Counting Method: A mathematical strategy used to determine the number of possible outcomes.

• Ordering Problem: A problem involving the arrangement of objects in particular positions.

Key Takeaways

• A permutation is an arrangement in which order matters.

• Changing the order of objects creates a different permutation.

• Permutations are based on the Fundamental Counting Principle.

• Factorials provide a compact way to count arrangements of distinct objects.

• The number of ways to arrange n distinct objects is n!.

• The number of ways to arrange r objects from n distinct objects without repetition is P(n, r) = n!/(n − r)!.

• When repetition is allowed and each of r positions has n choices, the number of arrangements is nʳ.

• Arrangements containing identical objects require division by the factorials of repeated counts.

• Permutations differ from combinations because combinations do not consider order.

• Circular arrangements often use (n − 1)! when rotations are considered equivalent.

• Restricted permutation problems may require grouping objects or subtracting invalid arrangements.

• The correct counting method depends on whether order matters, whether repetition is allowed, and whether restrictions apply.

• Permutations are useful in passwords, scheduling, sports competitions, seating arrangements, product displays, and computer science.

• A systematic approach helps prevent double-counting and ensures accurate results.

Check Your Understanding

Recall and Understanding

1. Define a permutation and explain why order matters.

2. Explain the difference between a permutation and a combination.

3. What does factorial notation represent?

4. State the formula for permutations without repetition.

5. Explain the difference between repetition allowed and repetition not allowed.

Application

6. Calculate 6!.

7. How many ways can five different books be arranged on a shelf?

8. How many ways can three students be selected and arranged from a group of eight?

9. A four-digit PIN uses digits 0–9. How many PINs are possible if repetition is allowed?

10. How many distinct arrangements can be made using the letters in the word LEVEL?

Analysis and Challenge

11. Seven students must stand in a line. How many arrangements are possible if two particular students must stand together?

12. Six people sit around a circular table. How many distinct seating arrangements are possible if rotations are considered equivalent?

13. How many four-digit numbers can be formed using digits 0–9 if repetition is not allowed?

14. A school must choose a president, vice-president, and secretary from 12 students. How many different assignments are possible?

15. A password contains three letters followed by two digits. Letters cannot repeat, but digits may repeat. Calculate the total number of possible passwords.

Final Summary

Permutations provide a mathematical method for counting arrangements in which the order of objects matters.

By applying factorials, the Fundamental Counting Principle, and permutation formulas, large numbers of possible arrangements can be calculated efficiently.

Different situations require different methods depending on whether repetition is allowed, objects are identical, arrangements are circular, or additional restrictions apply.

Understanding permutations is an important foundation for probability, statistics, combinatorics, computer science, cryptography, and practical decision-making problems.