Questions
3 questions per paper
Difficulty
Medium
Importance
Essential for Discrete Mathematics and Algorithms modules
Overview
Combinatorics is the fundamental study of counting, arrangement, and configuration of objects. Mastering this topic is essential for discrete mathematics and computer science applications, providing the logic required to solve probability and recurrence problems efficiently in university exams.
Permutations and Combinations
Permutations deal with ordered arrangements where sequence matters, while combinations focus on selecting items where order is irrelevant. Understanding the distinction between these two is critical for solving majority of counting problems in exams.
- Permutations: P(n, r) = n! / (n - r)!
- Combinations: C(n, r) = n! / [r!(n - r)!]
- Circular Permutation: (n - 1)!
- Permutation with identical objects: n! / (p!q!r!...)
- Property: C(n, r) = C(n, n - r)
- Pascal's Identity: C(n, k) + C(n, k - 1) = C(n + 1, k)
Pigeonhole Principle
The Pigeonhole Principle is a powerful existence theorem stating that if n items are put into m containers with n > m, at least one container must contain more than one item. It is frequently tested in problems involving guaranteed outcomes in partitions.
- Basic form: If n > m, one box has >= ceil(n/m) items
- Applicable to non-constructive existence proofs
- Useful for proving worst-case scenario constraints
- General form: If n items are in m holes, one hole has >= ceil(n/m) objects
Recurrence Relations
Recurrence relations define a sequence based on its preceding terms, serving as the backbone for algorithmic complexity analysis. Students should focus on solving linear homogeneous relations with constant coefficients.
- Linear Homogeneous: a_n = c_1*a_{n-1} + c_2*a_{n-2}
- Characteristic equation: r^2 - c_1*r - c_2 = 0
- General solution for distinct roots: a_n = A*r_1^n + B*r_2^n
- Fibonacci sequence: F_n = F_{n-1} + F_{n-2}
- Method of undetermined coefficients for non-homogeneous parts
Formula Sheet
P(n, r) = n! / (n - r)!
C(n, r) = n! / (r! * (n - r)!)
C(n, r) = C(n, n - r)
Circular Permutation = (n - 1)!
r^2 - c_1*r - c_2 = 0 (Characteristic Equation)
Pigeonhole Principle: ceil(n/m)
Exam Tip
Always check for identical objects in a set before applying standard permutation formulas to avoid overcounting.
Common Mistakes
- Confusing permutations and combinations by failing to identify if the order of selection matters.
- Forgetting the (n-1)! formula for circular arrangements and using n! instead.
- Neglecting initial conditions when solving recurrence relations, leading to incorrect constants.
More Revision Notes
Ready to test yourself?
Play topic-wise Combinatorics questions in Aspirant Arcade — gamified MCQ practice.
Download Free