Mathematics (9709) | Permutations and combinations

AS & A Level Mathematics 9709 (Paper 5: Probability & Statistics 1)

Chapter 5.2: Permutations and Combinations

Welcome to one of the most exciting (and sometimes tricky!) parts of statistics: figuring out how many different ways things can happen. Permutations and Combinations are essential tools used whenever you need to count arrangements or selections.

Don't worry if the formulas look complicated at first! The key is learning to ask the right question: Does the order matter? Once you answer that, the rest is just calculation. Mastering this chapter provides the foundation for solving more complex probability problems later on.

---

Part 1: The Essential Prerequisite – Factorials (n!)

Before we dive into arrangements, we need the concept of the Factorial.

What is a Factorial?

The factorial of a non-negative integer \(n\), denoted by \(n!\), is the product of all positive integers less than or equal to \(n\). It simply represents the total number of ways to arrange \(n\) distinct items in a line.

Formula:
\(n! = n \times (n-1) \times (n-2) \times \dots \times 1\)

Example: If you have 4 friends (A, B, C, D) and 4 seats, how many ways can they be seated?

• Seat 1: 4 choices
• Seat 2: 3 choices left
• Seat 3: 2 choices left
• Seat 4: 1 choice left

Total arrangements = \(4! = 4 \times 3 \times 2 \times 1 = 24\) ways.

Key Point to Remember:
The value of \(0!\) is defined as 1. (It sounds strange, but think of it as only having one way to arrange zero items—by doing nothing!)

Key Takeaway: Factorials tell us the number of ways to arrange ALL distinct items.

---

Part 2: Permutations (Order Matters!)

A Permutation is an arrangement of items where the order or position is important.

The Order Test for Permutations (P): If changing the position of two chosen items results in a new, different outcome, it is a permutation.
Analogy: Choosing a password. "CAT" is different from "ACT." Order matters!

A. Linear Arrangements of Distinct Items

This occurs when you are selecting \(r\) items from a set of \(n\) items, and arranging them in a line.

Notation: \(_nP_r\) or \(P(n, r)\)
This means "the number of permutations of \(n\) items taken \(r\) at a time."

Formula:
\(_nP_r = \frac{n!}{(n-r)!}\)

Step-by-step Example:
A race has 10 runners. How many ways can the gold, silver, and bronze medals be awarded? (Here, \(n=10\), \(r=3\)).

1. Identify that order matters (Gold, Silver, Bronze is different from Silver, Gold, Bronze). Use Permutation.
2. Apply the formula: \(_ {10} P_3 = \frac{10!}{(10-3)!} = \frac{10!}{7!}\)
3. Calculate: \(\frac{10 \times 9 \times 8 \times 7!}{7!} = 10 \times 9 \times 8 = 720\) ways.

B. Permutations with Repetition (Identical Items)

Sometimes, the items you are arranging are not all distinct (e.g., the letters in the word 'BOOK' have two O's). If we simply use \(n!\), we count arrangements that look identical.

To correct for identical items, we must divide the total number of arrangements by the factorials of the number of times each repeated item appears.

Formula for arrangements with repetitions:
If you have \(n\) total objects, with \(r_1\) identical objects of type 1, \(r_2\) identical objects of type 2, and so on, the number of distinct arrangements is:

\[\frac{n!}{r_1! r_2! \dots r_k!}\]

Example (Syllabus scope):
Find the number of distinct arrangements of the letters in the word NEEDLESS.

1. Total letters \(n=8\).
2. Count repetitions: E appears 2 times (\(r_E = 2\)), S appears 2 times (\(r_S = 2\)), N, D, L appear 1 time.
3. Calculation: \(\frac{8!}{2! \times 2!} = \frac{40320}{2 \times 2} = 10080\) distinct arrangements.

C. Permutations with Restrictions (The "Glue" Method)

When items must be kept together (e.g., people must sit next to each other), we use the "glue" or "unit" method.

Method:

1. "Glue" the restricted items together, treating them as a single unit.
2. Calculate the number of ways to arrange the total items, including this new unit.
3. Calculate the number of ways the restricted items can arrange themselves within their unit.
4. Multiply the results from step 2 and step 3.

Example:
4 boys (B) and 2 girls (G) are lining up. How many arrangements are there if the two girls must stand next to each other?

Unit = (GG). Total items to arrange = (Unit) + B1 + B2 + B3 + B4 = 5 items.

1. Arrangement of the 5 items: \(5! = 120\) ways.
2. Arrangement within the unit (GG): \(2! = 2\) ways (G1G2 or G2G1).
3. Total arrangements: \(120 \times 2 = 240\) ways.

Restriction (Must NOT be next to each other):
If the 2 girls must NOT stand next to each other, you calculate:
Total Arrangements (No restriction) - Arrangements (Girls are together).

• Total arrangements (6 people): \(6! = 720\)
• Arrangements where girls are together (calculated above): 240
• Arrangements where girls are NOT together: \(720 - 240 = 480\) ways.

---

Part 3: Combinations (Order Doesn't Matter!)

A Combination is a selection of items where the order of selection is irrelevant.

The Order Test for Combinations (C): If changing the position of two chosen items results in the same outcome, it is a combination.
Analogy: Choosing a team/committee. A committee of {John, Mary} is the exact same committee as {Mary, John}. Order does not matter!

A. Selections of Distinct Items

This occurs when you are selecting \(r\) items from a set of \(n\) items, but you are not arranging them.

Notation: \(_nC_r\) or \(\binom{n}{r}\)
This means "the number of combinations of \(n\) items taken \(r\) at a time."

Formula:
\(_nC_r = \frac{n!}{r!(n-r)!}\)

Did you know? The combination formula is simply the permutation formula divided by \(r!\). We divide by \(r!\) because there are \(r!\) ways to arrange the selected items, and since order doesn't matter in combinations, we eliminate those redundant arrangements.

Step-by-step Example:
You have 10 friends and you need to choose 3 to go to the cinema. How many ways can you choose the group? (Here, \(n=10\), \(r=3\)).

1. Identify that order does not matter (A, B, C is the same group as C, B, A). Use Combination.
2. Apply the formula: \(_ {10} C_3 = \frac{10!}{3!(10-3)!} = \frac{10!}{3! 7!}\)
3. Calculate: \(\frac{10 \times 9 \times 8}{3 \times 2 \times 1} = 120\) ways.

Important Property of Combinations:
Choosing 3 items from 10 is the same as choosing 7 items to leave behind (reject).
\(_ {10} C_3 = \_ {10} C_7\). This symmetry can sometimes simplify calculations.

Key Takeaway: Combinations are about selecting a subgroup where position is irrelevant.

---

Part 4: Solving Complex Problems (P & C Together)

Many exam questions require you to mix permutations and combinations, often involving different groups or restrictions.

A. Problems Involving Different Groups (The 'AND' Rule)

If a selection process requires choosing m items from group A AND k items from group B, you calculate the selection possibilities for each group separately and then multiply the results.

Example:
A committee of 5 people must be formed from a group of 8 men and 6 women, such that it contains exactly 3 men and 2 women.

Ways to choose 3 men from 8: \(_8C_3 = 56\)
Ways to choose 2 women from 6: \(_6C_2 = 15\)
Total ways = (Ways to choose men) \(\times\) (Ways to choose women)
Total ways = \(56 \times 15 = 840\)

B. Problems Involving Multiple Cases (The 'OR' Rule)

If a scenario can be satisfied by Case 1 OR Case 2 (where the cases are mutually exclusive—they cannot happen at the same time), you add the results.

Example:
Using the group above (8 men, 6 women), how many committees of 5 can be formed with at least 4 men?

"At least 4 men" means: Case 1 (4 Men AND 1 Woman) OR Case 2 (5 Men AND 0 Women).

Case 1: 4 Men and 1 Woman
\(_8C_4 \times \_6C_1 = 70 \times 6 = 420\)

Case 2: 5 Men and 0 Women
\(_8C_5 \times \_6C_0 = 56 \times 1 = 56\)

Total ways = \(420 + 56 = 476\)

C. The Arrangement-after-Selection Rule

If a question asks you to first select a subgroup and then arrange that subgroup, you must combine C and P.

Step 1 (Selection): Use Combination (\(_nC_r\)) to choose the items.
Step 2 (Arrangement): Use Factorial (\(r!\)) to arrange the chosen items.

Note: Mathematically, \(_nC_r \times r! = \_nP_r\). You are essentially performing a permutation. However, understanding the two separate steps is vital when dealing with complex constraints.

Example:
From 7 available paintings, 3 are selected and hung on a wall. How many different displays are possible?

1. Selection: \(_7C_3 = 35\) ways to choose the 3 paintings.
2. Arrangement: \(3! = 6\) ways to arrange those 3 chosen paintings.
3. Total displays: \(35 \times 6 = 210\). (Or simply \(_7P_3 = 210\)).

---

Common Mistakes to Avoid

1. Forgetting the Order Test: Always ask: If I swap two items, is the result different? If YES, use P. If NO, use C.

2. Misapplying the 'Glue' Method: If items A and B must be together, don't forget the internal arrangement: (AB) and (BA) are different internal arrangements, so you must multiply by \(2!\).

3. Ignoring Identical Items: If you are arranging letters, check for repeats and remember to divide by the factorials of the repetitions.

4. Overcounting in 'At Least' Problems: When calculating "at least X," ensure your different cases (Case 1, Case 2, etc.) do not overlap. Using the "OR" rule (addition) only works for mutually exclusive cases.

Remember, practice is key! Once you can correctly identify whether a problem is P or C, the calculations become routine. Good luck!