Permutations and combinations

1. Overview

Permutations and combinations are fundamental counting techniques used to determine the number of possible arrangements and selections of objects from a set. This topic is crucial for IGCSE Additional Mathematics (0606) as it appears frequently in both Paper 1 and Paper 2, often in the context of probability problems. Mastering these concepts allows you to efficiently calculate possibilities in various scenarios, ranging from simple arrangements to complex selections with constraints. The key is understanding when order matters (permutations) and when it doesn't (combinations), and applying the appropriate formulas.

Key Definitions

• Factorial ($n!$): The product of all positive integers from $n$ down to 1. Note that $0! = 1$ by definition.
• Permutation ($^nP_r$): An ordered arrangement of $r$ objects taken from a set of $n$ distinct objects. In permutations, the order of items matters (e.g., ABC is different from CBA).
• Combination ($^nC_r$): A selection of $r$ objects taken from a set of $n$ distinct objects where the order does not matter (e.g., ABC is the same as CBA).
• Arrangement: Another word for permutation; implies the sequence is important.
• Selection: Another word for combination; implies only the membership of the group is important.

---

Core Content

The Factorial Notation

To arrange $n$ distinct objects in a straight line, there are $n!$ ways.

• $n! = n \times (n-1) \times (n-2) \times \dots \times 3 \times 2 \times 1$
• In Paper 1, you must be able to simplify algebraic fractions involving factorials. For example: $\frac{(n+1)!}{(n-1)!} = \frac{(n+1)(n)(n-1)!}{(n-1)!} = n^2 + n$.

Permutations (Order Matters)

Used when objects are being placed in specific positions (e.g., first, second, third; or roles like President and Secretary).

Formula: $^nP_r = \frac{n!}{(n-r)!}$ (This formula is given on the 0606 formula sheet)

• Case 1: No restrictions: Simple application of formula.
• Case 2: Specific positions: If a certain item must be at the end, fill that position first, then arrange the remaining $(n-1)$ items.
• Case 3: Items together: Treat the "together" items as one single block, calculate permutations of the blocks, then multiply by the internal permutations of the items within the block.

Combinations (Order Does Not Matter)

Used when we are just forming a group or a team.

Formula: $^nC_r = \frac{n!}{r!(n-r)!}$ (This formula is given on the 0606 formula sheet)

• Note that $^nC_r$ is also written as $\binom{n}{r}$.

Worked Example 1: Algebraic Manipulation (Paper 1 Style)

Question: Show that $^nC_2 + \space ^nC_1 = \frac{n(n+1)}{2}$.

Working:

1. State the formula for each term: $^nC_2 = \frac{n!}{2!(n-2)!}$ and $^nC_1 = \frac{n!}{1!(n-1)!}$ Definition of combination
2. Expand factorials to allow simplification: $\frac{n!}{2!(n-2)!} + \frac{n!}{1!(n-1)!} = \frac{n(n-1)(n-2)!}{2(n-2)!} + \frac{n(n-1)!}{(n-1)!}$ Expand $n!$ to $(n)(n-1)(n-2)!$ and $(n)(n-1)!$ respectively
3. Simplify terms: $\frac{n(n-1)}{2} + n$ Cancel out the common factorial terms
4. Find a common denominator: $\frac{n(n-1)}{2} + \frac{2n}{2} = \frac{n^2 - n + 2n}{2}$ Multiply $n$ by $\frac{2}{2}$ to get a common denominator
5. Final simplification: $\frac{n^2 + n}{2} = \frac{n(n+1)}{2}$ Simplify the numerator

Therefore, $^nC_2 + \space ^nC_1 = \frac{n(n+1)}{2}$ [Q.E.D]

Worked Example 2: Permutations with Restrictions

Question: Find the number of different 5-letter arrangements that can be made from the letters in the word $DAUGHTER$ if: (a) The arrangement must begin with a consonant. (b) The letters $G, H,$ and $T$ must be together in that order.

Working: (a) Total letters = 8. Consonants = ${D, G, H, T, R}$ (5 total).

• Step 1: Choose the first letter (5 options).
• Step 2: Fill the remaining 4 spots from the 7 remaining letters ($^7P_4$).
• Total = $5 \times \frac{7!}{(7-4)!} = 5 \times \frac{7!}{3!} = 5 \times (7 \times 6 \times 5 \times 4) = 5 \times 840 = 4200$.

Therefore, the number of arrangements is $\bf{4200}$.

(b) Treat $(GHT)$ as 1 single block.

• Remaining letters: $D, A, U, E, R$ (5 letters).
• Total items to arrange: 1 block + 5 letters = 6 items.
• Since $GHT$ must be in that specific order, there is only 1 way to arrange the block internally.
• Total = $6! \times 1 = 720$.

Therefore, the number of arrangements is $\bf{720}$.

Worked Example 3: Combinations (Selection)

Question: A committee of 5 is to be chosen from 6 men and 8 women. How many ways can this be done if the committee must contain at least 3 women?

Working: We must consider the three mutually exclusive cases:

1. 3 Women and 2 Men: $^8C_3 \times \space ^6C_2 = \frac{8!}{3!5!} \times \frac{6!}{2!4!} = 56 \times 15 = 840$ Choose 3 women out of 8 AND 2 men out of 6
2. 4 Women and 1 Man: $^8C_4 \times \space ^6C_1 = \frac{8!}{4!4!} \times \frac{6!}{1!5!} = 70 \times 6 = 420$ Choose 4 women out of 8 AND 1 man out of 6
3. 5 Women and 0 Men: $^8C_5 \times \space ^6C_0 = \frac{8!}{5!3!} \times \frac{6!}{0!6!} = 56 \times 1 = 56$ Choose 5 women out of 8 AND 0 men out of 6

• Total ways = $840 + 420 + 56 = 1316$. Sum the mutually exclusive cases

Therefore, the total number of ways is $\bf{1316}$.

Worked Example 4: Permutation with Identical Objects

Question: How many different arrangements can be made using all the letters of the word "MISSISSIPPI"?

Working:

1. Count the total number of letters: There are 11 letters in "MISSISSIPPI". Identify the total number of objects to arrange
2. Count the repetitions of each letter:
   • I appears 4 times.
   • S appears 4 times.
   • P appears 2 times.
   • M appears 1 time. Identify the number of repetitions for each distinct object
3. Apply the formula for permutations with repetitions: $\frac{11!}{4!4!2!1!} = \frac{39916800}{(24)(24)(2)(1)} = \frac{39916800}{1152} = 34650$ Divide the total factorial by the product of the factorials of the repetitions

Therefore, the number of different arrangements is $\bf{34650}$.

Worked Example 5: Combination with Restrictions (Paper 2 Style)

Question: A bag contains 7 red balls and 5 blue balls. A sample of 4 balls is selected at random. Find the probability that the sample contains exactly 2 red balls.

Working:

1. Calculate the total number of ways to select 4 balls from the 12 balls: $^{12}C_4 = \frac{12!}{4!8!} = 495$ This is the denominator of the probability fraction
2. Calculate the number of ways to select 2 red balls from the 7 red balls: $^7C_2 = \frac{7!}{2!5!} = 21$ Choose 2 red balls from the 7 available
3. Calculate the number of ways to select 2 blue balls from the 5 blue balls: $^5C_2 = \frac{5!}{2!3!} = 10$ Choose 2 blue balls from the 5 available
4. Calculate the number of ways to select 2 red balls AND 2 blue balls: $^7C_2 \times \space ^5C_2 = 21 \times 10 = 210$ Multiply the combinations together
5. Calculate the probability of selecting exactly 2 red balls: $P(\text{2 red balls}) = \frac{^{7}C_2 \times \space ^{5}C_2}{^{12}C_4} = \frac{210}{495} = \frac{14}{33}$ Divide the number of successful outcomes by the total number of outcomes

Therefore, the probability is $\bf{\frac{14}{33}}$.

---

Extended Content (Extended Only)

Additional Mathematics is a single-tier syllabus — all content above applies to all students.

---

Key Equations

• Factorial: $n! = n(n-1)(n-2)\dots 1$
• Permutations: $^nP_r = \frac{n!}{(n-r)!}$ ($n$ = total items, $r$ = items arranged) (Given on formula sheet)
• Combinations: $^nC_r = \frac{n!}{r!(n-r)!}$ ($n$ = total items, $r$ = items selected) (Given on formula sheet)
• Symmetry Property: $^nC_r = \space ^nC_{n-r}$ (useful for simplifying calculations)

---

Common Mistakes to Avoid

• ❌ Wrong: Using trial and improvement on a calculator to solve for $n$ in an equation like $^nP_2 = 72$ in Paper 1. ✓ Right: Set up the algebraic equation $\frac{n!}{(n-2)!} = 72 \Rightarrow n(n-1) = 72$, and solve the quadratic $n^2 - n - 72 = 0$. This gives $n=9$ or $n=-8$. Since $n$ must be a positive integer, $n=9$.
• ❌ Wrong: Using the result you are asked to prove inside the proof itself. ✓ Right: Start from the Left Hand Side (LHS) and manipulate it algebraically until it matches the Right Hand Side (RHS). Show every step clearly.
• ❌ Wrong: Forgetting that $0! = 1$. In selection problems, selecting 0 items ($^nC_0$) is 1 way, not 0 ways. ✓ Right: Remember that $^nC_0 = 1$ for all $n$.
• ❌ Wrong: Not accounting for individual symbols if the problem uses non-alphanumeric characters. ✓ Right: Treat every distinct symbol as a unique object unless stated otherwise. For example, if arranging the symbols @, @, #, $, %, remember there are two identical @ symbols.
• ❌ Wrong: Giving decimal answers when the question requires an exact value (e.g., surds or fractions). ✓ Right: Leave your answer in its simplest surd form or as a simplified fraction. Use the calculator to check your answer, but not to replace the exact value.
• ❌ Wrong: Forgetting to consider domain restrictions when solving for $n$ or $r$. For example, if you get a negative value for $n$ when solving a quadratic, discard it. ✓ Right: Always check that $n$ and $r$ are non-negative integers and that $n \ge r$. Explain why you are discarding any invalid solutions.

---

Exam Tips

• Command Words: "Find the number of ways..." usually requires a numerical answer. "Show that..." requires a step-by-step algebraic derivation using factorial definitions.
• Identify the Type: Before starting, ask: "Does the order matter?" If yes, use $P$. If no, use $C$.
• Calculator Use: In Paper 2, use the $nCr$ and $nPr$ buttons to check your arithmetic, but always write down the formula and substitutions first to secure method marks.
• Exact Values: Never round your answers. The number of ways to arrange objects must always be an integer. If the question involves $n$, ensure your final value for $n$ is a positive integer.
• Check Domain Restrictions: In algebraic problems, $n$ must be greater than or equal to $r$. If your quadratic solver gives a negative value for $n$, discard it and explain why (e.g., "$n > 0$, therefore $n = 9$").
• Mutually Exclusive Cases: When dealing with "at least" or "at most" scenarios, break the problem into mutually exclusive cases and sum the results.
• Keywords: Look for keywords like "arrange" (permutation) and "select" (combination) to guide your approach. However, be careful as the wording can be tricky. Always think about whether order is important.

---

---

---

---

Exam-Style Questions

Practice these original exam-style questions to test your understanding. Each question mirrors the style, structure, and mark allocation of real Cambridge 0606 papers.

Exam-Style Question 1 — Paper 1 (No Calculator Allowed) [7 marks]

Question:

A committee of 5 people is to be chosen from 7 men and 4 women.

(a) Find the number of different committees that can be formed if there are no restrictions. [2]

Worked Solution:

1. Calculate the total number of ways to choose 5 people from 11, without restrictions. ${11 \choose 5} = \frac{11!}{5!6!} = \frac{11 \times 10 \times 9 \times 8 \times 7}{5 \times 4 \times 3 \times 2 \times 1} = 11 \times 3 \times 2 \times 7 = 462$ Using the combinations formula.

2. State the answer. $\boxed{462}$

How to earn full marks: Show the combination formula with the correct values substituted, and simplify to get the correct answer.

(b) Find the number of different committees that can be formed if the committee must contain exactly 3 men and 2 women. [3]

Worked Solution:

1. Calculate the number of ways to choose 3 men from 7. ${7 \choose 3} = \frac{7!}{3!4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ Using the combinations formula.

2. Calculate the number of ways to choose 2 women from 4. ${4 \choose 2} = \frac{4!}{2!2!} = \frac{4 \times 3}{2 \times 1} = 6$ Using the combinations formula.

3. Multiply the two results together. $35 \times 6 = 210$ To find the total number of committees with the specified composition.

4. State the answer. $\boxed{210}$

How to earn full marks: Calculate the combinations for men and women separately, showing your working, then multiply them together.

(c) Find the number of different committees that can be formed if the committee must contain at least 3 men. [2]

Worked Solution:

1. Consider the three cases: 3 men and 2 women (already calculated in part b), 4 men and 1 woman, and 5 men and 0 women. Breaking down the problem into manageable cases.

2. Calculate the number of ways to choose 4 men from 7. ${7 \choose 4} = \frac{7!}{4!3!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = 35$ Using the combinations formula.

3. Calculate the number of ways to choose 1 woman from 4. ${4 \choose 1} = 4$ Using the combinations formula.

4. Calculate the number of ways to choose 5 men from 7. ${7 \choose 5} = \frac{7!}{5!2!} = \frac{7 \times 6}{2 \times 1} = 21$ Using the combinations formula.

5. Multiply the number of ways to choose 4 men and 1 woman. $35 \times 4 = 140$ Calculating the number of committees with 4 men and 1 woman.

6. Sum all the cases: 3 men 2 women, 4 men and 1 woman and 5 men and 0 women $210 + 140 + 21 = 371$ Adding the results from all possible cases.

7. State the answer. $\boxed{371}$

How to earn full marks: Identify all possible cases (3 men, 4 men, 5 men), calculate each combination, and then sum them up.

Common Pitfall: Remember to consider all possible cases when dealing with "at least" or "at most" scenarios. It's easy to miss a case, so double-check your work. Also, make sure you understand the difference between combinations (order doesn't matter) and permutations (order matters).

Exam-Style Question 2 — Paper 1 (No Calculator Allowed) [7 marks]

Question:

(a) Find how many different arrangements can be made of all the letters of the word "SUCCESS". [3]

Worked Solution:

1. Identify the total number of letters and the repetitions. The word "SUCCESS" has 7 letters, with 'S' repeated 3 times and 'C' repeated 2 times.

2. Apply the formula for permutations with repetitions. $\frac{7!}{3!2!} = \frac{7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1}{(3 \times 2 \times 1)(2 \times 1)} = \frac{7 \times 6 \times 5 \times 4}{2} = 7 \times 6 \times 5 \times 2 = 420$ Dividing by the factorials of the repetition counts.

3. State the answer. $\boxed{420}$

How to earn full marks: Use the correct formula for permutations with repeated elements, showing the factorials in the denominator.

(b) In how many of these arrangements are the two 'C's together? [4]

Worked Solution:

1. Treat the two 'C's as a single unit ('CC'). Considering the two 'C's as one element.

2. Now we have 6 units to arrange: S, U, S, S, E, (CC). Reducing the problem to arranging 6 elements with repetitions.

3. Apply the formula for permutations with repetitions. $\frac{6!}{3!} = \frac{6 \times 5 \times 4 \times 3 \times 2 \times 1}{3 \times 2 \times 1} = 6 \times 5 \times 4 = 120$ Dividing by the factorial of the repetition count of 'S'.

4. State the answer. $\boxed{120}$

How to earn full marks: Treat the two 'C's as one unit, then use the permutation formula with repetitions for the remaining letters.

Common Pitfall: When dealing with arrangements where some letters must be together, treat those letters as a single unit. Don't forget to account for repetitions of other letters in the word. Always simplify your factorial expressions before calculating.

Exam-Style Question 3 — Paper 2 (Calculator Allowed) [6 marks]

Question:

A code is to be formed using 3 distinct letters chosen from the letters A, B, C, D, E, F, G, followed by 2 distinct digits chosen from the digits 1, 2, 3, 4, 5, 6, 7, 8, 9.

(a) Find the number of different codes that can be formed. [3]

Worked Solution:

1. Calculate the number of ways to choose 3 distinct letters from 7 and arrange them. ${7P3} = \frac{7!}{(7-3)!} = \frac{7!}{4!} = 7 \times 6 \times 5 = 210$ Using the permutation formula.

2. Calculate the number of ways to choose 2 distinct digits from 9 and arrange them. ${9P2} = \frac{9!}{(9-2)!} = \frac{9!}{7!} = 9 \times 8 = 72$ Using the permutation formula.

3. Multiply the two results together. $210 \times 72 = 15120$ To find the total number of possible codes.

4. State the answer. $\boxed{15120}$

How to earn full marks: Recognize this is a permutation problem, calculate the permutations for letters and digits separately, and multiply them.

(b) Find the number of these codes which contain the letter A and end with an odd digit. [3]

Worked Solution:

1. If the code must contain the letter A, and end with an odd digit, consider the number of odd digits to choose from: 1, 3, 5, 7, 9. Identifying the restrictions.

2. Calculate the number of ways to place the letter A: 2 positions to put it. The A cannot be in the last position as that is reserved for digits. Accounting for the placement of 'A'.

3. Calculate the number of ways to choose the other 2 letters from the remaining 6 (B, C, D, E, F, G) and arrange them. ${6P2} = \frac{6!}{(6-1)!} = \frac{6!}{4!} = 6 \times 5 = 30$ Selecting and arranging the remaining letters.

4. Calculate the number of ways to choose the odd digit: 5 odd digits to choose from. Accounting for the possible odd digits.

5. Calculate the number of ways to choose the other digit: 8 digits to choose from. Accounting for the possible digits.

6. Multiply the results together. $2 \times 30 \times 5 = 300$ To get the total number of codes with the given restrictions.

7. State the answer. $\boxed{300}$

How to earn full marks: Account for the restrictions (A must be included, odd digit at the end), and carefully calculate the permutations for the remaining letters and digits.

Common Pitfall: Carefully consider the restrictions when calculating permutations. In this case, the position of 'A' and the odd digit at the end significantly affect the calculation. Make sure you subtract the used elements from the total when calculating the next permutation.

Exam-Style Question 4 — Paper 2 (Calculator Allowed) [7 marks]

Question:

A sports team of 11 players is to be selected from a squad of 15 players.

(a) Find the number of different ways the team can be selected. [2]

Worked Solution:

1. Calculate the number of ways to choose 11 players from 15, without restrictions. ${15 \choose 11} = \frac{15!}{11!4!} = \frac{15 \times 14 \times 13 \times 12}{4 \times 3 \times 2 \times 1} = 15 \times 7 \times 13 = 1365$ Using the combinations formula.

2. State the answer. $\boxed{1365}$

How to earn full marks: Use the combination formula to calculate the number of ways to choose 11 players from 15.

(b) Within the squad of 15 players, there are 6 players who can only play in defence, 5 players who can only play in midfield, and 4 players who can only play in attack. The team must consist of 4 defenders, 4 midfielders and 3 attackers. Find the number of different teams that can be selected. [3]

Worked Solution:

1. Calculate the number of ways to choose 4 defenders from 6. ${6 \choose 4} = \frac{6!}{4!2!} = \frac{6 \times 5}{2 \times 1} = 15$ Using the combinations formula.

2. Calculate the number of ways to choose 4 midfielders from 5. ${5 \choose 4} = \frac{5!}{4!1!} = 5$ Using the combinations formula.

3. Calculate the number of ways to choose 3 attackers from 4. ${4 \choose 3} = \frac{4!}{3!1!} = 4$ Using the combinations formula.

4. Multiply the three results together. $15 \times 5 \times 4 = 300$ To find the total number of teams with the specified composition.

5. State the answer. $\boxed{300}$

How to earn full marks: Calculate the combinations for each position separately, and then multiply the results together.

(c) Given that John and Peter are in the squad of 15 players, find the number of different teams that can be selected that include either John or Peter, but not both. [2]

Worked Solution:

1. Calculate the number of teams including John but not Peter. This means we choose John (1 way) and then choose the remaining 10 players from the remaining 13 (excluding Peter). ${13 \choose 10} = \frac{13!}{10!3!} = \frac{13 \times 12 \times 11}{3 \times 2 \times 1} = 13 \times 2 \times 11 = 286$ Using the combinations formula.

2. Calculate the number of teams including Peter but not John. This means we choose Peter (1 way) and then choose the remaining 10 players from the remaining 13 (excluding John). ${13 \choose 10} = \frac{13!}{10!3!} = \frac{13 \times 12 \times 11}{3 \times 2 \times 1} = 13 \times 2 \times 11 = 286$ Using the combinations formula.

3. Add the two results together. $286 + 286 = 572$ To find the total number of teams.

4. State the answer. $\boxed{572}$

How to earn full marks: Calculate the number of teams with John but not Peter, then the number of teams with Peter but not John, and add them together.

Common Pitfall: When dealing with "either/or" conditions, calculate each case separately and then add the results. Make sure you exclude the unwanted element (in this case, either John or Peter) when calculating the combinations for the remaining team members.