| Content | Guidance, clarification and syllabus links |
|---|---|
|
Fundamental counting principle.
Permutations and combinations. \({}^nP_r = \frac{n!}{(n-r)!}\) and \({}^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}\) Arrangements with restrictions. Circular permutations. Applications to probability. |
Link to SL 1.9 Binomial theorem.
Use of technology to calculate large factorials. Distinguishing between situations requiring permutations vs combinations. Advanced topics: arrangements with identical objects, conditional arrangements, inclusion-exclusion principle. Applications in genetics, computer science, and quality control. Link to binomial and multinomial distributions in statistics. Extension to probability spaces and sample counting. |
📌 Introduction
Combinatorics, the mathematics of counting, stands as one of the most fundamental yet sophisticated branches of discrete mathematics. From ancient problems like determining the number of ways to arrange objects to modern applications in cryptography, computer science, and probability theory, counting principles provide the essential tools for analyzing complex systems where order, selection, and arrangement matter. The elegance of combinatorial thinking lies in its ability to transform seemingly impossible counting problems into systematic, calculable solutions.
This advanced topic builds directly on the binomial theorem from SL 1.9, revealing the deep connections between algebraic expansion and combinatorial selection. The fundamental counting principle forms the cornerstone, while permutations and combinations provide specialized tools for handling ordered and unordered selections respectively. As we progress to arrangements with restrictions, circular permutations, and real-world applications, we discover that combinatorics is not just about counting—it’s about understanding the structure and possibilities inherent in mathematical systems, making it indispensable for advanced probability, statistics, and theoretical computer science.
📌 Definition Table
| Term | Definition |
|---|---|
| Fundamental Counting Principle |
If task A can be done in m ways and task B in n ways, then both tasks can be done in m × n ways |
| Factorial |
\(n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1\) By convention: \(0! = 1\) |
| Permutation |
An arrangement of objects where order matters \({}^nP_r = \frac{n!}{(n-r)!}\) ways to arrange r objects from n objects |
| Combination |
A selection of objects where order does not matter \({}^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}\) ways to choose r objects from n objects |
| Circular Permutation |
Arrangement of objects in a circle \((n-1)!\) ways to arrange n distinct objects in a circle |
| Restricted Arrangement |
Permutations with constraints (objects together, apart, or in specific positions) Requires systematic case-by-case analysis |
| Repeated Objects |
Arrangements of n objects with repeated elements \(\frac{n!}{n_1! \times n_2! \times \cdots \times n_k!}\) for k types of repeated objects |
| Inclusion-Exclusion |
Counting principle for overlapping sets \(|A \cup B| = |A| + |B| – |A \cap B|\) |
| Derangement |
Permutation where no object appears in its original position \(D_n = n! \sum_{i=0}^{n} \frac{(-1)^i}{i!}\) (advanced topic) |
📌 Properties & Key Formulas
- Fundamental Counting Principle: For k independent tasks: \(n_1 \times n_2 \times \cdots \times n_k\)
- Permutation Formula: \({}^nP_r = \frac{n!}{(n-r)!}\) for arranging r objects from n
- Combination Formula: \({}^nC_r = \binom{n}{r} = \frac{n!}{r!(n-r)!}\) for selecting r objects from n
- Circular Permutations: \((n-1)!\) for n distinct objects in a circle
- Repeated Objects: \(\frac{n!}{n_1! n_2! \cdots n_k!}\) for identical object arrangements
- Symmetry Property: \({}^nC_r = {}^nC_{n-r}\)
- Pascal’s Identity: \({}^nC_r + {}^nC_{r+1} = {}^{n+1}C_{r+1}\)
- Relationship: \({}^nP_r = {}^nC_r \times r!\)
Decision Tree for Counting Problems:
YES → Use Permutations
NO → Use Combinations
Step 2: Are there restrictions?
YES → Use complementary counting or case analysis
NO → Apply direct formula
Step 3: Are objects identical?
YES → Use multinomial coefficients
NO → Use standard formulas
Step 4: Circular arrangement?
YES → Use (n-1)! formula
NO → Use standard permutation formula
Advanced Counting Scenarios:
- Committee Selection: Use combinations \({}^nC_r\)
- Password Creation: Use permutations with repetition
- Seating Arrangements: Use permutations or circular permutations
- Distribution Problems: Use multinomial coefficients
- Tournament Brackets: Systematic counting with restrictions
- Graph Theory: Counting paths, trees, and matchings
Remember: Permutations for arrangements (line up people), combinations for selections (choose team members).
📌 Common Mistakes & How to Avoid Them
Wrong: “Choose 3 people from 10 for a team” using \({}^{10}P_3\)
Right: Use \({}^{10}C_3\) because order doesn’t matter in team selection
How to avoid: Ask “If I swap two selected items, is it a different outcome?”
Wrong: “Arrange 5 people with 2 specific people together” by treating as 4 objects
Right: Treat the 2 people as one unit (4! arrangements) × internal arrangements (2!) = 4! × 2!
How to avoid: Use systematic case analysis or complementary counting.
Wrong: Arranging letters in “MATHEMATICS” using 11!
Right: \(\frac{11!}{2! \times 2! \times 2!}\) (accounting for repeated M, A, T)
How to avoid: Always identify and count repeated elements before calculating.
Wrong: Seating 6 people around a circular table using 6!
Right: Use (6-1)! = 5! because circular arrangements eliminate one degree of freedom
How to avoid: Remember that in circles, rotations are considered identical.
Wrong: Counting arrangements and then forgetting some cases overlap
Right: Use inclusion-exclusion principle or carefully define mutually exclusive cases
How to avoid: Clearly define what makes two outcomes different before counting.
📌 Calculator Skills: Casio CG-50 & TI-84
Factorial Calculations:
1. Input number, then [OPTN] → [PROB] → [x!]
2. Example: 8[x!] gives 40320
3. For large factorials: Use scientific notation display
Permutations & Combinations:
1. [OPTN] → [PROB] → [nPr] for permutations
2. [OPTN] → [PROB] → [nCr] for combinations
3. Example: 10[nPr]3 gives P(10,3) = 720
4. Example: 10[nCr]3 gives C(10,3) = 120
Advanced Calculations:
1. Use [MENU] → “Statistics” for probability distributions
2. Store values in variables for complex calculations
3. Use parentheses for multi-step calculations
Verification Techniques:
1. Check P(n,r) = C(n,r) × r!
2. Verify symmetry: C(n,r) = C(n,n-r)
3. Use Pascal’s identity for verification
Basic Operations:
1. [MATH] → [PRB] → [4:!] for factorials
2. [MATH] → [PRB] → [2:nPr] for permutations
3. [MATH] → [PRB] → [3:nCr] for combinations
Complex Calculations:
1. Use [STO] to store intermediate results
2. Example: 8[!]/((8-3)[!]) for P(8,3)
3. Use [ANS] to build on previous calculations
Programming for Repetitive Tasks:
1. [PRGM] → [NEW] to create programs
2. Useful for multinomial coefficients
3. Can automate restriction-based counting
Statistical Applications:
1. [2nd] [DISTR] for probability distributions
2. Link combinatorics to binomial probabilities
3. Use for Monte Carlo simulations
Large Number Handling:
• Use logarithms for very large factorials
• Simplify fractions before calculating
• Check for common factors in numerator/denominator
Verification Methods:
• Small case testing: verify formulas with n=3,4,5
• Symmetry checks: C(n,r) should equal C(n,n-r)
• Boundary testing: check n=r and r=0 cases
Problem-solving workflow:
• Identify the counting type (permutation/combination)
• Check for restrictions or special conditions
• Calculate step by step, storing intermediate values
• Verify answer using alternative methods when possible
📌 Mind Map
📌 Applications in Science and IB Math
- Computer Science: Algorithm complexity analysis, cryptography, data structures
- Genetics: DNA sequence analysis, inheritance patterns, population genetics
- Chemistry: Molecular arrangements, isomer counting, reaction pathways
- Physics: Statistical mechanics, quantum state counting, particle arrangements
- Economics: Market analysis, portfolio optimization, game theory applications
- Engineering: Network design, reliability analysis, optimization problems
- Biology: Ecological modeling, species distribution, evolutionary pathways
- Pure Mathematics: Graph theory, number theory, algebraic structures
Excellent IA Topics:
• Genetic inheritance modeling using advanced combinatorial techniques
• Cryptographic analysis: combinations in code-breaking and security
• Sports tournament design and optimization using combinatorial principles
• Social network analysis: counting connections and influence patterns
• Card game mathematics: probability and counting in poker, bridge
• DNA sequence analysis: combinatorial approaches to genetic patterns
• Traffic flow optimization: combinations in urban planning
• Art and design: combinatorial aesthetics and pattern generation
IA Structure Tips:
• Begin with simple, concrete examples before advancing to complex theory
• Use technology to verify calculations and explore large-scale patterns
• Include historical development and multiple cultural perspectives
• Connect theoretical results to real-world data and applications
• Explore extensions like generating functions or recurrence relations
• Use statistical analysis to validate combinatorial models
• Create visual representations of complex counting scenarios
• Discuss computational complexity and algorithmic approaches
• Address limitations and assumptions in real-world modeling
📌 Worked Examples (IB Style)
Q1. In how many ways can 7 people be arranged in a line if 2 specific people must not stand next to each other?
Solution:
Method: Complementary counting
Total arrangements – Arrangements with 2 people together
Step 1: Total arrangements of 7 people
Total = 7! = 5040
Step 2: Arrangements with 2 specific people together
Treat the 2 people as one unit → 6 units to arrange
Arrangements = 6! × 2! = 720 × 2 = 1440
(6! for arranging units, 2! for internal arrangement)
Step 3: Apply complementary counting
Required arrangements = 5040 – 1440 = 3600
✅ Answer: 3600 ways
Q2. A committee of 5 people is to be selected from 8 men and 6 women. Find the number of ways if the committee must have at least 2 women.
Solution:
Method: Case-by-case analysis
Case 1: Exactly 2 women, 3 men
Ways = \({}^6C_2 \times {}^8C_3 = 15 \times 56 = 840\)
Case 2: Exactly 3 women, 2 men
Ways = \({}^6C_3 \times {}^8C_2 = 20 \times 28 = 560\)
Case 3: Exactly 4 women, 1 man
Ways = \({}^6C_4 \times {}^8C_1 = 15 \times 8 = 120\)
Case 4: Exactly 5 women, 0 men
Ways = \({}^6C_5 \times {}^8C_0 = 6 \times 1 = 6\)
Total: 840 + 560 + 120 + 6 = 1526
✅ Answer: 1526 ways
Q3. In how many ways can the letters of the word “STATISTICS” be arranged?
Solution:
Step 1: Count letters and repetitions
STATISTICS has 10 letters:
S appears 3 times, T appears 3 times, A appears 1 time,
I appears 2 times, C appears 1 time
Step 2: Apply formula for repeated objects
\(\text{Arrangements} = \frac{n!}{n_1! \times n_2! \times \cdots \times n_k!}\)
Step 3: Calculate
\(\text{Arrangements} = \frac{10!}{3! \times 3! \times 1! \times 2! \times 1!}\)
Step 4: Evaluate
\(= \frac{3628800}{6 \times 6 \times 1 \times 2 \times 1} = \frac{3628800}{72} = 50400\)
✅ Answer: 50,400 arrangements
Q4. Find the number of ways 8 people can be seated around a circular table if 2 specific people must sit together.
Solution:
Step 1: Treat the 2 specific people as one unit
We now have 7 units to arrange in a circle
Step 2: Arrange units in a circle
Number of ways = (7-1)! = 6! = 720
Step 3: Account for internal arrangement
The 2 specific people can be arranged in 2! = 2 ways
Step 4: Calculate total
Total arrangements = 6! × 2! = 720 × 2 = 1440
✅ Answer: 1440 ways
Q5. A password consists of 4 digits followed by 3 letters. How many different passwords are possible if repetition is allowed?
Solution:
Step 1: Apply fundamental counting principle
Total possibilities = (choices for digits) × (choices for letters)
Step 2: Count digit possibilities
4 digit positions, each can be 0-9 (10 choices)
With repetition allowed: \(10^4 = 10,000\) possibilities
Step 3: Count letter possibilities
3 letter positions, each can be A-Z (26 choices)
With repetition allowed: \(26^3 = 17,576\) possibilities
Step 4: Calculate total passwords
Total = \(10^4 \times 26^3 = 10,000 \times 17,576 = 175,760,000\)
✅ Answer: 175,760,000 passwords
Key problem-solving strategies:
• Identify whether order matters (permutation vs combination)
• Look for restrictions and handle them systematically
• Use complementary counting for “at least” or “at most” problems
• Break complex problems into simpler cases
• Always verify your answer makes intuitive sense
• Check boundary cases and special conditions
📌 Multiple Choice Questions (with Detailed Solutions)
Q1. In how many ways can 5 people be arranged in a circle?
A) 5! B) (5-1)! C) 5!/2 D) 5!/5
📖 Show Answer
Solution:
For circular arrangements, we fix one person’s position to eliminate rotational symmetry.
With n people in a circle, there are (n-1)! distinct arrangements.
For 5 people: (5-1)! = 4! = 24 ways
✅ Answer: B) (5-1)!
Q2. What is \({}^8P_3\)?
A) 56 B) 336 C) 512 D) 40320
📖 Show Answer
Solution:
\({}^8P_3 = \frac{8!}{(8-3)!} = \frac{8!}{5!}\)
\(= \frac{8 \times 7 \times 6 \times 5!}{5!} = 8 \times 7 \times 6 = 336\)
✅ Answer: B) 336
Q3. How many different committees of 4 can be formed from 9 people?
A) 36 B) 126 C) 3024 D) 6561
📖 Show Answer
Solution:
This is a combination problem since order doesn’t matter in committee selection.
\({}^9C_4 = \frac{9!}{4!(9-4)!} = \frac{9!}{4! \times 5!}\)
\(= \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = \frac{3024}{24} = 126\)
✅ Answer: B) 126
📌 Short Answer Questions (with Detailed Solutions)
Q1. Find the number of ways to arrange the letters in the word “BANANA”.
📖 Show Answer
Complete solution:
Step 1: Count letters and repetitions
BANANA has 6 letters: B(1), A(3), N(2)
Step 2: Apply multinomial coefficient
Arrangements = \(\frac{6!}{1! \times 3! \times 2!} = \frac{720}{1 \times 6 \times 2} = \frac{720}{12} = 60\)
✅ Answer: 60 arrangements
Q2. A team of 6 is to be chosen from 10 players, including a specific player who must be on the team. How many ways can this be done?
📖 Show Answer
Complete solution:
Step 1: Account for the required player
Since one specific player must be on the team, we need to choose 5 more from the remaining 9 players.
Step 2: Calculate combinations
Ways = \({}^9C_5 = \frac{9!}{5! \times 4!} = \frac{9 \times 8 \times 7 \times 6}{4 \times 3 \times 2 \times 1} = \frac{3024}{24} = 126\)
✅ Answer: 126 ways
📌 Extended Response Questions (with Full Solutions)
Q1. A school has 12 teachers: 7 male and 5 female. A committee of 4 teachers is to be formed.
(a) How many different committees can be formed? [2 marks]
(b) How many committees have at least one female teacher? [4 marks]
(c) How many committees have equal numbers of male and female teachers? [3 marks]
(d) If the committee must have a chairperson, how many ways can this be arranged with at least one female? [4 marks]
📖 Show Answer
Complete solution:
(a) Total committees:
Choose 4 from 12 teachers: \({}^{12}C_4 = \frac{12!}{4! \times 8!} = \frac{12 \times 11 \times 10 \times 9}{4!} = \frac{11880}{24} = 495\)
(b) At least one female:
Method: Total – All male committees
All male committees: \({}^7C_4 = \frac{7!}{4! \times 3!} = \frac{7 \times 6 \times 5}{6} = 35\)
Committees with at least one female: \(495 – 35 = 460\)
(c) Equal numbers (2 male, 2 female):
Ways = \({}^7C_2 \times {}^5C_2 = 21 \times 10 = 210\)
(d) Committee with chairperson and at least one female:
From part (b): 460 committees have at least one female
Each committee can choose chairperson in 4 ways
Total arrangements: \(460 \times 4 = 1840\)
✅ Final Answers:
(a) 495 committees
(b) 460 committees
(c) 210 committees
(d) 1840 arrangements