1. The Fundamental Counting Principle

The Fundamental Counting Principle

Introduction to the Fundamental Counting Principle

Many everyday situations involve making several choices. You might choose an outfit, create a password, order a meal, or plan a journey using different transportation options.

Rather than listing every possible combination, mathematics provides a faster and more systematic way to count the outcomes.

The Fundamental Counting Principle, also called the Multiplication Principle, states:

If one stage of a process can be completed in m ways and a second stage can be completed in n ways for each first-stage choice, then the complete process can be completed in m × n ways.

For example, suppose a restaurant offers:

• 3 main courses

• 4 drinks

If you choose one main course and one drink, the total number of possible combinations is:

3 × 4 = 12 combinations

The principle can be extended to any number of stages.

Understanding the Multiplication Principle

The Fundamental Counting Principle is based on the idea that each choice can be paired with other available choices.

Suppose a student has:

• 2 shirts: red and blue

• 3 pairs of trousers: black, grey, and beige

The student can create the following outfits:

There are 6 possible outfits.

Using the Fundamental Counting Principle:

2 × 3 = 6

This is much faster than listing every combination, especially when there are many choices.

General Formula

If a process has k stages, with n₁, n₂, n₃, ..., nₖ choices at each stage, then:

Total outcomes = n₁ × n₂ × n₃ × ... × nₖ

This formula applies when the number of choices at each stage is known and consistent for every preceding choice.

If the available choices depend on earlier decisions, the problem may need to be divided into cases.

Multi-Stage Counting Problems

Many counting problems involve more than two stages.

For example, suppose a café offers:

• 4 sandwiches

• 3 drinks

• 2 desserts

A customer chooses one item from each category.

The number of possible meals is:

4 × 3 × 2 = 24

There are 24 different meal combinations.

Worked Example: Choosing an Outfit

A student has:

• 5 shirts

• 4 pairs of trousers

• 3 pairs of shoes

How many different outfits can the student create?

Step 1: Identify the stages.

Shirt → Trousers → Shoes

Step 2: Identify the number of choices.

5, 4, and 3

Step 3: Multiply.

5 × 4 × 3 = 60

Final answer: 60 different outfits.

Worked Example: Planning a Journey

A traveler can choose between:

• 3 airlines

• 4 hotels

• 2 transportation options from the airport

How many travel arrangements are possible?

3 × 4 × 2 = 24

Final answer: 24 possible arrangements, assuming every combination is available.

Representing Counting Problems with Tree Diagrams

A tree diagram is a visual method for organizing multi-stage choices.

Each branch represents a possible decision.

For example, suppose a student chooses:

• One of 2 drinks: water or juice

• One of 3 snacks: apple, banana, or biscuit

A tree diagram can show all possible combinations.

The possible outcomes are:

• Water and apple

• Water and banana

• Water and biscuit

• Juice and apple

• Juice and banana

• Juice and biscuit

The tree has 6 final branches.

Using the Fundamental Counting Principle:

2 × 3 = 6

When Are Tree Diagrams Useful?

Tree diagrams are particularly useful when:

• There are relatively few choices.

• The problem involves several stages.

• Students need to visualize the decision process.

• Choices depend on previous selections.

• The problem involves probability.

For very large counting problems, multiplication is usually more efficient.

Representing Counting Problems with Tables

Tables provide another systematic way to organize outcomes.

Suppose a coin is flipped and a six-sided die is rolled.

The coin has 2 possible outcomes:

H, T

The die has 6 possible outcomes:

1, 2, 3, 4, 5, 6

Total outcomes:

2 × 6 = 12

A table is useful because it helps ensure that no outcomes are missed or counted more than once.

Counting with Repetition Allowed

In some counting problems, an item may be selected more than once.

For example, consider a four-digit PIN code.

Each digit can be any number from 0 to 9.

If repetition is allowed, each position has 10 choices.

The total number of possible PINs is:

10 × 10 × 10 × 10

= 10⁴

= 10,000

Final answer: 10,000 possible PIN codes.

This includes codes such as 0000, 1111, and 2020.

Worked Example: Repeated Letters

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

Letters may be repeated.

Each position has 5 choices.

Total outcomes:

5 × 5 × 5 = 125

Final answer: 125 different codes.

Counting Without Repetition

Some counting problems do not allow the same item to be selected more than once.

For example, suppose a code consists of three different digits selected from 0 to 9.

The first digit has 10 choices.

The second digit has 9 choices because one digit has already been used.

The third digit has 8 choices.

Total outcomes:

10 × 9 × 8 = 720

Final answer: 720 possible codes.

Worked Example: Arranging Books

Five different books are placed on a shelf.

How many different arrangements are possible?

For the first position, there are 5 choices.

For the second position, there are 4 remaining choices.

For the third position, there are 3 choices.

For the fourth position, there are 2 choices.

For the final position, there is 1 choice.

Total arrangements:

5 × 4 × 3 × 2 × 1 = 120

Final answer: 120 arrangements.

This introduces the concept of factorials.

Factorials and Counting

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

Factorials are written using an exclamation mark.

For example:

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

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

3! = 3 × 2 × 1 = 6

By definition:

0! = 1

Factorials are useful when arranging distinct objects without repetition.

The Addition Principle

Not every counting problem requires multiplication.

Sometimes we must choose between separate alternatives.

The Addition Principle states that if one option can occur in m ways and another mutually exclusive option can occur in n ways, then there are:

m + n total possibilities

For example, a student may choose:

• One of 4 science clubs

• Or one of 3 sports clubs

If the student joins exactly one club, the total number of choices is:

4 + 3 = 7

Multiplication Versus Addition

The key difference is:

• AND usually indicates multiplication.

• OR usually indicates addition, provided the alternatives do not overlap.

Examples:

Choose a shirt AND trousers:

3 × 4 = 12

Choose a shirt OR a pair of trousers:

3 + 4 = 7

These keywords are helpful, but students must always consider the actual structure of the problem.

Combining Addition and Multiplication

Some counting problems require both principles.

Worked Example: Choosing a Meal

A restaurant offers two meal options.

Option A

• 3 sandwiches

• 2 drinks

Option B

• 4 salads

• 3 drinks

A customer chooses one complete meal from either Option A or Option B.

Step 1: Count Option A.

3 × 2 = 6

Step 2: Count Option B.

4 × 3 = 12

Step 3: Add the alternatives.

6 + 12 = 18

Final answer: 18 possible meals.

This illustrates how counting problems can be divided into separate cases.

Distinguishing Different Counting Methods

There are several important methods for solving counting problems.

The Fundamental Counting Principle forms the foundation for several of these methods.

Permutations and the Fundamental Counting Principle

A permutation is an arrangement in which order matters.

For example, suppose 6 students compete for three awards:

• First place

• Second place

• Third place

The number of possible outcomes is:

6 × 5 × 4 = 120

The order matters because receiving first place is different from receiving third place.

The permutation formula is:

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

where:

• n is the number of available objects.

• r is the number selected and arranged.

For this example:

P(6, 3) = 6!/3!

= 120

Combinations and the Fundamental Counting Principle

A combination is a selection in which order does not matter.

Suppose 6 students are available and 3 must be chosen for a committee.

Choosing students A, B, and C is the same committee as choosing C, A, and B.

The number of combinations is:

C(n, r) = n!/[r!(n − r)!]

For this example:

C(6, 3) = 6!/(3! × 3!)

= 20

There are 20 different committees.

Why Permutations and Combinations Differ

Permutations count arrangements.

Combinations count groups.

For example:

ABC, ACB, BAC, BCA, CAB, CBA

are six different permutations of the same three objects.

However, they represent only one combination.

Practical Applications of the Fundamental Counting Principle

Passwords and Security

The Fundamental Counting Principle helps calculate the number of possible passwords.

Suppose a password contains:

• 2 letters

• Followed by 3 digits

Assume letters and digits may repeat.

Each letter has 26 choices.

Each digit has 10 choices.

Total passwords:

26 × 26 × 10 × 10 × 10

= 676,000

Final answer: 676,000 possible passwords.

If uppercase and lowercase letters are treated as different characters, the number of possibilities increases substantially.

Vehicle Registration Numbers

Suppose a vehicle registration number contains:

• 3 letters

• Followed by 4 digits

If repetition is allowed:

26³ × 10⁴

= 175,760,000

There are 175,760,000 possible registration numbers under these rules.

Sports Competitions

Suppose 8 runners compete for gold, silver, and bronze medals.

The number of possible podium arrangements is:

8 × 7 × 6 = 336

There are 336 possible medal arrangements, assuming no ties.

Product Customization

A company allows customers to design a backpack using:

• 5 colours

• 3 sizes

• 4 patterns

• 2 types of straps

The total number of possible designs is:

5 × 3 × 4 × 2 = 120

There are 120 possible backpack designs, assuming all combinations are available.

Solving More Challenging Counting Problems

Some counting problems involve restrictions that change the number of choices.

Worked Example: Four-Digit Numbers

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

A four-digit number cannot begin with zero.

Therefore:

• First digit: 9 choices (1–9)

• Second digit: 10 choices

• Third digit: 10 choices

• Fourth digit: 10 choices

Total:

9 × 10 × 10 × 10

= 9,000

Final answer: 9,000 four-digit numbers.

Worked Example: Without Repetition

How many four-digit numbers can be formed using the digits 0–9 if no digit may be repeated?

First digit: 9 choices.

Second digit: 9 choices (zero is available, but the first digit cannot be reused).

Third digit: 8 choices.

Fourth digit: 7 choices.

Total:

9 × 9 × 8 × 7

= 4,536

Final answer: 4,536 numbers.

Worked Example: Counting with a Restriction

A three-digit code uses digits 0–9.

Repetition is allowed, but the final digit must be even.

How many codes are possible?

First digit: 10 choices.

Second digit: 10 choices.

Final digit: 5 choices (0, 2, 4, 6, 8).

Total:

10 × 10 × 5 = 500

Final answer: 500 possible codes.

A Systematic Strategy for Counting Problems

When solving a counting problem, use the following approach.

Identify the stages

Determine how many separate decisions must be made.

Determine the number of choices

Count the available options at each stage.

Check restrictions

Ask whether repetition is allowed and whether previous choices affect later choices.

Decide whether order matters

This helps distinguish permutations from combinations.

Choose the correct operation

Use multiplication for sequential stages and addition for separate, mutually exclusive alternatives.

Calculate and check

Make sure the answer is reasonable and that no outcomes have been counted twice or omitted.

Common Mistakes

Adding instead of multiplying

When a complete outcome requires several choices, multiplication is often appropriate.

Multiplying when alternatives should be added

When selecting one option from separate categories, addition may be required.

Ignoring repetition restrictions

If repetition is not allowed, the number of available choices usually decreases after each selection.

Forgetting that zero cannot begin a multi-digit number

A code may begin with zero, but an ordinary four-digit number cannot.

Confusing permutations and combinations

Permutations involve arrangements where order matters.

Combinations involve selections where order does not matter.

Counting the same outcome more than once

This is particularly common when using the Addition Principle with overlapping categories.

Assuming every stage has the same number of choices

Some stages have restrictions that change the number of possibilities.

Failing to identify all stages

Leaving out a stage produces an incorrect total.

Using a formula without understanding the situation

It is better to identify the counting structure before selecting a formula.

Key Terms

• Fundamental Counting Principle: A rule stating that the total number of outcomes in a multi-stage process is found by multiplying the number of choices at each stage, when those counts apply consistently.

• Multiplication Principle: Another name for the Fundamental Counting Principle.

• Counting problem: A mathematical problem involving the number of possible outcomes or arrangements.

• Outcome: One possible result of a process.

• Stage: A separate decision or step within a counting process.

• Choice: An available option at a particular stage.

• Tree diagram: A branching diagram used to organize possible outcomes.

• Systematic listing: A method of recording all possible outcomes in an organized way.

• Addition Principle: A rule used to count outcomes from mutually exclusive alternatives.

• Mutually exclusive: Describes outcomes or categories that cannot occur together.

• Repetition: The reuse of an item or option in a counting process.

• Restriction: A condition limiting the available choices.

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

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

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

• Arrangement: A particular ordering of selected objects.

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

• Sample space: The set of all possible outcomes of a random experiment.

• Independent choices: Choices in which one selection does not affect the available options in another stage.

• Dependent choices: Choices in which earlier selections affect later options.

Key Takeaways

• The Fundamental Counting Principle is used to calculate the total number of outcomes in a multi-stage process.

• When each stage has a fixed number of available choices, multiply the number of choices at each stage.

• Multi-stage counting problems can be represented using tables, lists, and tree diagrams.

• Tree diagrams are useful for visualizing smaller counting problems.

• The Addition Principle is used when counting mutually exclusive alternatives.

• The Multiplication Principle is used when combining sequential choices.

• Counting problems may require both addition and multiplication.

• Repetition rules can significantly change the number of possible outcomes.

• When repetition is not allowed, the number of choices often decreases after each selection.

• Factorials provide a compact way to represent products of consecutive positive integers.

• Permutations count arrangements where order matters.

• Combinations count selections where order does not matter.

• Restrictions must be considered carefully before multiplying.

• The Fundamental Counting Principle is useful in passwords, codes, sports, travel, product design, and probability.

• A systematic approach helps prevent missed outcomes and double-counting.

Check Your Understanding

Recall and Understanding

1. State the Fundamental Counting Principle in your own words.

2. Explain the difference between the Addition Principle and the Multiplication Principle.

3. What is a tree diagram, and when is it useful?

4. Explain the difference between counting with repetition and counting without repetition.

5. What is the difference between a permutation and a combination?

Application

6. A student has 4 shirts, 3 pairs of trousers, and 2 pairs of shoes. How many different outfits can be created?

7. A restaurant offers 5 main courses, 4 drinks, and 3 desserts. How many complete meals are possible?

8. A code contains 3 digits from 0–9. How many codes are possible if repetition is allowed?

9. How many different arrangements can be made using 6 distinct books?

10. A coin is flipped and an eight-sided die is rolled. How many possible outcomes are there?

Analysis and Challenge

11. How many four-digit numbers can be formed using digits 0–9 if no digit may be repeated?

12. A password consists of 2 letters followed by 3 digits. How many passwords are possible if letters cannot repeat but digits may repeat?

13. Eight students compete for first, second, and third place. How many possible podium arrangements are there?

14. A student must choose either a science activity from 5 options or a sports activity from 4 options. Explain why addition is used rather than multiplication.

15. A company creates identification codes containing 2 letters and 4 digits. The letters may repeat, but the digits must all be different. Calculate the number of possible codes.

Final Summary

The Fundamental Counting Principle provides a powerful method for solving problems involving several stages of choice.

By multiplying the number of possibilities at each stage, we can calculate large numbers of outcomes without listing every possibility individually.

Understanding when to use multiplication, addition, factorials, permutations, and combinations allows students to solve increasingly complicated counting problems.

These methods form an important foundation for probability, statistics, computer science, cryptography, and many practical decision-making situations.

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.

3. Combinations

Combinations

Introduction to Combinations

Many everyday situations involve choosing objects or people from a larger group. For example, a teacher may select students for a committee, a coach may choose players for a team, or a customer may select toppings for a pizza.

In these situations, the order in which the objects are selected often does not matter.

A combination is a selection of objects from a larger set in which order does not matter.

For example, suppose three students—Alex, Ben, and Chloe—are selected for a science project.

Selecting Alex, Ben, and Chloe produces the same group as selecting Chloe, Alex, and Ben.

Although the order of the names changes, the members of the group remain the same.

Combinations provide a mathematical method for calculating the number of different groups that can be formed without listing every possibility.

Understanding Why Order Does Not Matter

The defining feature of a combination is that changing the order of selected objects does not create a new outcome.

Consider four students:

A, B, C, D

Suppose two students must be selected.

The possible combinations are:

• AB

• AC

• AD

• BC

• BD

• CD

There are six different combinations.

Notice that AB and BA are not counted separately because they contain the same two students.

Comparing Arrangements and Selections

If two students are selected for different positions, such as president and vice-president, order matters.

AB means A is president and B is vice-president.

BA means B is president and A is vice-president.

These are different permutations.

However, if A and B are simply selected for a committee, AB and BA represent the same combination.

This distinction is essential when deciding which counting method to use.

Combinations and Permutations

Permutations and combinations both involve selecting objects from a larger set.

The difference is whether order matters.

Worked Example: Selecting Two Students

Suppose five students are available.

Situation A: Choosing a captain and vice-captain

Order matters because the positions are different.

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

There are 20 possible assignments.

Situation B: Choosing two students for a committee

Order does not matter.

C(5, 2) = 10

There are 10 possible committees.

The number of combinations is smaller because different arrangements of the same selected objects are counted only once.

The Combination Formula

The number of ways to select r objects from n distinct objects without repetition is:

C(n, r) = n!/[r!(n − r)!]

This is also written as:

nCr

or read as:

"n choose r"

where:

• n is the total number of available objects.

• r is the number of objects selected.

• ! represents factorial.

The formula applies when 0 ≤ r ≤ n and both are whole numbers.

Understanding Factorials

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

For example:

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

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

3! = 3 × 2 × 1 = 6

By definition:

0! = 1

Factorials allow combination calculations to be written efficiently.

Why the Combination Formula Works

The combination formula can be derived from the permutation formula.

Suppose we want to select three students from a group of five.

If order matters, the number of permutations is:

P(5, 3) = 5 × 4 × 3 = 60

However, each group of three students can be arranged in:

3! = 6 ways

For example, the group ABC can be arranged as:

ABC, ACB, BAC, BCA, CAB, CBA

All six arrangements represent the same combination.

Therefore, divide the number of permutations by 3!.

C(5, 3) = 60/6

C(5, 3) = 10

This gives the general relationship:

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

Substituting the permutation formula:

C(n, r) = [n!/(n − r)!]/r!

Therefore:

C(n, r) = n!/[r!(n − r)!]

Calculating Combinations

To calculate a combination:

1. Identify the total number of objects, n.

2. Identify how many objects are selected, r.

3. Substitute into the combination formula.

4. Simplify the factorial expressions.

5. Calculate the result.

Worked Example: Choosing a Committee

A class has 8 students.

How many different committees of 3 students can be formed?

Step 1: Identify n and r.

n = 8

r = 3

Step 2: Apply the formula.

C(8, 3) = 8!/[3!(8 − 3)!]

Step 3: Simplify.

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

C(8, 3) = (8 × 7 × 6)/(3 × 2 × 1)

Step 4: Calculate.

C(8, 3) = 336/6

Final answer:

56 different committees

Worked Example: Choosing Books

A student has 10 different books but can take only 4 on a trip.

How many different groups of 4 books can be selected?

n = 10

r = 4

C(10, 4) = 10!/(4! × 6!)

C(10, 4) = (10 × 9 × 8 × 7)/(4 × 3 × 2 × 1)

C(10, 4) = 5040/24

Final answer:

210 possible selections

The order in which the books are chosen does not matter.

Using a Calculator to Find Combinations

Many scientific calculators include a function labeled:

nCr

This function calculates combinations directly.

For example, to calculate:

C(8, 3)

enter:

8 nCr 3

The calculator returns:

56

This method is particularly useful when working with large numbers.

However, students should understand the formula and why it works rather than relying only on a calculator.

Important Properties of Combinations

Combinations have several useful mathematical properties.

Selecting Zero Objects

There is exactly one way to select no objects from a set.

Therefore:

C(n, 0) = 1

Selecting Every Object

There is exactly one way to select all n objects.

Therefore:

C(n, n) = 1

Selecting One Object

There are n ways to select one object from n available objects.

Therefore:

C(n, 1) = n

Symmetry Property

An important property is:

C(n, r) = C(n, n − r)

For example:

C(8, 3) = C(8, 5)

Both equal 56.

Why Does This Work?

Choosing 3 students from a group of 8 automatically determines which 5 students are not chosen.

Every selection of 3 students corresponds to exactly one group of 5 students who remain.

Therefore, the number of ways to select 3 students equals the number of ways to leave out 3 students, or equivalently select the remaining 5.

This property can simplify calculations.

Pascal's Triangle and Combinations

Combinations are closely connected to Pascal's Triangle.

Pascal's Triangle is a triangular arrangement of numbers in which each interior number is the sum of the two numbers directly above it.

For example, the row:

1, 4, 6, 4, 1

represents:

C(4, 0) = 1

C(4, 1) = 4

C(4, 2) = 6

C(4, 3) = 4

C(4, 4) = 1

Pascal's Identity

The relationship between adjacent rows is expressed by:

C(n, r) = C(n − 1, r − 1) + C(n − 1, r)

This identity is useful in probability, algebra, and combinatorics.

Combinations and the Binomial Theorem

Combinations also appear in the expansion of binomial expressions.

For example:

(a + b)² = a² + 2ab + b²

The coefficients are:

1, 2, 1

These correspond to the second row of Pascal's Triangle.

Similarly:

(a + b)³ = a³ + 3a²b + 3ab² + b³

The coefficients are:

1, 3, 3, 1

For a positive integer n, the Binomial Theorem states:

(a + b)ⁿ = Σ C(n, r)a^(n−r)bʳ

where the sum runs from r = 0 to n.

This demonstrates an important connection between counting selections and algebraic expansion.

Solving Selection Problems

Some combination problems involve restrictions or multiple groups.

These problems may require both the combination formula and the Fundamental Counting Principle.

Worked Example: Selecting Boys and Girls

A class contains:

• 6 boys

• 5 girls

A committee must contain exactly:

• 2 boys

• 2 girls

How many committees are possible?

Step 1: Choose the boys.

C(6, 2) = 15

Step 2: Choose the girls.

C(5, 2) = 10

Step 3: Multiply.

15 × 10 = 150

Final answer:

150 possible committees

The multiplication is used because each selection of boys can be paired with each selection of girls.

Worked Example: At Least One Girl

A class contains 5 boys and 4 girls.

A committee of 3 students must contain at least one girl.

How many committees are possible?

Method: Complementary Counting

First calculate the total number of committees:

C(9, 3) = 84

Next calculate committees containing only boys:

C(5, 3) = 10

Subtract:

84 − 10 = 74

Final answer:

74 possible committees

This method is often easier than counting every acceptable case separately.

Combinations with Restrictions

Some problems require particular objects to be included or excluded.

Worked Example: A Particular Student Must Be Included

A group contains 10 students.

A committee of 4 must include Alex.

How many committees are possible?

Since Alex is already included, only 3 additional students must be selected.

There are 9 remaining students.

C(9, 3) = 84

Final answer:

84 possible committees

Worked Example: Two Students Cannot Be Selected Together

A group contains 8 students.

A committee of 3 is selected.

Alex and Ben cannot both be on the committee.

Step 1: Count all possible committees.

C(8, 3) = 56

Step 2: Count committees containing both Alex and Ben.

If both are selected, one more student must be chosen from the remaining 6.

C(6, 1) = 6

Step 3: Subtract.

56 − 6 = 50

Final answer:

50 possible committees

Combinations with Repetition

In some selection problems, the same type of object may be chosen more than once.

For example, suppose an ice cream shop offers 4 flavours.

A customer chooses 3 scoops, and flavours may be repeated.

If the order of the scoops does not matter, this is a combination with repetition.

The formula is:

C(n + r − 1, r)

where:

• n is the number of available types.

• r is the number of objects selected.

Worked Example: Choosing Ice Cream Scoops

There are 4 flavours and a customer chooses 3 scoops.

Repetition is allowed.

C(4 + 3 − 1, 3)

= C(6, 3)

= 20

Final answer:

20 possible flavour combinations

This includes selections such as:

• Vanilla, vanilla, vanilla

• Vanilla, chocolate, strawberry

• Chocolate, chocolate, mint

The order of the scoops is not counted.

Important Distinction

Combinations without repetition:

C(n, r) = n!/[r!(n − r)!]

Combinations with repetition:

C(n + r − 1, r)

These formulas apply to different situations.

Practical Applications of Combinations

Choosing Sports Teams

A coach has 15 players and must select 5 for a starting team.

Assuming all players are eligible and positions do not matter:

C(15, 5) = 3,003

There are 3,003 possible teams.

Lottery Numbers

Suppose a lottery requires selecting 6 different numbers from 49.

The order of the numbers does not matter.

The number of possible selections is:

C(49, 6) = 13,983,816

There are 13,983,816 possible combinations.

This illustrates why matching all six numbers is unlikely when every combination is equally likely.

Choosing Pizza Toppings

A pizza restaurant offers 8 different toppings.

A customer chooses exactly 3 different toppings.

C(8, 3) = 56

There are 56 possible topping combinations.

Scientific Experiments

A scientist has 10 samples and must select 4 for testing.

If the order of testing does not matter:

C(10, 4) = 210

There are 210 possible groups of samples.

Computer Science and Data Analysis

Combinations are useful in:

• Selecting features for machine-learning models.

• Forming groups of data points.

• Testing subsets of variables.

• Designing experiments.

• Analyzing networks.

• Solving optimization problems.

For example, a researcher may need to determine how many different groups of variables can be selected from a larger dataset.

Choosing the Correct Counting Method

Before solving a counting problem, ask three important questions.

Does order matter?

If yes, use permutations.

If no, use combinations.

Is repetition allowed?

If yes, the counting method may need to account for repeated selections.

Are there restrictions?

If yes, divide the problem into cases, use complementary counting, or apply additional multiplication.

Summary of Counting Methods

Common Mistakes

Confusing combinations with permutations

Combinations do not consider order, while permutations do.

Using the permutation formula for selection problems

If order does not matter, the combination formula should usually be used.

Forgetting to divide by r!

The combination formula accounts for repeated arrangements of the same selected objects.

Using the wrong values for n and r

n represents the total number available, while r represents the number selected.

Ignoring restrictions

Conditions such as requiring particular members or excluding certain combinations must be included.

Assuming repetition is always allowed

The standard combination formula assumes objects are selected without repetition.

Confusing combinations with repetition and permutations with repetition

Selecting repeated items without regard to order is different from arranging repeated symbols in positions.

Adding when multiplication is required

When independent selections must be combined, such as choosing boys and girls for a committee, multiplication is often appropriate.

Counting the same group more than once

Different selection orders do not create different combinations.

Key Terms

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

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

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

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

• Combination Formula: The expression C(n, r) = n!/[r!(n − r)!].

• Binomial Coefficient: Another name for C(n, r), often read as "n choose r."

• Fundamental Counting Principle: A rule used to calculate outcomes by multiplying choices across stages.

• Pascal's Triangle: A triangular arrangement of numbers containing binomial coefficients.

• Pascal's Identity: The relationship C(n, r) = C(n − 1, r − 1) + C(n − 1, r).

• Binomial Theorem: A rule for expanding powers of binomial expressions using combination coefficients.

• Repetition: The selection of the same object or type more than once.

• Combination with Repetition: A selection in which repeated types are allowed and order does not matter.

• Restriction: A condition that limits which selections are permitted.

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

• Mutually Exclusive Cases: Cases that cannot occur simultaneously.

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

• Combinatorics: The branch of mathematics concerned with counting, arrangements, and selections.

• Symmetry Property: The relationship C(n, r) = C(n, n − r).

• Committee Problem: A common counting problem involving the selection of group members.

• Probability: The mathematical study of the likelihood of events.

Key Takeaways

• A combination is a selection in which order does not matter.

• Changing the order of selected objects does not create a new combination.

• Combinations differ from permutations because permutations count arrangements.

• The standard combination formula is C(n, r) = n!/[r!(n − r)!].

• The combination formula can be derived by dividing permutations by r!.

• Factorials are used to calculate combinations efficiently.

• The number of ways to select zero objects or all available objects is always 1.

• The symmetry property states that C(n, r) = C(n, n − r).

• Pascal's Triangle contains combination values.

• Combinations are closely related to the Binomial Theorem.

• Selection problems with restrictions may require multiplication, addition, or complementary counting.

• Combinations with repetition use a different formula from combinations without repetition.

• Combinations are useful in team selection, committees, lotteries, scientific experiments, product choices, and computer science.

• Understanding combinations is an important foundation for probability, statistics, and advanced counting methods.

Check Your Understanding

Recall and Understanding

1. Define a combination and explain why order does not matter.

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

3. State the combination formula and explain the meaning of n and r.

4. Why do we divide permutations by r! to calculate combinations?

5. Explain the symmetry property C(n, r) = C(n, n − r).

Application

6. Calculate C(6, 2).

7. A class has 10 students. How many committees of 3 students can be formed?

8. A student has 8 books and wants to select 4. How many selections are possible?

9. A pizza restaurant offers 7 toppings. How many ways can a customer select exactly 2 different toppings?

10. A sports team has 12 players. How many groups of 5 players can be selected?

Analysis and Challenge

11. A class contains 7 boys and 6 girls. How many committees containing exactly 2 boys and 3 girls can be formed?

12. A group contains 9 students. How many committees of 4 can be formed if one particular student must be included?

13. A group contains 10 students. How many committees of 3 can be formed if two particular students cannot both be selected?

14. An ice cream shop offers 5 flavours. How many different selections of 3 scoops are possible if flavours may repeat and order does not matter?

15. Explain how combinations are used in probability, and calculate the number of ways to select 5 different numbers from a set of 20.

Final Summary

Combinations provide a systematic method for counting selections in which the order of objects does not matter.

By using factorials and the combination formula, large numbers of possible groups can be calculated efficiently without listing every selection.

Understanding the difference between combinations and permutations is essential for choosing the correct counting method.

Combinations also connect to Pascal's Triangle, the Binomial Theorem, probability, statistics, and many practical applications involving group selection and decision-making.

4. Binomial Coefficients

Binomial Coefficients

Introduction to Binomial Coefficients

When expanding algebraic expressions such as (a + b)² or (x + 3)⁴, patterns appear in the numbers multiplying each term.

For example:

(a + b)² = a² + 2ab + b²

(a + b)³ = a³ + 3a²b + 3ab² + b³

(a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴

Notice the patterns in the coefficients:

• 1, 2, 1

• 1, 3, 3, 1

• 1, 4, 6, 4, 1

These numbers are called binomial coefficients.

Binomial coefficients connect algebraic expansion with combinations, factorials, Pascal's Triangle, and probability.

They allow complicated expressions to be expanded systematically without repeatedly multiplying brackets.

What Is a Binomial?

A binomial is an algebraic expression containing two terms.

Examples include:

• a + b

• x + 3

• 2x − 5

• 3p + 2q

• y − 4

A binomial expansion is the result of raising a binomial to a power and expressing it as a sum of terms.

For example:

(x + 2)² = (x + 2)(x + 2)

Expanding:

= x² + 2x + 2x + 4

= x² + 4x + 4

The coefficients are:

1, 4, 4

The first coefficient is 1 because the coefficient of x² is understood to be 1.

Binomial coefficients help determine these numerical factors efficiently.

Understanding Binomial Coefficients

A binomial coefficient represents the number of ways to choose a particular number of objects from a larger set when order does not matter.

The notation is:

C(n, r)

It is also written as nCr or read as "n choose r."

The formula is:

C(n, r) = n!/[r!(n − r)!]

where:

• n is the total number of objects.

• r is the number selected.

• ! represents factorial.

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

Factorial Notation

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

For example:

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

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

3! = 3 × 2 × 1 = 6

By definition:

0! = 1

Factorials provide a compact method for calculating combinations and binomial coefficients.

Calculating Binomial Coefficients

Worked Example: Calculate C(5, 2)

Step 1: Identify n and r.

n = 5

r = 2

Step 2: Substitute into the formula.

C(5, 2) = 5!/[2!(5 − 2)!]

Step 3: Simplify.

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

C(5, 2) = (5 × 4)/(2 × 1)

Step 4: Calculate.

C(5, 2) = 20/2

Final answer:

C(5, 2) = 10

This means there are 10 ways to select 2 objects from a group of 5 distinct objects.

Worked Example: Calculate C(8, 3)

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

= (8 × 7 × 6)/(3 × 2 × 1)

= 336/6

Final answer:

C(8, 3) = 56

Important Properties of Binomial Coefficients

Binomial coefficients have several useful properties.

Selecting No Objects

There is exactly one way to select nothing from a set.

C(n, 0) = 1

Selecting Every Object

There is exactly one way to select all available objects.

C(n, n) = 1

Selecting One Object

There are n ways to select one object from n available objects.

C(n, 1) = n

Symmetry Property

An important relationship is:

C(n, r) = C(n, n − r)

For example:

C(7, 2) = C(7, 5) = 21

This happens because choosing 2 objects determines exactly which 5 objects remain unselected.

Worked Example: Using Symmetry

Calculate:

C(12, 10)

Instead of expanding a large factorial expression, use symmetry:

C(12, 10) = C(12, 2)

= (12 × 11)/(2 × 1)

Final answer:

66

The symmetry property can make calculations much faster.

Pascal's Triangle

Pascal's Triangle is a triangular arrangement of numbers that displays binomial coefficients.

It is named after the French mathematician Blaise Pascal, although the pattern was studied by mathematicians in several cultures long before Pascal.

Each row begins and ends with 1.

Every interior number is obtained by adding the two numbers directly above it.

How Pascal's Triangle Is Constructed

Begin with:

1

The next row is:

1 1

To construct the following row, place 1 at each end and add the adjacent numbers above.

For example:

1 3 3 1

produces:

1 4 6 4 1

because:

1 + 3 = 4

3 + 3 = 6

3 + 1 = 4

This pattern continues indefinitely.

Interpreting Pascal's Triangle

Each row corresponds to the coefficients in a binomial expansion.

For example, the coefficients in:

(a + b)⁴

are:

1, 4, 6, 4, 1

Therefore:

(a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴

Pascal's Identity

The rule used to construct Pascal's Triangle can be written mathematically as:

C(n, r) = C(n − 1, r − 1) + C(n − 1, r)

For example:

C(5, 2) = C(4, 1) + C(4, 2)

= 4 + 6

= 10

This identity connects neighbouring rows of Pascal's Triangle.

Connecting Binomial Coefficients to Combinations

The connection between combinations and binomial expansions can be understood by examining how terms are formed.

Consider:

(a + b)³ = (a + b)(a + b)(a + b)

To produce a term containing a²b, we must choose b from exactly one of the three brackets and a from the other two.

There are three possible choices:

• Choose b from the first bracket.

• Choose b from the second bracket.

• Choose b from the third bracket.

Therefore, the coefficient of a²b is:

C(3, 1) = 3

Similarly, to produce ab², we must choose b from exactly two of the three brackets.

There are:

C(3, 2) = 3

possible choices.

Therefore:

(a + b)³ = a³ + 3a²b + 3ab² + b³

This explains why binomial coefficients appear naturally in algebraic expansions.

The Binomial Theorem

The Binomial Theorem provides a general method for expanding a binomial raised to a non-negative integer power.

The theorem states:

(a + b)ⁿ = C(n, 0)aⁿ + C(n, 1)aⁿ⁻¹b + C(n, 2)aⁿ⁻²b² + ... + C(n, n)bⁿ

An equivalent compact form is:

(a + b)ⁿ = Σ C(n, r)a^(n−r)bʳ

where the sum runs from r = 0 to n.

Understanding the Pattern

In the expansion:

• The exponent of a begins at n and decreases by 1.

• The exponent of b begins at 0 and increases by 1.

• The sum of the exponents in each term is n.

• The coefficients are C(n, 0), C(n, 1), ..., C(n, n).

• There are n + 1 terms before any like terms are combined.

For example:

(a + b)⁴ = a⁴ + 4a³b + 6a²b² + 4ab³ + b⁴

Notice that the sum of the exponents in every term is 4.

Visualizing the Binomial Theorem

The relationship between Pascal's Triangle and the Binomial Theorem can be explored by changing the power of the binomial.

For example, the fifth row of Pascal's Triangle provides the coefficients:

1, 5, 10, 10, 5, 1

These correspond to the expansion of (a + b)⁵.

Expanding Binomials Using Pascal's Triangle

For smaller powers, Pascal's Triangle provides a quick method.

Worked Example: Expand (x + 2)³

Step 1: Identify the power.

n = 3

Step 2: Find the coefficients.

From Pascal's Triangle:

1, 3, 3, 1

Step 3: Write the general expansion.

(x + 2)³ = x³ + 3x²(2) + 3x(2²) + 2³

Step 4: Simplify.

= x³ + 6x² + 12x + 8

Final answer:

(x + 2)³ = x³ + 6x² + 12x + 8

Worked Example: Expand (2x + 1)⁴

Step 1: Identify the coefficients.

For n = 4:

1, 4, 6, 4, 1

Step 2: Substitute into the expansion.

(2x + 1)⁴

= (2x)⁴ + 4(2x)³(1) + 6(2x)²(1²) + 4(2x)(1³) + 1⁴

Step 3: Simplify each term.

(2x)⁴ = 16x⁴

4(2x)³ = 32x³

6(2x)² = 24x²

4(2x) = 8x

Final answer:

(2x + 1)⁴ = 16x⁴ + 32x³ + 24x² + 8x + 1

Expanding Binomials with Negative Terms

The Binomial Theorem also works when one term is negative.

For example:

(a − b)³

can be treated as:

(a + (−b))³

Using the coefficients 1, 3, 3, 1:

(a − b)³ = a³ − 3a²b + 3ab² − b³

Notice that the signs alternate.

Worked Example: Expand (x − 3)⁴

Step 1: Identify the coefficients.

1, 4, 6, 4, 1

Step 2: Apply the theorem.

(x − 3)⁴

= x⁴ + 4x³(−3) + 6x²(−3)² + 4x(−3)³ + (−3)⁴

Step 3: Simplify.

= x⁴ − 12x³ + 54x² − 108x + 81

Final answer:

(x − 3)⁴ = x⁴ − 12x³ + 54x² − 108x + 81

Important Reminder

When raising a negative number to a power:

• An even power produces a positive result.

• An odd power produces a negative result.

For example:

(−3)² = 9

(−3)³ = −27

Careful attention to signs is essential.

Finding a Specific Term Without Expanding Everything

Sometimes a question asks for only one term in a large binomial expansion.

The general term in the expansion of (a + b)ⁿ is:

Tᵣ₊₁ = C(n, r)a^(n−r)bʳ

where r begins at 0.

This formula allows any term to be calculated directly.

Worked Example: Find the Fourth Term of (x + 2)⁶

Step 1: Identify the term number.

The fourth term corresponds to:

r = 3

Step 2: Apply the general term formula.

T₄ = C(6, 3)x^(6−3)(2³)

Step 3: Calculate the coefficient.

C(6, 3) = 20

Step 4: Simplify.

T₄ = 20 × x³ × 8

Final answer:

T₄ = 160x³

This method avoids expanding all seven terms.

Finding the Coefficient of a Particular Power

Another common problem involves finding the coefficient of a particular variable power.

Worked Example: Find the Coefficient of x³ in (2x + 1)⁵

The general term is:

Tᵣ₊₁ = C(5, r)(2x)^(5−r)(1)ʳ

We want the power of x to be 3.

Therefore:

5 − r = 3

r = 2

Substitute:

T₃ = C(5, 2)(2x)³

= 10 × 8x³

= 80x³

Final answer:

The coefficient of x³ is 80.

Worked Example: Find the Constant Term in (x + 2)⁵

A constant term contains no x.

In this expansion, the constant term occurs when the exponent of x is zero.

Therefore:

5 − r = 0

r = 5

The constant term is:

C(5, 5)x⁰2⁵

= 1 × 1 × 32

Final answer:

32

Patterns in Binomial Coefficients

Binomial coefficients display several interesting patterns.

Symmetry

Each row of Pascal's Triangle is symmetrical.

For example:

1, 5, 10, 10, 5, 1

This reflects:

C(n, r) = C(n, n − r)

Sum of the Coefficients

The sum of all binomial coefficients in row n is:

2ⁿ

For example, row 4 contains:

1, 4, 6, 4, 1

Their sum is:

1 + 4 + 6 + 4 + 1 = 16

Since:

2⁴ = 16

the property holds.

This follows from the Binomial Theorem by setting a = 1 and b = 1.

Alternating Sum

For n ≥ 1, the alternating sum of the coefficients is zero.

For example:

1 − 4 + 6 − 4 + 1 = 0

This follows from expanding:

(1 − 1)ⁿ = 0

Number of Terms

For a positive integer n, the expansion of (a + b)ⁿ contains n + 1 terms before simplification.

For example:

(a + b)⁵ contains 6 terms.

Applications in Probability

Binomial coefficients are important in probability because they count how many ways a particular number of successes can occur in repeated trials.

For example, suppose a fair coin is tossed four times.

How many different sequences contain exactly two heads?

We must choose which two of the four positions contain heads.

C(4, 2) = 6

The possible sequences are:

• HHTT

• HTHT

• HTTH

• THHT

• THTH

• TTHH

There are six sequences.

Since four fair coin tosses have:

2⁴ = 16

equally likely outcomes, the probability of exactly two heads is:

P = 6/16

P = 3/8 = 0.375

The Binomial Probability Formula

For n independent trials with the same probability p of success on each trial, the probability of exactly r successes is:

P(X = r) = C(n, r)pʳ(1 − p)^(n−r)

where:

• n is the number of trials.

• r is the number of successes.

• p is the probability of success.

• 1 − p is the probability of failure.

This formula is used in the binomial distribution.

Applications in Science and Technology

Binomial coefficients are useful in many areas beyond algebra.

Computer Science

Binomial coefficients appear in:

• Counting algorithms.

• Probability calculations.

• Data analysis.

• Recursive programming.

• Combinatorial optimization.

Genetics

In simplified probability models, binomial coefficients help calculate the likelihood of different numbers of offspring inheriting a particular characteristic.

For example, if an inherited trait has a probability of 0.5 in each independent case, binomial probabilities can model the number of offspring displaying that trait.

Statistics

Binomial coefficients are used when studying repeated experiments with two possible outcomes.

Examples include:

• Success or failure.

• Correct or incorrect.

• Pass or fail.

• Defective or non-defective.

Engineering

Binomial coefficients appear in mathematical models involving reliability, repeated independent events, and probabilistic systems.

A Systematic Strategy for Binomial Expansion Problems

When solving binomial expansion problems, follow these steps.

Identify the binomial and its power.

Determine the two terms and the exponent.

Find the coefficients.

Use Pascal's Triangle for smaller powers or the combination formula for larger powers.

Apply the exponent pattern.

The exponent of the first term decreases while the exponent of the second term increases.

Calculate each term carefully.

Include numerical coefficients, variables, powers, and signs.

Simplify the result.

Combine numerical factors and write the polynomial in descending powers when appropriate.

Check your answer.

Confirm that the powers in each term add to the original exponent and that the coefficients follow the expected pattern.

Common Mistakes

Confusing binomial coefficients with the final numerical coefficients

In (2x + 3)³, the binomial coefficients are 1, 3, 3, 1, but the final numerical coefficients are different because the terms contain factors of 2 and 3.

Using the wrong row of Pascal's Triangle

The expansion of (a + b)ⁿ uses row n when the first row is numbered 0.

Forgetting factorial notation

Remember that 5! means 5 × 4 × 3 × 2 × 1.

Incorrectly simplifying factorial expressions

Cancel common factorial factors carefully before multiplying large numbers.

Forgetting the exponent pattern

The exponent of the first term decreases while the exponent of the second term increases.

Making sign errors

Negative terms raised to odd powers remain negative.

Confusing term number with r

The general term Tᵣ₊₁ uses r beginning at zero.

Forgetting to include numerical factors

For example, (3x)² = 9x², not 3x².

Assuming every binomial expansion has positive coefficients

Expressions containing subtraction may produce alternating signs.

Expanding unnecessarily

If only one coefficient or term is required, use the general term formula instead of expanding the entire expression.

Key Terms

• Binomial: An algebraic expression containing two terms.

• Binomial Coefficient: A number representing the ways to choose r objects from n distinct objects without regard to order.

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

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

• Pascal's Triangle: A triangular arrangement of binomial coefficients.

• Binomial Theorem: A rule for expanding a binomial raised to a non-negative integer power.

• Binomial Expansion: The polynomial expression obtained by expanding a power of a binomial.

• Coefficient: A numerical factor multiplying a variable or algebraic term.

• Exponent: A number indicating how many times a base is multiplied by itself.

• General Term: A formula used to calculate a particular term in a sequence or expansion.

• Term Number: The position of a term within an expansion.

• Symmetry Property: The relationship C(n, r) = C(n, n − r).

• Pascal's Identity: The relationship C(n, r) = C(n − 1, r − 1) + C(n − 1, r).

• Polynomial: An algebraic expression consisting of terms with non-negative integer powers of variables.

• Constant Term: A term that does not contain a variable.

• Binomial Distribution: A probability distribution describing the number of successes in repeated independent trials with two possible outcomes.

• Probability: A measure of the likelihood of an event occurring.

• Combinatorics: The branch of mathematics concerned with counting arrangements and selections.

• Recursive Pattern: A pattern in which new values are determined from previous values.

• Algebraic Expansion: The process of rewriting a product or power as a sum of terms.

Key Takeaways

• Binomial coefficients represent the number of ways to choose objects from a larger set when order does not matter.

• Binomial coefficients are calculated using C(n, r) = n!/[r!(n − r)!].

• Factorials are essential for calculating combinations and binomial coefficients.

• Pascal's Triangle displays binomial coefficients in a triangular pattern.

• Each interior number in Pascal's Triangle is the sum of the two numbers above it.

• Row n of Pascal's Triangle gives the coefficients for (a + b)ⁿ.

• Binomial coefficients are symmetrical: C(n, r) = C(n, n − r).

• The sum of the coefficients in row n is 2ⁿ.

• The Binomial Theorem provides a systematic method for expanding powers of binomials.

• In a binomial expansion, the exponent of the first term decreases while the exponent of the second term increases.

• The general term formula allows individual terms or coefficients to be calculated without expanding the entire expression.

• Negative terms must be handled carefully because odd and even powers produce different signs.

• Binomial coefficients are closely connected to combinations, probability, statistics, and algebra.

• The Binomial Theorem is useful in mathematics, science, engineering, and computer science.

Check Your Understanding

Recall and Understanding

1. Define a binomial coefficient and explain its relationship to combinations.

2. State the formula for calculating C(n, r).

3. Explain how Pascal's Triangle is constructed.

4. Describe how Pascal's Triangle relates to the Binomial Theorem.

5. Explain the pattern of exponents in the expansion of (a + b)ⁿ.

Application

6. Calculate C(7, 3).

7. Write the coefficients in row 6 of Pascal's Triangle.

8. Expand (x + 2)³.

9. Expand (2x + 1)⁴.

10. Find the coefficient of x² in (x + 3)⁴.

Analysis and Challenge

11. Use the symmetry property to simplify C(15, 13).

12. Find the fourth term in the expansion of (2x + 3)⁶.

13. Expand (x − 2)⁵ and explain the pattern of signs.

14. A fair coin is tossed six times. Use binomial coefficients to determine the probability of obtaining exactly three heads.

15. Explain why the sum of the binomial coefficients in the expansion of (a + b)ⁿ equals 2ⁿ.

Final Summary

Binomial coefficients provide an important connection between combinations, Pascal's Triangle, and algebraic expansions.

By calculating binomial coefficients using factorials, students can determine the number of selections from a larger set and identify the coefficients in powers of binomial expressions.

Pascal's Triangle reveals patterns of symmetry, addition, and numerical relationships that make binomial expansions easier to understand.

The Binomial Theorem extends these ideas by providing a general method for expanding expressions such as (a + b)ⁿ and finding specific terms without performing lengthy multiplication.

These concepts form an important foundation for advanced algebra, probability, statistics, combinatorics, and mathematical modelling.

5. Advanced Counting Techniques

Advanced Counting Techniques

Introduction to Advanced Counting Techniques

Many counting problems are more complicated than simply arranging objects or selecting members of a group. Real-world situations often include restrictions, repeated objects, circular arrangements, or several conditions that must be satisfied simultaneously.

For example:

• How many ways can six people sit around a circular table?

• How many different arrangements can be made from the letters in BANANA?

• How many ways can students line up if two particular students must stand together?

• How many committees can be formed if certain members cannot serve together?

• How can we count arrangements without accidentally counting the same outcome more than once?

These problems require advanced counting techniques that combine permutations, combinations, the Fundamental Counting Principle, and logical reasoning.

The most important skill is not simply memorizing formulas. It is recognizing the structure of a counting problem and explaining why a particular method works.

Reviewing the Fundamental Counting Principles

Before studying more advanced techniques, it is important to understand the basic counting rules.

Multiplication Principle

When a process consists of several stages, multiply the number of choices available at each stage, provided those counts apply to every possible choice made earlier.

For example, a student has:

• 4 shirts

• 3 pairs of trousers

• 2 pairs of shoes

The total number of outfits is:

4 × 3 × 2 = 24

Addition Principle

When a choice can be made from separate, mutually exclusive categories, add the number of possibilities.

For example, a student may choose:

• One of 5 science activities

• Or one of 4 sports activities

If exactly one activity is selected:

5 + 4 = 9

Permutations

Permutations count arrangements where order matters.

For n distinct objects arranged in a line:

P = n!

For r objects selected and arranged from n distinct objects without repetition:

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

Combinations

Combinations count selections where order does not matter.

C(n, r) = n!/[r!(n − r)!]

These principles form the foundation for more challenging counting problems.

Understanding Restrictions

A restriction is a condition that limits which arrangements or selections are allowed.

Examples include:

• Two people must sit together.

• Two people cannot sit together.

• A particular person must occupy the first position.

• A number must be even.

• A password cannot contain repeated characters.

• A committee must contain a specified number of members from different groups.

Restrictions change the number of available outcomes.

A useful strategy is to identify the restriction before applying any counting formula.

Worked Example: A Fixed Position

Six students must stand in a line.

Alex must stand at the beginning.

How many arrangements are possible?

Step 1: Fix Alex in the first position.

There is only one choice for that position.

Step 2: Arrange the remaining five students.

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

Final answer:

120 arrangements

Without the restriction, there would be:

6! = 720 arrangements

The restriction reduces the number of possibilities.

The Block Method: Objects That Must Stay Together

The block method is useful when two or more objects must remain adjacent.

Instead of treating the objects separately, group them into a single block.

Worked Example: Two Students Together

Six students stand 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 block.

The objects are now:

• (Alex, Ben)

• Student C

• Student D

• Student E

• Student F

There are five objects to arrange.

Step 2: Arrange the five objects.

5! = 120

Step 3: Arrange Alex and Ben within their block.

They can stand as:

Alex–Ben

or:

Ben–Alex

There are 2! = 2 possibilities.

Step 4: Multiply.

120 × 2 = 240

Final answer:

240 arrangements

Worked Example: Three Students Together

Seven students stand in a line.

Three particular students must remain together.

Step 1: Treat the three students as one block.

There are now five objects:

• One block of three students

• Four other students

Step 2: Arrange the five objects.

5! = 120

Step 3: Arrange the three students within their block.

3! = 6

Step 4: Multiply.

120 × 6 = 720

Final answer:

720 arrangements

General Strategy

When k particular objects must remain together among n distinct objects:

1. Treat the k objects as one block.

2. Arrange the resulting n − k + 1 objects.

3. Arrange the k objects within the block.

The number of arrangements is:

(n − k + 1)! × k!

This formula applies when all objects are distinct and the k specified objects must form one consecutive block.

Complementary Counting: Objects That Must Not Stay Together

Sometimes it is easier to count the arrangements that are not allowed and subtract them from the total.

This method is called complementary counting.

Valid outcomes = Total outcomes − Invalid outcomes

Worked Example: Two Students Must Be Apart

Six students stand in a line.

Alex and Ben must not stand next to each other.

Step 1: Count all arrangements.

6! = 720

Step 2: Count arrangements where Alex and Ben are together.

Using the block method:

5! × 2! = 240

Step 3: Subtract.

720 − 240 = 480

Final answer:

480 arrangements

This method is much simpler than listing every arrangement in which the students are separated.

The Gap Method

The gap method is useful when certain objects must be separated from one another.

For example, suppose three boys and two girls must stand in a line, and the girls cannot stand next to each other.

Step 1: Arrange the three boys.

3! = 6 arrangements

Step 2: Identify the gaps.

For a particular order of boys:

_ B _ B _ B _

There are four possible gaps where girls may stand.

Step 3: Choose two different gaps.

C(4, 2) = 6

Step 4: Arrange the two girls.

2! = 2

Step 5: Multiply.

6 × 6 × 2 = 72

Final answer:

72 arrangements

The gap method is especially useful for arranging people, letters, or objects that must not appear consecutively.

Circular Permutations

In a linear arrangement, positions are fixed from left to right.

In a circular arrangement, there is no natural starting position.

For example, consider four people sitting around a round table.

Rotating everyone one seat clockwise does not change who sits beside whom.

Therefore, rotations are usually considered the same arrangement.

Formula for Circular Permutations

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

P = (n − 1)!

Why Does the Formula Work?

In a straight line, n distinct objects can be arranged in:

n! ways

However, each circular arrangement can be represented by n different linear sequences, depending on which object is listed first.

Therefore:

n!/n = (n − 1)!

An alternative explanation is to fix one person in a reference position and arrange the remaining n − 1 people.

Worked Example: Seating Six People Around a Table

Six people sit around a circular table.

How many different seating arrangements are possible?

Step 1: Identify n.

n = 6

Step 2: Apply the circular permutation formula.

P = (6 − 1)!

P = 5!

Final answer:

120 arrangements

Circular Arrangements Versus Linear Arrangements

Circular arrangements have fewer distinct outcomes because rotations are treated as equivalent.

Circular Arrangements with Restrictions

Circular permutation problems may include conditions such as two people sitting together or opposite one another.

Worked Example: Two People Must Sit Together

Six people sit around a circular table.

Alex and Ben must sit next to each other.

Step 1: Treat Alex and Ben as one block.

There are now five objects around the circle:

• The Alex–Ben block

• Four other people

Step 2: Arrange the five objects circularly.

(5 − 1)! = 4! = 24

Step 3: Arrange Alex and Ben within their block.

2! = 2

Step 4: Multiply.

24 × 2 = 48

Final answer:

48 arrangements

Worked Example: Two People Must Not Sit Together

Six people sit around a circular table.

Alex and Ben must not sit next to each other.

Step 1: Count all circular arrangements.

5! = 120

Step 2: Count arrangements where they sit together.

4! × 2! = 48

Step 3: Subtract.

120 − 48 = 72

Final answer:

72 arrangements

Important Note About Reflections

For ordinary round-table seating, clockwise and counterclockwise arrangements are usually considered different unless one can be obtained from the other by rotation.

However, for necklaces or bracelets that can be turned over, mirror-image arrangements may also be considered equivalent.

These problems require additional care because the simple formula (n − 1)! may no longer apply.

Circular Arrangements with Opposite Positions

Some circular problems involve people sitting directly opposite one another.

This requires an even number of equally spaced seats.

Worked Example: Two People Must Sit Opposite

Six people sit around a circular table.

Alex and Ben must sit opposite each other.

Step 1: Fix Alex's position.

Fixing Alex removes rotational duplicates.

Step 2: Place Ben opposite Alex.

There is exactly one available opposite seat.

Step 3: Arrange the remaining four people.

4! = 24

Final answer:

24 arrangements

The fixed-position method is especially useful when circular arrangements contain positional restrictions.

Permutations Involving Repeated Objects

Some arrangements contain objects that are identical.

For example, the word LEVEL 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 swapping identical letters does not create a new arrangement.

To correct for repeated objects, divide by the factorials of their repetition counts.

Formula for Repeated Objects

If n objects contain groups of identical objects with repetition counts a, b, c, ...:

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

The repetition counts must add to n.

Worked Example: Arranging BANANA

The word BANANA contains six letters.

• A appears three times.

• N appears twice.

• B appears once.

Step 1: Count the total letters.

n = 6

Step 2: Identify repetitions.

A: 3

N: 2

Step 3: Apply the formula.

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

Step 4: Calculate.

P = 720/(6 × 2)

P = 720/12

Final answer:

60 distinct arrangements

Worked Example: Arranging MISSISSIPPI

The word MISSISSIPPI contains 11 letters.

The repetition counts are:

• M: 1

• I: 4

• S: 4

• P: 2

The number of distinct arrangements is:

P = 11!/(4! × 4! × 2!)

P = 39,916,800/(24 × 24 × 2)

P = 39,916,800/1,152

Final answer:

34,650 distinct arrangements

This example demonstrates why the repeated-object formula is much more efficient than listing outcomes.

Repeated Objects with Restrictions

Repeated-object problems become more challenging when certain letters must appear together or apart.

Worked Example: All Vowels Together

How many distinct arrangements of the word BANANA have all three A's together?

Step 1: Treat AAA as one block.

The objects are now:

• AAA

• B

• N

• N

There are four objects, with N repeated twice.

Step 2: Apply the repeated-object formula.

P = 4!/2!

P = 24/2

Final answer:

12 distinct arrangements

Because all three A's are identical, rearranging them within the block does not create additional outcomes.

Worked Example: Two Identical Letters Must Not Be Together

Consider the word LEVEL.

How many arrangements have the two Ls separated?

Step 1: Count all arrangements.

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

P = 30

Step 2: Count arrangements where the Ls are together.

Treat LL as one block.

The objects become:

• LL

• E

• E

• V

There are four objects, with E repeated twice.

P = 4!/2!

P = 12

Step 3: Subtract.

30 − 12 = 18

Final answer:

18 arrangements

Combining Permutations and Combinations

Some problems require selecting objects first and then arranging them.

This combines combinations with permutations.

Worked Example: Selecting and Arranging Students

A class contains 10 students.

Four students are selected to give presentations.

How many different presentation schedules are possible?

Method A: Direct Permutation

P(10, 4) = 10 × 9 × 8 × 7

P(10, 4) = 5,040

Method B: Combination Followed by Permutation

First select four students:

C(10, 4) = 210

Then arrange those four students:

4! = 24

Multiply:

210 × 24 = 5,040

Both methods give the same result.

This illustrates the relationship:

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

Counting Problems with Multiple Cases

Some restrictions require dividing a problem into separate cases.

Worked Example: Forming a Committee

A school has:

• 5 boys

• 4 girls

A committee of 3 students must contain at least one girl.

How many committees are possible?

Method A: Count Separate Cases

Case 1: One girl and two boys

C(4, 1) × C(5, 2)

= 4 × 10

= 40

Case 2: Two girls and one boy

C(4, 2) × C(5, 1)

= 6 × 5

= 30

Case 3: Three girls

C(4, 3) = 4

Add the cases:

40 + 30 + 4 = 74

Final answer: 74 committees

Method B: Complementary Counting

Count all committees:

C(9, 3) = 84

Subtract committees containing only boys:

C(5, 3) = 10

84 − 10 = 74

Both methods give the same answer.

Why Are Both Methods Valid?

The first method divides the valid outcomes into mutually exclusive cases.

The second method counts all possible outcomes and removes the invalid ones.

Choosing the simpler method can save considerable time.

The Inclusion–Exclusion Principle

Sometimes counting categories overlap.

If we simply add their sizes, outcomes belonging to both categories are counted twice.

The Inclusion–Exclusion Principle corrects this problem.

For two sets A and B:

|A ∪ B| = |A| + |B| − |A ∩ B|

where:

• |A| is the number of outcomes in A.

• |B| is the number of outcomes in B.

• |A ∩ B| is the number of outcomes in both.

• |A ∪ B| is the number of outcomes in either or both.

Worked Example: Students Studying Languages

In a class:

• 18 students study French.

• 15 students study Spanish.

• 7 students study both languages.

How many students study at least one of these languages?

18 + 15 − 7 = 26

Final answer:

26 students

The overlap must be subtracted once because it was counted in both original groups.

Advanced Digit Arrangement Problems

Digit problems often combine permutations with restrictions.

Worked Example: Four-Digit Even Numbers

How many four-digit even numbers can be formed using the digits 0–9 without repetition?

An even number must end in:

0, 2, 4, 6, or 8

However, the first digit cannot be zero.

We divide the problem into two cases.

Case 1: The Last Digit Is Zero

Last digit: 1 choice

First digit: 9 choices

Second digit: 8 choices

Third digit: 7 choices

Total:

1 × 9 × 8 × 7 = 504

Case 2: The Last Digit Is 2, 4, 6, or 8

Last digit: 4 choices

First digit: 8 choices (nonzero and different from the last digit)

Second digit: 8 choices

Third digit: 7 choices

Total:

4 × 8 × 8 × 7 = 1,792

Combine the Cases

504 + 1,792 = 2,296

Final answer:

2,296 four-digit even numbers

This problem demonstrates why it is important to identify restrictions before multiplying.

Counting Arrangements with Identical Groups

Some problems involve selecting or arranging groups rather than individual objects.

Worked Example: Distributing Identical Objects

A teacher has five identical pencils to distribute among three students.

Each student may receive zero or more pencils.

How many different distributions are possible?

This is a combinations with repetition problem.

The formula is:

C(n + r − 1, r)

where:

• n is the number of recipients or categories.

• r is the number of identical objects.

Here:

n = 3

r = 5

C(3 + 5 − 1, 5)

= C(7, 5)

= 21

Final answer:

21 distributions

This method is often called stars and bars.

The five stars represent the pencils, while the two bars divide them among the three students.

There are seven positions containing five stars and two bars.

Choosing the positions of the bars gives:

C(7, 2) = 21

Justifying Counting Methods

In advanced counting problems, obtaining the correct numerical answer is only part of the task.

A complete mathematical solution should explain why the method counts every valid outcome exactly once.

A strong justification includes the following ideas.

Identify What Is Being Counted

Clearly define the objects, arrangements, or selections.

For example:

"We are counting distinct arrangements of six students in a line."

Explain Why Order Matters or Does Not Matter

This determines whether permutations or combinations are appropriate.

For example:

"Order matters because changing the students' positions creates a different arrangement."

Explain the Restrictions

Describe how the restrictions affect the available choices.

For example:

"Because Alex and Ben must stand together, they are treated as one block."

Explain the Counting Operation

State why multiplication, addition, or subtraction is used.

For example:

"The arrangements of the blocks are multiplied by the arrangements within the block because each block arrangement can be paired with either internal order."

Check for Double-Counting

Make sure the same outcome is not counted more than once.

This is especially important when:

• Objects are identical.

• Circular rotations are equivalent.

• Different cases overlap.

• Multiple restrictions apply.

Comparing Advanced Counting Strategies

The best method depends on the structure of the problem.

Real-World Applications

Scheduling

Schools and businesses use counting methods to calculate possible schedules.

Restrictions may include:

• Certain activities must occur consecutively.

• Some activities cannot overlap.

• Particular events must occur first or last.

• Certain tasks must follow others.

Seating Arrangements

Event organizers may need to arrange guests while satisfying conditions such as:

• Family members sitting together.

• Guests being separated.

• Particular guests sitting opposite one another.

• Assigned seats at circular tables.

Passwords and Security

Password systems use counting principles to estimate the number of possible codes.

Restrictions may include:

• At least one number.

• At least one uppercase letter.

• No repeated characters.

• A minimum password length.

Computer Science

Advanced counting methods are used in:

• Algorithm design.

• Data organization.

• Search problems.

• Network analysis.

• Cryptography.

• Resource allocation.

Genetics and Biology

Counting methods help scientists investigate possible genetic combinations, experimental arrangements, and distributions of biological characteristics.

Common Mistakes

Using n! for circular arrangements

When rotations are equivalent, use (n − 1)! rather than n!.

Forgetting internal arrangements in the block method

Objects within a block may still be arranged in several ways.

Treating identical objects as distinct

Repeated objects must be accounted for to avoid overcounting.

Using complementary counting incorrectly

The invalid outcomes being subtracted must correspond exactly to the restriction.

Adding overlapping cases without correction

Use Inclusion–Exclusion when cases overlap.

Confusing selections with arrangements

Use combinations when order does not matter and permutations when order matters.

Ignoring zero restrictions in digit problems

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

Assuming every circular arrangement has the same rules

Some circular problems treat reflections as equivalent, while others do not.

Failing to justify the method

A correct answer should explain why the chosen method counts the intended outcomes.

Counting the same outcome more than once

Double-counting is a major source of error in advanced counting problems.

Key Terms

• Advanced Counting Techniques: Mathematical methods used to count arrangements and selections involving restrictions or complicated conditions.

• Restriction: A condition that limits which outcomes are allowed.

• Fundamental Counting Principle: A rule for multiplying the number of choices across stages.

• Addition Principle: A rule for adding the numbers of outcomes from mutually exclusive cases.

• Permutation: An arrangement in which order matters.

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

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

• Circular Permutation: An arrangement of objects around a circle.

• Rotational Equivalence: The condition that arrangements differing only by rotation are considered identical.

• Reflection: A reversal of orientation that may or may not create a distinct circular arrangement.

• Block Method: A strategy that treats objects required to remain together as a single unit.

• Gap Method: A strategy that places objects into available gaps to prevent adjacency.

• Complementary Counting: A method that subtracts invalid outcomes from the total.

• Repeated Objects: Objects that are identical and cannot be distinguished from one another.

• Multiset: A collection in which identical elements may occur more than once.

• Inclusion–Exclusion Principle: A method for counting overlapping sets without double-counting.

• Mutually Exclusive Cases: Cases that cannot occur simultaneously.

• Stars and Bars: A method for counting distributions of identical objects among distinct categories.

• Double-Counting: Counting the same outcome more than once.

• Justification: A mathematical explanation showing why a counting method is valid.

• Combinatorics: The branch of mathematics concerned with counting arrangements and selections.

• Sample Space: The set of all possible outcomes in an experiment or counting situation.

Key Takeaways

• Advanced counting problems often require several counting principles to be combined.

• Restrictions must be identified before selecting a counting method.

• The block method is useful when objects must remain together.

• Complementary counting is useful when it is easier to count invalid outcomes than valid ones.

• The gap method helps count arrangements where particular objects must remain separated.

• Circular permutations usually use (n − 1)! when rotations are considered equivalent.

• Circular arrangements involving fixed or opposite positions may require additional reasoning.

• Repeated objects reduce the number of distinct arrangements.

• The repeated-object permutation formula divides by the factorials of identical-object counts.

• Selection followed by arrangement can be counted using combinations multiplied by permutations.

• Complex restrictions may require dividing problems into mutually exclusive cases.

• Inclusion–Exclusion prevents double-counting when cases overlap.

• Stars and bars counts distributions of identical objects among distinct categories.

• Advanced counting methods are useful in scheduling, seating, passwords, computer science, and scientific research.

• A complete solution should justify why every valid outcome is counted exactly once.

Check Your Understanding

Recall and Understanding

1. Explain the difference between a linear permutation and a circular permutation.

2. Why is the formula for circular permutations usually (n − 1)!?

3. Describe the block method and explain when it is useful.

4. What is complementary counting?

5. Explain why repeated objects require a modified permutation formula.

Application

6. Seven people sit around a circular table. How many distinct seating arrangements are possible?

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

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

9. Eight students must give presentations. How many schedules are possible if one particular student must present first?

10. How many different committees of 3 students can be formed from a group of 10 students if one particular student must be included?

Analysis and Challenge

11. Seven students stand in a line. How many arrangements are possible if two particular students must not stand next to each other?

12. Eight people sit around a circular table. How many arrangements are possible if two particular people must sit together?

13. How many distinct arrangements can be made using the letters in MISSISSIPPI?

14. How many four-digit even numbers can be formed using digits 0–9 without repetition?

15. A class contains 6 boys and 5 girls. A committee of 4 students must contain at least 2 girls. Calculate the number of possible committees and justify your method.

Final Summary

Advanced counting techniques extend the Fundamental Counting Principle, permutations, and combinations to situations involving restrictions, circular arrangements, repeated objects, and overlapping conditions.

By using methods such as grouping, complementary counting, gap counting, Inclusion–Exclusion, and stars and bars, complicated counting problems can be solved systematically.

The most important part of advanced counting is understanding the structure of the problem and choosing a method that counts every valid outcome exactly once.

These techniques provide a foundation for probability, statistics, combinatorics, computer science, optimization, and many practical problems involving arrangements and selections.