Chapter 11: Permutations and Combinations
11.1 Factorial Notation and the Fundamental Principle of Counting
Factorial Notation:
For a positive integer \(n\), \(n!\) (read as "\(n\) factorial") is defined as:
\[
n! = n \times (n-1) \times (n-2) \times \cdots \times 3 \times 2 \times 1
\]
Special case: \(0! = 1\) (by definition, to make combinatorial formulas work).
Examples:
- \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)
- \(3! = 3 \times 2 \times 1 = 6\)
The Fundamental Principle of Counting:
If there are \(a\) ways to do one thing and \(b\) ways to do another, then there are:
- \(a \times b\) ways to do both (multiplication principle)
- \(a + b\) ways to do one or the other (addition principle)
Key Words: In general, if you see the word 'AND' you will most likely need to 'MULTIPLY'. If you see the word 'OR' you will most likely need to 'ADD'.
Worked Example 11.1 (Evaluating factorials – non-calculator)
Evaluate:
- \(6!\)
- \(\frac{8!}{6!}\)
- \(\frac{7!}{3!4!}\)
Solution:
(a) \(6! = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 720\)
(b) \(\frac{8!}{6!} = \frac{8 \times 7 \times 6!}{6!} = 8 \times 7 = 56\)
(c) \(\frac{7!}{3!4!} = \frac{7 \times 6 \times 5 \times 4!}{3! \times 4!} = \frac{7 \times 6 \times 5}{3 \times 2 \times 1} = \frac{210}{6} = 35\)
Worked Example 11.2 (Multiplication principle – Mauritian context)
A restaurant in Port Louis offers 4 types of starter, 6 main courses, and 3 desserts. How many different 3-course meals can be chosen?
Solution:
Choose starter AND main course AND dessert.
\[
4 \times 6 \times 3 = 72
\]
Answer: 72 different meals.
11.2 Permutations – Arrangements Where Order Matters
Definition: A permutation is an arrangement of objects in a specific order. The order of arrangement matters.
Number of permutations of \(n\) different items:
\[
{}^{n}P_n = n!
\]
Number of permutations of \(r\) items from \(n\) different items:
\[
{}^{n}P_r = \frac{n!}{(n-r)!}
\]
Derivation: For the first position, there are \(n\) choices. For the second, \(n-1\) choices. Continuing to the \(r\)-th position, there are \(n - r + 1\) choices. The product is:
\[
n(n-1)(n-2)\cdots(n-r+1) = \frac{n!}{(n-r)!}
\]
Note: Permutations questions often use keywords such as "arrange", "order", "sequence", or "password".
Permutations with Restrictions:
- Items that must be together: Treat them as a single "block".
- Items that must be separated: Arrange the other items first, then place the separated items in the gaps.
- Items in fixed positions: Arrange the remaining items around the fixed ones.
Worked Example 11.3 (Permutations of all items – non-calculator)
How many ways can the letters of the word "MAURITIUS" be arranged?
Solution:
There are 9 letters, all different.
\[
9! = 9 \times 8 \times 7 \times 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 362880
\]
Answer: 362,880 ways.
Worked Example 11.4 (Permutations of \(r\) items – non-calculator)
In how many ways can 4 different students be chosen from a class of 10 to fill the positions of President, Vice-President, Secretary, and Treasurer?
Solution:
Order matters (each position is different).
\[
{}^{10}P_4 = \frac{10!}{(10-4)!} = \frac{10!}{6!} = 10 \times 9 \times 8 \times 7 = 5040
\]
Answer: 5040 ways.
Worked Example 11.5 (Restriction – items together – non-calculator)
How many ways can the letters of the word "BOOK" be arranged if the two O's must be together?
Solution:
Treat the two O's as one "block": [OO], B, K.
We have 3 items to arrange: \(3! = 6\) ways.
(Note: The two O's are identical, so there is no internal arrangement of the block.)
Answer: 6 ways.
Worked Example 11.6 (Restriction – items separated – non-calculator)
How many ways can the letters of the word "EXAMS" be arranged if the E and the S must be at the ends?
Solution:
The E and S must be at the ends. They can be arranged in the two end positions in \(2! = 2\) ways.
The remaining 3 letters (X, A, M) can be arranged in the middle 3 positions in \(3! = 6\) ways.
Total ways = \(2 \times 6 = 12\).
Answer: 12 ways.
Worked Example 11.7 (Mauritian context – number plates)
In Mauritius, a number plate consists of 2 letters followed by 4 digits. How many different number plates are possible if letters and digits can be repeated? (Assume 26 letters and 10 digits.)
Solution:
First letter: 26 choices
Second letter: 26 choices
First digit: 10 choices
Second digit: 10 choices
Third digit: 10 choices
Fourth digit: 10 choices
Total = \(26 \times 26 \times 10 \times 10 \times 10 \times 10 = 26^2 \times 10^4 = 676 \times 10000 = 6,760,000\).
Answer: 6,760,000 number plates.
11.3 Combinations – Selections Where Order Does Not Matter
Definition: A combination is a selection of objects where the order of selection does not matter.
Number of combinations of \(r\) items from \(n\) different items:
\[
{}^{n}C_r = \binom{n}{r} = \frac{n!}{(n-r)!r!}
\]
Derivation: The number of permutations of \(r\) items from \(n\) is \({}^{n}P_r\). Each combination of \(r\) items can be arranged in \(r!\) ways to form permutations. Therefore:
\[
{}^{n}C_r \times r! = {}^{n}P_r \Rightarrow {}^{n}C_r = \frac{{}^{n}P_r}{r!} = \frac{n!}{(n-r)!r!}
\]
Note: Combinations questions often use keywords such as "select", "choose", "group", or "committee".
Properties:
- \(\binom{n}{r} = \binom{n}{n-r}\) (symmetry)
- \(\binom{n}{0} = \binom{n}{n} = 1\)
Worked Example 11.8 (Basic combination – non-calculator)
How many ways can a committee of 3 people be chosen from a group of 8?
Solution:
Order does not matter (a committee is a selection).
\[
{}^{8}C_3 = \frac{8!}{5!3!} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56
\]
Answer: 56 ways.
Worked Example 11.9 (Combination with restrictions)
From a group of 5 men and 6 women, a committee of 4 is to be chosen. Find the number of ways if:
- There are no restrictions.
- The committee must contain exactly 2 women.
- The committee must contain at least 2 women.
Solution:
(a) Choose 4 from 11: \({}^{11}C_4 = \frac{11!}{7!4!} = \frac{11 \times 10 \times 9 \times 8}{4 \times 3 \times 2 \times 1} = 330\).
(b) Choose 2 women from 6
AND 2 men from 5:
\[
{}^{6}C_2 \times {}^{5}C_2 = \frac{6!}{4!2!} \times \frac{5!}{3!2!} = 15 \times 10 = 150
\]
(c) "At least 2 women" means 2 women
OR 3 women
OR 4 women.
- 2 women, 2 men: \({}^{6}C_2 \times {}^{5}C_2 = 150\)
- 3 women, 1 man: \({}^{6}C_3 \times {}^{5}C_1 = 20 \times 5 = 100\)
- 4 women, 0 men: \({}^{6}C_4 \times {}^{5}C_0 = 15 \times 1 = 15\)
Total = \(150 + 100 + 15 = 265\).
Answers: (a) 330, (b) 150, (c) 265.
Worked Example 11.10 (Mauritian context – exam question selection)
In an examination, candidates must select 2 questions from the 5 questions in section A and 4 questions from the 8 questions in section B. Find the number of ways in which this can be done.
Solution:
Choose 2 from 5 AND 4 from 8.
\[
{}^{5}C_2 \times {}^{8}C_4 = \frac{5!}{3!2!} \times \frac{8!}{4!4!} = 10 \times 70 = 700
\]
Answer: 700 ways.
11.4 Problem-Solving Strategies
Step-by-step approach:
- Identify whether the problem is permutations (order matters) or combinations (order does not matter).
- Identify if repetition is allowed.
- Identify restrictions (e.g., "at least", "together", "separated", "must start with...").
- Break down the problem into smaller stages using AND/OR logic.
- Multiply for AND stages; add for OR stages.
Keywords:
- Permutations: arrange, order, sequence, password, line, positions
- Combinations: select, choose, group, committee, team, handshake
Worked Example 11.11 (Combined problem – non-calculator)
A group of 10 people, 6 men and 4 women, are to be arranged in a row for a photograph. How many arrangements are possible if:
- No restrictions?
- The women must all be together?
- The men and women must alternate? (Assume they start with a man.)
Solution:
(a) \(10! = 3,628,800\).
(b) Treat the 4 women as one block. We have 6 men + 1 block = 7 items to arrange.
Internal arrangement of women: \(4!\).
Total = \(7! \times 4! = 5040 \times 24 = 120,960\).
(c) Alternate: M W M W M W M W M W.
Arrange men in their 6 positions: \(6!\).
Arrange women in their 4 positions: \(4!\).
Total = \(6! \times 4! = 720 \times 24 = 17,280\).
Chapter 11 Summary
| Concept |
Key points |
| Factorial |
\(n! = n \times (n-1) \times \cdots \times 1\), \(0! = 1\) |
| Permutation |
Order matters: \({}^{n}P_r = \frac{n!}{(n-r)!}\) |
| Combination |
Order does not matter: \(\binom{n}{r} = \frac{n!}{(n-r)!r!}\) |
| Multiplication principle |
For 'AND' \(\rightarrow\) multiply |
| Addition principle |
For 'OR' \(\rightarrow\) add |
| Restrictions |
Handle separately (together, separated, fixed) |
Exercises – Chapter 11
Easy (Drill – Non-Calculator)
- Evaluate:
(a) \(5!\)
(b) \(\frac{9!}{7!}\)
(c) \(\binom{6}{2}\)
- How many ways can 5 books be arranged on a shelf?
- How many ways can a team of 3 be chosen from 10 people?
Medium (Examination Style)
- Find the number of ways to arrange the letters of the word "MATHS".
- In how many ways can 4 people be chosen from 8 to fill the positions of President, Vice-President, Secretary and Treasurer?
- Mauritian context: A committee of 4 is to be selected from 7 men and 5 women.
(a) How many committees are possible?
(b) How many committees have exactly 2 women?
(c) How many committees have at least 2 women?
- How many different 4-digit numbers can be formed using four of the digits 1, 2, 3, 4, 5, 6, 7, 8 if each digit can be used once only?
Hard (Challenge for A*)
- How many ways can the letters of the word "STATISTICS" be arranged?
- A password consists of 2 letters from A, B, C, D, E followed by 3 digits from 0 to 9. No letter or digit may be repeated. Find how many passwords can be formed.
- Mauritian context: A school in Curepipe has 6 teachers and 8 students. They want to form a committee of 5 people that must include at least 2 teachers. Find the number of ways this can be done.