Questions
2 questions per paper
Difficulty
Medium-Hard
Importance
High yield for HPCL and NTPC technical sections
Overview
Combinatorics and Recurrences form the mathematical backbone of algorithm analysis and discrete optimization in PSU engineering exams. Mastery of these topics is essential for solving problems related to state transitions and arrangement possibilities, which frequently appear in technical aptitude sections.
Counting & Pigeonhole Principle
This subtopic deals with fundamental counting rules and the logic of set distribution. The Pigeonhole Principle is a powerful tool for proving the existence of certain conditions in finite sets.
- Rule of Sum: Total ways = n + m for disjoint sets
- Rule of Product: Total ways = n * m for sequential choices
- Pigeonhole Principle: If n items are put into m containers where n > m, at least one container holds more than one item
- Inclusion-Exclusion Principle for overlapping sets
Permutations & Combinations
Permutations focus on ordered arrangements, while combinations focus on selection. Understanding the distinction between selection and arrangement is crucial for handling selection-based numerical problems.
- Permutations: nPr = n! / (n-r)!
- Combinations: nCr = n! / (r!(n-r)!)
- Circular Permutation: (n-1)!
- Identical items permutation: n! / (p!q!r!)
- nCr = nC(n-r)
Recurrence Relations
Recurrence relations express the complexity or state of a problem in terms of its smaller sub-problems. These are critical for determining the time complexity of recursive algorithms like Merge Sort or Quick Sort.
- Homogeneous Linear Recurrence: c0*an + c1*an-1 + ... = 0
- Characteristic Equation: r^k + c1*r^(k-1) + ... = 0
- Master Theorem: T(n) = aT(n/b) + f(n)
- Linear non-homogeneous recurrence solution = homogeneous + particular solution
Generating Functions
Generating functions convert sequence problems into algebraic manipulation problems, making them useful for solving complex recurrence relations and partition problems.
- Ordinary Generating Function: G(x) = sum(an * x^n)
- Exponential Generating Function: E(x) = sum(an * x^n / n!)
- Use binomial expansion (1-x)^(-n) for series representation
- Applicable for solving linear recurrences with constant coefficients
Formula Sheet
nPr = n! / (n-r)!
nCr = n! / (r!(n-r)!)
nCr = (n-1)C(r-1) + (n-1)Cr
T(n) = aT(n/b) + O(n^d)
Exam Tip
Always verify if the order matters before picking between nPr and nCr; in PSU exams, half the questions are solvable by just identifying this distinction correctly.
Common Mistakes
- Confusing order-dependent permutations with order-independent combinations in probability questions
- Forgetting to check boundary conditions (initial values) when solving recurrence relations
- Applying the Pigeonhole Principle without correctly identifying the pigeons and the holes
More Revision Notes
Ready to test yourself?
Play topic-wise Combinatorics & Recurrences questions in Aspirant Arcade — gamified MCQ practice.
Download Free