Permutations and Combinations
CSEC Additional Mathematics Essential Knowledge: Permutations and combinations are fundamental counting techniques used to determine the number of ways to arrange or select objects. These concepts are essential for probability calculations and appear in various real-world scenarios from lottery odds to password security.
Key Concept: Permutations concern arrangements where order matters. Combinations concern selections where order does not matter. The fundamental difference lies in whether the sequence/positioning of items is important.
Part 1: Fundamental Counting Principle & Factorials
Building Blocks of Counting
If one event can occur in \(m\) ways and a second event can occur in \(n\) ways, then the two events can occur in \(m \times n\) ways.
A restaurant offers 3 types of appetizers and 4 types of main courses. How many different meals (appetizer + main course) can be ordered?
The factorial of a non-negative integer \(n\), denoted \(n!\), is the product of all positive integers less than or equal to \(n\).
Special cases: \(0! = 1\), \(1! = 1\)
Examples:
\(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\)
\(4! = 4 \times 3 \times 2 \times 1 = 24\)
\(\frac{8!}{6!} = \frac{8 \times 7 \times 6!}{6!} = 8 \times 7 = 56\)
Part 2: Permutations
Arrangements Where Order Matters
The number of ways to arrange \(n\) distinct objects in a row:
The number of ways to arrange \(r\) objects from \(n\) distinct objects:
Notation: Also written as \(^nP_r\) or \(P_r^n\)
In a race with 8 runners, how many ways can gold, silver, and bronze medals be awarded?
When arranging \(n\) objects where some are identical:
Where \(n_1, n_2, \ldots, n_k\) are the counts of each type of identical object.
How many different arrangements can be made from the letters of “MISSISSIPPI”?
Arranging objects in a circle (rotations considered the same):
For \(n\) distinct objects arranged around a circle.
In how many ways can 6 people be seated around a circular table?
Part 3: Combinations
Selections Where Order Doesn’t Matter
The number of ways to choose \(r\) objects from \(n\) distinct objects (order unimportant):
Notation: Also written as \(^nC_r\), \(C_r^n\), or \(\binom{n}{r}\) (binomial coefficient)
Choose r from n
Symmetry property
One way to choose nothing
A committee of 4 people is to be chosen from 10 candidates. How many different committees are possible?
Calculate \(C(100, 98)\).
| Aspect | Permutations | Combinations |
|---|---|---|
| Order matters? | YES | NO |
| Formula | \(P(n, r) = \frac{n!}{(n-r)!}\) | \(C(n, r) = \frac{n!}{r!(n-r)!}\) |
| Example situation | Race positions (1st, 2nd, 3rd) | Committee selection |
| Relationship | \(P(n, r) = C(n, r) \times r!\) Permutations = Combinations × arrangements of selected items |
|
Part 4: Decision Tree – Which Method to Use?
Step-by-Step Problem Solving Guide
• Positions ranked?
• Arrangement specific?
Examples: passwords, race positions, seating arrangements
Examples: committees, lottery numbers, handshakes
• Repeated objects: \(\frac{n!}{n_1!n_2!\cdots}\)
• Circular arrangements: \((n-1)!\)
• Restrictions: handle separately
Memory Aid: Permutations = Positions matter. Combinations = Choices only. If you can swap two items and get the same result → Combinations. If swapping gives a different result → Permutations.
Part 5: Applications with Restrictions
Problems with Conditions and Limitations
When dealing with restrictions (certain items must/must not be together or in specific positions):
- Treat restricted items as a unit if they must be together
- Consider cases separately if items must not be together
- Fill restricted positions first, then the remaining positions
In how many ways can 5 people be arranged in a row if 2 specific people must sit together?
In how many ways can 5 books be arranged on a shelf if 2 specific books must not be adjacent?
📝 Example 9: Combination with Conditions
A committee of 5 is to be chosen from 7 men and 6 women. How many committees contain at least 3 women?
Quiz: Test Your Understanding
\(P(7, 3) = \frac{7!}{(7-3)!} = \frac{7!}{4!} = 7 \times 6 \times 5 = 210\)
\(C(9, 4) = \frac{9!}{4!5!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = \frac{3024}{24} = 126\)
Alternative: \(C(9, 4) = C(9, 5) = \frac{9 \times 8 \times 7 \times 6 \times 5}{5 \times 4 \times 3 \times 2 \times 1} = 126\)
All letters are distinct, so: \(5! = 5 \times 4 \times 3 \times 2 \times 1 = 120\) arrangements
Order of toppings doesn’t matter, so use combinations:
\(C(8, 3) = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = \frac{336}{6} = 56\) different pizzas
Treat the 3 girls as a single unit. Now we have 5 units (girls unit + 4 boys)
Arrange 5 units: \(5! = 120\) ways
Arrange the 3 girls within their unit: \(3! = 6\) ways
Total: \(120 \times 6 = 720\) arrangements
Choose 2 aces from 4: \(C(4, 2) = 6\)
Choose 3 non-aces from 48: \(C(48, 3) = \frac{48 \times 47 \times 46}{3 \times 2 \times 1} = 17296\)
Total hands: \(6 \times 17296 = 103,776\)
🎯 Key Concepts Summary
- Fundamental Counting Principle: Multiply number of ways for each independent choice
- Factorial: \(n! = n \times (n-1) \times \cdots \times 2 \times 1\), with \(0! = 1\)
- Permutations (order matters):
- \(P(n, r) = \frac{n!}{(n-r)!}\)
- Arrangements of all n objects: \(n!\)
- With repetitions: \(\frac{n!}{n_1!n_2!\cdots}\)
- Circular: \((n-1)!\)
- Combinations (order doesn’t matter):
- \(C(n, r) = \frac{n!}{r!(n-r)!}\)
- Symmetry: \(C(n, r) = C(n, n-r)\)
- Special values: \(C(n, 0) = 1\), \(C(n, 1) = n\), \(C(n, n) = 1\)
- Key Question: Does order/position matter? → Yes: Permutations, No: Combinations
- Common Problem Types:
- Password/word arrangements (permutations)
- Committee/team selection (combinations)
- Seating arrangements (often permutations)
- Lottery/probability problems (combinations)
- Problems with restrictions: handle separately or use complement
- CSEC Exam Strategy:
- Read carefully: identify if order matters
- For large calculations, cancel factorials before multiplying
- Check if problem has restrictions (must/must not be together)
- Show all working: write formula, substitute values, calculate step by step
- Verify answer makes sense (e.g., combinations should be ≤ corresponding permutations)
CSEC Exam Strategy: Permutations and combinations questions often appear in Paper 2. Common mistakes: 1) Confusing permutations with combinations, 2) Forgetting to account for repeated items, 3) Misapplying restrictions, 4) Calculation errors with factorials. Always ask yourself: “Does order matter?” If you can swap two items and it’s the same outcome → combinations. If swapping gives a different outcome → permutations. Show clear working for full marks.
Real-World Applications
Pro Tip: When calculating combinations like \(C(10, 3)\), remember it’s \(\frac{10 \times 9 \times 8}{3 \times 2 \times 1}\), not \(\frac{10 \times 9 \times 8}{3}\). The denominator is \(r!\), not just \(r\). This is a common calculation error!