Figure 1.7: Core Restriction Strategies: Block Method (Together) vs. Gap Method (Separated)
1. Fundamental Principles of Counting
- The Addition Principle (Rule of Sum): If an event can occur in $m$ ways and a second mutually exclusive event can occur in $n$ ways, then either event can occur in $m + n$ ways.
- The Multiplication Principle (Rule of Product): If a process can be broken into two successive stages where stage 1 has $m$ possible outcomes and stage 2 has $n$ possible outcomes regardless of stage 1, then the overall process has $m \times n$ outcomes.
2. Permutations vs. Combinations
The distinction between order mattering and order being irrelevant is fundamental:
| Concept | Mathematical Definition | Formula | Context Example |
|---|---|---|---|
| Permutations (Ordered) | Arrangement of $r$ objects selected from $n$ distinct objects where order matters. | $${}^n P_r = P(n, r) = \frac{n!}{(n - r)!}$$ | Gold, silver, bronze medalists; assign roles (President, Secretary); line-ups; passcodes. |
| Combinations (Unordered) | Selection of $r$ objects from $n$ distinct objects where order does NOT matter. | $${}^n C_r = \binom{n}{r} = \frac{n!}{r!(n - r)!}$$ | Choosing a committee of 4 people; drawing a hand of 5 playing cards; selecting pizza toppings. |
3. Permutations with Repetition & Indistinguishable Objects
When arranging $n$ total objects where $n_1$ are identical of type 1, $n_2$ of type 2, $\dots$, $n_k$ of type $k$ (with $\sum n_i = n$):
$$\text{Number of distinct permutations} = \frac{n!}{n_1! \, n_2! \, \dots \, n_k!}$$Example: For the word PARALLEL ($n = 8$ letters with 3 L's and 2 A's): $\frac{8!}{3! \, 2!} = \frac{40,320}{6 \times 2} = 3,360$.
4. Circular Permutations
When $n$ distinct objects are arranged in a closed circle:
- Rotational Equivalence: Shifting all $n$ people by 1 seat in the circle produces the exact same relative configuration. There is no unique "head" of the table. Fixing one person's position removes the $n$-fold rotational redundancy: $$\text{Circular arrangements} = \frac{n!}{n} = (n - 1)!$$
- Flippable Loops (Keyrings & Necklaces): If the arrangement can be viewed from both sides (flipped over, reversing clockwise and anticlockwise order): $$\text{Necklace arrangements} = \frac{(n - 1)!}{2}$$
5. Key Restriction Techniques for Examination Problems
- 1. The Block Method (Objects Must Be Together): Treat the group of items that must stay together as a single composite unit ("super-element"). Permute the composite units, then multiply by the internal permutations of the block.
$\text{Total} = (\text{number of composite units})! \times (\text{internal permutations})!$ - 2. The Gap / Slot Method (Objects Must Be Separated / Never Adjacent): Arrange the unrestricted objects first with single spaces between and around them. If there are $k$ unrestricted objects, they create $k + 1$ available gaps. Choose and assign slots for the restricted items:
$\text{Total} = k! \times {}^{k+1} P_m$ - 3. Complementary Counting ("At Least One"): When direct counting requires multiple tedious cases, subtract the invalid outcomes from the unrestricted universe:
$\text{Count}(\ge 1) = \text{Total Unrestricted Count} - \text{Count}(\text{None})$
Worked Examples
Worked Example 1: Permutations of "ABSOLUTE" with Vowel Grouping
Question: Consider the letters in the word ABSOLUTE (8 distinct letters: A, B, S, O, L, U, T, E).
(a) Find the total number of distinct 8-letter arrangements. [1 mark]
(b) Find the number of arrangements in which all 4 vowels (A, E, O, U) are adjacent. [3 marks]
(c) Find the number of arrangements in which no two vowels are adjacent. [3 marks]
Solution:
(a) Total Unrestricted Arrangements: All 8 letters are distinct: [A1]
$$\text{Total} = 8! = 40,320$$(b) All 4 Vowels Together (Block Method): Treat the 4 vowels $\{A, E, O, U\}$ as a single block: [M1]
$$\text{Elements to arrange} = \{[Vowels], B, S, L, T\} \implies 5 \text{ units}$$Arrange the 5 units in $5!$ ways. Within the block, the 4 vowels can be permuted in $4!$ ways: [M1]
$$\text{Arrangements} = 5! \times 4! = 120 \times 24 = 2,880 \quad [\text{A1}]$$(c) No Two Vowels Adjacent (Gap Method): First arrange the 4 consonants $\{B, S, L, T\}$ in a line: [M1]
$$\text{Consonants arrangement} = 4! = 24$$The 4 consonants create 5 potential gaps: $\_ \, C_1 \, \_ \, C_2 \, \_ \, C_3 \, \_ \, C_4 \, \_$ [M1]
We must choose 4 of these 5 gaps and assign the 4 distinct vowels into them (${}^5 P_4$ or $\binom{5}{4} \times 4!$):
Worked Example 2: Circular Table Seating with Spouses Separated
Question: Five married couples (10 people in total) attend a dinner party and sit around a circular table.
(a) Find the total number of circular seating arrangements. [1 mark]
(b) Find the number of arrangements if men and women must alternate. [3 marks]
(c) For a specific couple, John and Mary, find the probability that they sit directly next to each other in an alternating seating arrangement. [3 marks]
Solution:
(a) Total Circular Arrangements: For $n = 10$ people around a circle: [A1]
$$\text{Total} = (10 - 1)! = 9! = 362,880$$(b) Alternating Men and Women:
Seat the 5 men first around the circle. Fixing one man removes rotational symmetry, leaving $(5 - 1)! = 4! = 24$ ways to arrange the men. [M1]
The 5 men create 5 distinct circular seats between them. Because the seats are now identifiable relative to the seated men, the 5 women can be assigned to these 5 seats in $5!$ ways: [M1]
(c) Probability John and Mary are Adjacent in Alternating Layout:
Seat John first at the table (1 way). [M1]
In an alternating arrangement, Mary can only sit in one of the 2 seats directly adjacent to John (to his immediate left or immediate right).
The other 4 men can be seated in the remaining 4 male seats in $4! = 24$ ways. [M1]
Mary chooses one of the 2 adjacent seats ($2$ ways), and the other 4 women fill the remaining 4 female seats in $4! = 24$ ways:
$$\text{Favourable arrangements} = 4! \times 2 \times 4! = 24 \times 2 \times 24 = 1,152$$
$$\text{Probability} = \frac{1,152}{2,880} = \frac{2}{5} = 0.4 \quad [\text{A1}]$$
(Short cut: John has 2 adjacent seats out of 5 available female seats $\implies \frac{2}{5}$).
Worked Example 3: Committee Selection with "At Least One" Quotas
Question: A student council committee of 5 members is to be formed from a pool of 6 seniors and 8 juniors.
(a) How many committees can be formed if there are no restrictions? [1 mark]
(b) How many committees contain at least one senior and at least one junior? [3 marks]
(c) How many committees contain strictly more seniors than juniors? [3 marks]
Solution:
(a) Unrestricted Committee: Choose 5 from $6 + 8 = 14$ people: [A1]
$$\binom{14}{5} = \frac{14 \times 13 \times 12 \times 11 \times 10}{5 \times 4 \times 3 \times 2 \times 1} = 2,002$$(b) At Least One Senior and At Least One Junior (Complementary Counting): [M1]
Subtract the mutually exclusive impossible cases: (all seniors) and (all juniors):
(c) Strictly More Seniors Than Juniors:
A 5-person committee has more seniors than juniors if there are 3, 4, or 5 seniors: [M1]
- Case 1 (3 seniors, 2 juniors): $\binom{6}{3} \times \binom{8}{2} = 20 \times 28 = 560$ [A1]
- Case 2 (4 seniors, 1 junior): $\binom{6}{4} \times \binom{8}{1} = 15 \times 8 = 120$ [A1]
- Case 3 (5 seniors, 0 juniors): $\binom{6}{5} \times \binom{8}{0} = 6 \times 1 = 6$
Worked Example 4: Combinatorial Probability in Card Hands
Question: Five cards are drawn at random without replacement from a standard deck of 52 cards.
Find the exact probability of obtaining:
(a) A "Full House" (3 cards of one rank and 2 cards of another rank). [3 marks]
(b) Exactly two Aces. [3 marks]
Solution:
Total possible 5-card hands: $N = \binom{52}{5} = 2,598,960$. [M1]
(a) Full House Probability:
• Choose the rank for the triplet: $\binom{13}{1} = 13$ choices. [M1]
• Choose 3 of the 4 cards of that rank: $\binom{4}{3} = 4$.
• Choose the rank for the pair from the remaining 12 ranks: $\binom{12}{1} = 12$ choices.
• Choose 2 of the 4 cards of that rank: $\binom{4}{2} = 6$.
Total full houses: $13 \times 4 \times 12 \times 6 = 3,744$. [A1]
(b) Exactly Two Aces:
• Choose 2 Aces from the 4 available Aces: $\binom{4}{2} = 6$. [M1]
• Choose the remaining 3 cards from the 48 non-Ace cards: $\binom{48}{3} = \frac{48 \times 47 \times 46}{6} = 17,296$. [M1]
Total favourable hands: $6 \times 17,296 = 103,776$.
Worked Example 5: Anagrams with Adjacent Restriction (MISSISSIPPI)
Question: How many distinct arrangements of the 11 letters in the word MISSISSIPPI can be formed such that no two S's are adjacent? [5 marks]
Solution:
Count the frequencies of each letter in MISSISSIPPI: [M1]
• M: 1
• I: 4
• S: 4 (the restricted letters)
• P: 2
Total non-S letters: $1 + 4 + 2 = 7$ letters ($\{M, I, I, I, I, P, P\}$).
Step 1: Arrange the 7 non-S letters: Using permutations with repetition: [M1]
$$N_{\text{non-S}} = \frac{7!}{1! \, 4! \, 2!} = \frac{5,040}{1 \times 24 \times 2} = \frac{5,040}{48} = 105 \quad [\text{A1}]$$Step 2: Apply Gap Method for the 4 S's:
The 7 arranged non-S letters create $7 + 1 = 8$ potential gaps: [M1]
Because all 4 S's are identical, placing an S in a chosen gap does not involve internal order! We simply choose 4 distinct gaps out of the 8 available: [M1]
$$\binom{8}{4} = \frac{8 \times 7 \times 6 \times 5}{4 \times 3 \times 2 \times 1} = 70 \quad [\text{A1}]$$Step 3: Combine by Multiplication Principle: [A1]
$$\text{Total valid arrangements} = 105 \times 70 = 7,350$$Practice Exercises (10 Tiered Questions)
Try these 10 exam-style questions, from core skills to harder problems. Open each question to view its solution.
A 4-digit PIN code is created using the digits 0 to 9.
(a) How many PINs can be formed if repetition of digits is allowed?
(b) How many PINs can be formed if no digit may be repeated?
(c) How many 4-digit numbers greater than 5000 can be formed without repetition?
Show Full Solution
(a) Repetition allowed: $10^4 = 10,000$ codes. [A1]
(b) No repetition: ${}^{10} P_4 = 10 \times 9 \times 8 \times 7 = 5,040$ codes. [A1]
(c) Numbers > 5000: The first digit must be chosen from $\{5, 6, 7, 8, 9\}$ ($5$ options). The remaining 3 digits can be any of the remaining 9 digits without repetition: $5 \times (9 \times 8 \times 7) = 5 \times 504 = 2,520$. [A1]
Find the number of distinct arrangements of the letters in the word STATISTICS.
Show Full Solution
Total letters: $10$. Frequencies: S: 3, T: 3, A: 1, I: 2, C: 1. [M1]
Distinct arrangements: $\frac{10!}{3! \, 3! \, 2! \, 1! \, 1!} = \frac{3,628,800}{6 \times 6 \times 2} = \frac{3,628,800}{72} = 50,400$. [A1]
Seven delegates attend an international summit and sit at a round table.
(a) In how many ways can they be seated?
(b) In how many ways can they be seated if Delegate A and Delegate B refuse to sit next to each other?
Show Full Solution
(a) Total circular seating: $(7 - 1)! = 6! = 720$. [A1]
(b) A and B not together: [M1]
Total ways with A and B together (Block method): treat [AB] as 1 person $\implies (6 - 1)! \times 2! = 5! \times 2 = 240$. [A1]
Ways where A and B are NOT together: $720 - 240 = 480$. [A1]
Four different Mathematics books, three different Physics books, and two different Chemistry books are placed on a bookshelf. Find the number of arrangements such that books of the same subject remain together.
Show Full Solution
Treat each subject as a block: $[M], [P], [C]$. [M1]
Number of ways to arrange the 3 blocks: $3! = 6$. [A1]
Internal arrangements:
• Mathematics books: $4! = 24$
• Physics books: $3! = 6$
• Chemistry books: $2! = 2$ [M1]
Total arrangements: $3! \times (4! \times 3! \times 2!) = 6 \times (24 \times 6 \times 2) = 6 \times 288 = 1,728$. [A1]
Five boys and four girls stand in a straight line for a photograph. In how many ways can they stand if no two girls are allowed to stand next to each other?
Show Full Solution
Step 1: Arrange the 5 boys in a row: $5! = 120$ ways. [M1]
Step 2: The 5 boys create 6 gaps: $\_ \, B_1 \, \_ \, B_2 \, \_ \, B_3 \, \_ \, B_4 \, \_ \, B_5 \, \_$. [M1]
Step 3: Choose 4 of the 6 gaps and arrange the 4 girls in them (${}^6 P_4$):
${}^6 P_4 = 6 \times 5 \times 4 \times 3 = 360$. [A1]
Total arrangements: $120 \times 360 = 43,200$. [A1]
A committee of 6 people is chosen from 7 men and 5 women. In how many ways can the committee be chosen if it must contain at least 2 men and at least 2 women?
Show Full Solution
Partition into mutually exclusive cases for (Men, Women): [M1]
• Case 1 (2 Men, 4 Women): $\binom{7}{2} \times \binom{5}{4} = 21 \times 5 = 105$. [A1]
• Case 2 (3 Men, 3 Women): $\binom{7}{3} \times \binom{5}{3} = 35 \times 10 = 350$. [A1]
• Case 3 (4 Men, 2 Women): $\binom{7}{4} \times \binom{5}{2} = 35 \times 10 = 350$. [A1]
Total valid committees: $105 + 350 + 350 = 805$. [A1]
Consider the letters of the word EQUATION (all 8 letters distinct).
(a) How many arrangements begin and end with a consonant?
(b) In how many arrangements are all five vowels $\{E, U, A, I, O\}$ in alphabetical order (not necessarily adjacent)?
Show Full Solution
Consonants: $\{Q, T, N\}$ (3 consonants). Vowels: $\{E, U, A, I, O\}$ (5 vowels).
(a) Consonants at ends: [M1]
Pick 2 consonants for ends: ${}^3 P_2 = 3 \times 2 = 6$.
Arrange the remaining 6 letters in middle: $6! = 720$.
Total: $6 \times 720 = 4,320$. [A1]
(b) Vowels in alphabetical order (A, E, I, O, U): [M1]
In any random permutation of the 8 letters, the 5 vowels can appear in $5! = 120$ possible relative orders, exactly 1 of which is alphabetical.
Total: $\frac{8!}{5!} = \frac{40,320}{120} = 336$. [A1]
How many 5-digit even numbers greater than 30,000 can be formed using the digits $\{0, 1, 2, 3, 4, 5, 6\}$ without repetition?
Show Full Solution
Even units digit must be $\{0, 2, 4, 6\}$. First digit must be $\{3, 4, 5, 6\}$.
Because $\{4, 6\}$ overlap both requirements, split into cases based on first digit: [M1]
Case 1: First digit is odd ($\{3, 5\}$ - 2 choices):
• First digit: 2 choices.
• Last digit: must be even ($\{0, 2, 4, 6\}$ - 4 choices).
• Middle 3 digits: chosen from remaining 5 digits: ${}^5 P_3 = 5 \times 4 \times 3 = 60$.
Subtotal: $2 \times 4 \times 60 = 480$. [A1]
Case 2: First digit is even ($\{4, 6\}$ - 2 choices):
• First digit: 2 choices.
• Last digit: 3 remaining even choices ($\{0, 2, \text{and the other even}\}$ - 3 choices).
• Middle 3 digits: ${}^5 P_3 = 60$.
Subtotal: $2 \times 3 \times 60 = 360$. [A1]
Total even numbers > 30,000: $480 + 360 = 840$. [A1]
Eight different keys are placed on a circular keyring.
(a) In how many visually distinct ways can the keys be arranged?
(b) If two specific keys must be separated by at least two other keys, find the number of valid arrangements on the keyring.
Show Full Solution
(a) Keyring arrangements: A keyring can be flipped over in 3D space, so clockwise and counter-clockwise arrangements are identical: [M1]
$\text{Total} = \frac{(8 - 1)!}{2} = \frac{7!}{2} = \frac{5,040}{2} = 2,520$. [A1]
(b) Keys separated by at least 2 keys:
Fix Key 1 at position 1. Positions around ring are $1, 2, 3, 4, 5, 6, 7, 8$.
Key 2 cannot be adjacent to Key 1 (positions 2 and 8 forbidden).
Key 2 also cannot have only 1 key between them (positions 3 and 7 forbidden).
Thus Key 2 can only occupy positions $4, 5$, or $6$ ($3$ positions out of $7$). [M1]
Remaining 6 keys can be placed in $6! = 720$ ways.
Accounting for keyring flip: $\frac{3 \times 6!}{2} = \frac{3 \times 720}{2} = 1,080$. [A1]
Algebraically prove Pascal's Identity: $\binom{n}{r} + \binom{n}{r+1} = \binom{n+1}{r+1}$, and give a brief combinatorial argument explaining why this identity must hold.
Show Full Solution
Algebraic Proof: [M1]
$\binom{n}{r} + \binom{n}{r+1} = \frac{n!}{r!(n-r)!} + \frac{n!}{(r+1)!(n-r-1)!}$
Find common denominator $(r+1)!(n-r)!$: [M1]
$= \frac{n!(r+1)}{(r+1)!(n-r)!} + \frac{n!(n-r)}{(r+1)!(n-r)!} = \frac{n![(r+1) + (n-r)]}{(r+1)!(n-r)!}$
$= \frac{n!(n+1)}{(r+1)!(n-r)!} = \frac{(n+1)!}{(r+1)!((n+1) - (r+1))!} = \binom{n+1}{r+1}$. [A1] [AG]
Combinatorial Explanation:
To choose a committee of $r+1$ people from a group of $n+1$ people containing person $X$:
• If person $X$ is included: choose the remaining $r$ people from $n \implies \binom{n}{r}$.
• If person $X$ is excluded: choose all $r+1$ people from $n \implies \binom{n}{r+1}$.
Since these two cases partition all possible committees, their sum must equal the total number of committees $\binom{n+1}{r+1}$. [R1]
Formula Booklet References
Syllabus AHL 1.10: Permutations and Combinations
$${}^n P_r = \frac{n!}{(n - r)!}, \quad {}^n C_r = \binom{n}{r} = \frac{n!}{r!(n - r)!}$$Key Formulas & Identities
1. Permutations with Identical Items
$$\frac{n!}{n_1! \, n_2! \, \dots \, n_k!}, \quad \text{where } \sum n_i = n$$2. Circular Arrangements
- Around a table (rotations equivalent): $(n - 1)!$
- On a keyring or necklace (rotations and reflections equivalent): $\frac{(n - 1)!}{2}$
3. Core Counting Strategies
- Block Method (Together): Tie items into 1 composite unit $\implies N! \times (\text{internal})!$
- Gap Method (Separated): Arrange unrestricted items first ($k!$), then choose slots (${}^{k+1} P_m$).
- At Least One: $\text{Valid} = \text{Total} - \text{None}$.
Common Exam Pitfalls
"At Least One" Overcounting Trap
When selecting a committee with at least one woman, DO NOT pick 1 woman first and then select the remaining members from the combined pool! This double-counts combinations. Always partition into mutually exclusive cases or use $\text{Total} - \text{No Women}$.
Confusing "No Two Together" with "Not All Together"
"Not all together" means subtracting the case where all elements form one single block ($Total - Block$). "No two together" is much stricter and requires the Gap Method!
Topic Diagnostic Test
Complete this timed test to check your understanding and exam technique.
Section A: Diagnostic Multiple Choice Questions
Which calculation gives the number of ways to select a committee of 3 people from a group of 8 candidates?
How many distinct 3-letter anagrams can be formed from the letters in AAB?
A code consists of 4 symbols chosen from 5 distinct symbols with repetition permitted. How many distinct codes are possible?
Why does circular permutation of $n$ distinct objects use $(n - 1)!$ instead of $n!$?
Section B: Examination-Style Free Response Questions
A team of 4 runners is to be selected from 5 sprinters and 6 middle-distance runners.
(a) Find the total number of different teams that can be selected. [1 mark]
(b) Find the number of teams that contain at least one sprinter and at least one middle-distance runner. [3 marks]
(c) Once selected, the 4 team members run in a 4-leg relay. If the team contains exactly 2 sprinters and 2 middle-distance runners, and the first leg must be run by a sprinter, find the number of possible running orders. [2 marks]
Show Full Markscheme
(a) Total teams: [1 mark]
$\binom{11}{4} = \frac{11 \times 10 \times 9 \times 8}{24} = 330$. [A1]
(b) At least one of each: [3 marks]
Total teams minus teams with only sprinters or only middle-distance runners: [M1]
• All 4 sprinters: $\binom{5}{4} = 5$.
• All 4 middle-distance runners: $\binom{6}{4} = 15$. [A1]
Valid teams: $330 - 5 - 15 = 310$. [A1]
(c) Relay running orders: [2 marks]
Leg 1: must be a sprinter ($2$ choices). [M1]
Legs 2, 3, 4: any order of the remaining 3 runners ($3! = 6$ ways).
Running orders: $2 \times 3! = 12$. [A1]
A group consists of 5 boys and 4 girls.
(a) In how many ways can they be arranged in a line if all 4 girls must stand together? [2 marks]
(b) In how many ways can they be arranged in a line if no two girls may stand next to each other? [3 marks]
(c) If they are arranged completely at random in a circle, find the probability that all 4 girls sit together. [2 marks]
Show Full Markscheme
(a) Girls together (Block Method): [2 marks]
Treat the 4 girls as 1 block $\implies 5 \text{ boys} + 1 \text{ block} = 6 \text{ units}$. [M1]
Arrangements: $6! \times 4! = 720 \times 24 = 17,280$. [A1]
(b) No two girls together (Gap Method): [3 marks]
Arrange the 5 boys first: $5! = 120$ ways. [M1]
The 5 boys create 6 slots: $\_ \, B \, \_ \, B \, \_ \, B \, \_ \, B \, \_ \, B \, \_$.
Assign the 4 girls into 4 of the 6 slots: ${}^6 P_4 = 6 \times 5 \times 4 \times 3 = 360$. [M1]
Total arrangements: $120 \times 360 = 43,200$. [A1]
(c) Circular probability: [2 marks]
Total circular arrangements of 9 people: $(9 - 1)! = 8! = 40,320$. [M1]
Favourable circular arrangements with girls together: treat 4 girls as 1 block $\implies 5 \text{ boys} + 1 \text{ block} = 6 \text{ units}$ around a circle:
$(6 - 1)! \times 4! = 5! \times 4! = 120 \times 24 = 2,880$.
$\text{Probability} = \frac{2,880}{40,320} = \frac{1}{14} \approx 0.0714$. [A1]