Combinatorics, recurrence relations and generating functions notes — Unit 4

Combinatorics is the branch of mathematics dealing with counting, arrangement, and combination of objects.

⇒1.1 The Rule of Sum (Addition Principle)

If task A can be done in $m$ ways and task B can be done in $n$ ways, and the tasks are mutually exclusive (they cannot be done at the same time), then either task A OR task B can be done in $m + n$ ways.

⇒1.2 The Rule of Product (Multiplication Principle)

If a procedure can be broken down into two successive stages, where the first stage can occur in $m$ ways and the second stage can occur in $n$ ways, then the total procedure can occur in $m \times n$ ways.

(Keyword clue: 'OR' usually means Add, 'AND' usually means Multiply).

A Permutation is an arrangement of a set of objects into a specific order. Order matters.

⇒2.1 Permutation of Distinct Objects

The number of ways to arrange $r$ objects chosen from $n$ distinct objects is denoted by $P(n, r)$ or $^nP_r$.

$P(n, r) = \frac{n!}{(n - r)!}$

If we arrange all $n$ objects, $P(n, n) = n!$.

⇒2.2 Permutations with Repetition (Multisets)

If we have $n$ objects where $n_1$ are identical of type 1, $n_2$ are identical of type 2, etc., the number of distinct permutations is:

$\frac{n!}{n_1! \times n_2! \times \dots \times n_k!}$

Example: How many ways to arrange the letters of the word 'MISSISSIPPI'? Total letters $n=11$. S=4, I=4, P=2. Ways = $\frac{11!}{4! \cdot 4! \cdot 2!}$.

A Combination is a selection of objects where the order does not matter.

⇒3.1 Combinations of Distinct Objects

The number of ways to select $r$ objects from a set of $n$ distinct objects is denoted by $C(n, r)$ or $\binom{n}{r}$.

$C(n, r) = \frac{n!}{r! (n - r)!}$

⇒3.2 Properties of Combinations

• $\binom{n}{r} = \binom{n}{n - r}$ (Choosing $r$ objects to keep is the same as choosing $n-r$ objects to reject).
• $\binom{n}{0} = 1$ and $\binom{n}{n} = 1$.
• Pascal's Identity: $\binom{n}{r} + \binom{n}{r - 1} = \binom{n + 1}{r}$.

What if we want to select $r$ items from $n$ distinct types, but we can choose multiple items of the same type? (e.g., buying 10 donuts from a shop that sells 4 flavors).

⇒4.1 Stars and Bars Theorem

The number of ways to select $r$ items from $n$ types, with unlimited supply of each type, is given by:

$C(r + n - 1, r) = \binom{r + n - 1}{r}$

⇒4.2 Application to Integer Equations

This formula directly solves the problem: "Find the number of non-negative integer solutions to the equation $x_1 + x_2 + \dots + x_n = r$".

Example: Solutions to $x_1 + x_2 + x_3 = 10$. Here $n=3$, $r=10$. Ways = $\binom{10 + 3 - 1}{10} = \binom{12}{10} = 66$.

A very simple but remarkably powerful logic principle.

⇒5.1 Basic Principle

If $n$ pigeons fly into $m$ pigeonholes, and $n > m$, then at least one pigeonhole must contain two or more pigeons.

⇒5.2 Generalized Pigeonhole Principle

If $N$ objects are placed into $k$ boxes, then there is at least one box containing at least $\lceil N / k \rceil$ objects.

⇒5.3 Applications

Example: In any group of 367 people, at least two people must share the same birthday. (Pigeons = 367, Holes = 366).

Example: How many cards must be drawn from a 52-card deck to guarantee getting 3 cards of the same suit?
Suits ($k$) = 4. We want $\lceil N/4 \rceil = 3$. Minimum $N = (3-1) \times 4 + 1 = 9$ cards.

Used to count the number of elements in the union of overlapping sets.

⇒6.1 For Two Sets

$|A \cup B| = |A| + |B| - |A \cap B|$

⇒6.2 For Three Sets

$|A \cup B \cup C| = |A| + |B| + |C| - |A \cap B| - |A \cap C| - |B \cap C| + |A \cap B \cap C|$

⇒6.3 General Pattern

Add the sizes of individual sets, subtract the intersections of pairs, add the intersections of triples, subtract quadruples, and so on.

Application: Finding the number of integers between 1 and 100 that are divisible by 2, 3, or 5.

A Recurrence Relation is an equation that defines a sequence recursively; each term is defined as a function of its preceding terms.

Example (Fibonacci Sequence): $a_n = a_{n-1} + a_{n-2}$, with initial conditions $a_0 = 0$, $a_1 = 1$.

⇒7.1 Why Study Them?

In computer science, recurrence relations are the primary mathematical tool used to analyse the time complexity of recursive algorithms (like Merge Sort or Binary Search).

⇒7.2 Linear Recurrence Relations with Constant Coefficients

An equation of the form:
$c_0 a_n + c_1 a_{n-1} + c_2 a_{n-2} + \dots + c_k a_{n-k} = f(n)$

• Linear: No squares or powers of the sequence terms (e.g., $a_{n-1}^2$).
• Constant Coefficients: The multipliers $c_i$ are constants, not functions of $n$.
• Homogeneous: If $f(n) = 0$.
• Non-Homogeneous: If $f(n) \neq 0$.
• Order (Degree): The difference between the highest and lowest subscripts (here, $n - (n-k) = k$).

To solve $a_n + c_1 a_{n-1} + c_2 a_{n-2} = 0$, we find a closed-form formula (an equation for $a_n$ that does not depend on previous terms).

⇒8.1 The Characteristic Equation Method

• 1. Assume the solution is of the form $a_n = r^n$.
• 2. Substitute this into the relation to get the Characteristic Equation: $r^2 + c_1 r + c_2 = 0$.
• 3. Find the roots of this polynomial equation ($r_1, r_2$).

⇒8.2 Forming the Solution

• Case 1: Roots are real and distinct ($r_1 \neq r_2$).
  General solution: $a_n = A(r_1)^n + B(r_2)^n$.
• Case 2: Roots are real and equal ($r_1 = r_2 = r$).
  General solution: $a_n = (A + Bn) r^n$.

Finally, use the given initial conditions (e.g., $a_0, a_1$) to solve for the constants $A$ and $B$.

For an equation like $a_n - 3a_{n-1} + 2a_{n-2} = 5^n$, the right side $f(n)$ is not zero.

⇒9.1 Structure of the Solution

The total solution is the sum of two parts: $a_n = a_n^{(h)} + a_n^{(p)}$.

• Homogeneous Solution ($a_n^{(h)}$): Solved by setting $f(n) = 0$ and finding the roots as shown on the previous page.
• Particular Solution ($a_n^{(p)}$): A specific solution guessed based on the form of $f(n)$.

⇒9.2 Guessing the Particular Solution

• If $f(n)$ is a constant $C$: Guess $a_n^{(p)} = K$.
• If $f(n)$ is a polynomial like $3n^2$: Guess $a_n^{(p)} = K_2n^2 + K_1n + K_0$.
• If $f(n)$ is exponential like $C \cdot q^n$: Guess $a_n^{(p)} = K \cdot q^n$. (If $q$ is already a root of the characteristic equation, multiply the guess by $n$ or $n^2$).

Substitute the guessed $a_n^{(p)}$ into the original recurrence relation to solve for the constant $K$.

A Generating Function is a formal power series used to represent a sequence of numbers. It translates problems about sequences into problems about functions, allowing us to use calculus and algebra to solve them.

⇒10.1 Definition

The ordinary generating function for the sequence $a_0, a_1, a_2, \dots$ is the infinite polynomial:

$G(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \dots = \sum_{n=0}^{\infty} a_n x^n$

⇒10.2 Standard Generating Functions

Using Taylor series expansion and the binomial theorem, we know:

• $\frac{1}{1 - x} = 1 + x + x^2 + x^3 + \dots$ (Generates the sequence 1, 1, 1, 1...)
• $\frac{1}{(1 - x)^2} = 1 + 2x + 3x^2 + 4x^3 + \dots$ (Generates 1, 2, 3, 4...)
• $e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots$ (Exponential Generating Function)

Generating functions provide an alternative, systematic way to solve recurrence relations.

⇒11.1 Method

• Step 1: Write down the recurrence relation. Multiply both sides by $x^n$ and sum over all valid $n$ to infinity.
• Step 2: Express both sides of the summation in terms of the generating function $G(x) = \sum a_n x^n$. This usually involves factoring out $x$ and adjusting indices.
• Step 3: Solve the resulting algebraic equation to find an explicit formula for $G(x)$.
• Step 4: Expand $G(x)$ back into a power series (often using Partial Fractions and standard expansions). The coefficient of $x^n$ in the expansion is the closed-form solution for $a_n$.

In algorithm analysis, we frequently encounter recurrences that divide the input size, rather than subtracting from it.

Standard Form: $T(n) = aT(n/b) + f(n)$

Where $a \ge 1$ is the number of subproblems, $n/b$ is the size of each subproblem, and $f(n)$ is the cost of dividing and merging.

⇒12.1 Solving via Substitution

Often solved by assuming $n = b^k$, expanding the recurrence tree down to the base case, and summing the series.

Example: Binary Search gives $T(n) = T(n/2) + c$.
Expanding this gives $c + c + c \dots$ ($\log_2 n$ times), yielding $T(n) = O(\log n)$.

Example: Merge Sort gives $T(n) = 2T(n/2) + cn$.
Expanding this yields a tree of depth $\log_2 n$, where each level costs $cn$, yielding $T(n) = O(n \log n)$.

The Master Theorem provides a direct "cookbook" formula for solving divide and conquer recurrences of the form $T(n) = aT(n/b) + O(n^d)$.

⇒13.1 The Three Cases

Compare the values of $a$ and $b^d$.

• Case 1 (Leaves Dominate): If $a > b^d$, then $T(n) = O(n^{\log_b a})$.
  (The work done at the base cases outweighs the merge step).
• Case 2 (Even Split): If $a = b^d$, then $T(n) = O(n^d \log n)$.
  (Work is distributed evenly across all levels).
• Case 3 (Root Dominates): If $a < b^d$, then $T(n) = O(n^d)$.
  (The work done to split/merge at the top level outweighs the recursive calls).

Example: Strassen's Matrix Multiplication is $T(n) = 7T(n/2) + O(n^2)$.
$a=7$, $b=2$, $d=2$. Since $7 > 2^2$ (Case 1), $T(n) = O(n^{\log_2 7}) \approx O(n^{2.81})$.

Combinatorics and recurrences form the mathematical engine for analysing how algorithms scale.

⇒14.1 University Exam Checklist

• Solve counting problems involving permutations with identical objects.
• Apply the Stars and Bars theorem to find non-negative integer solutions to equations.
• Solve a Linear Homogeneous Recurrence Relation given initial conditions.
• Find the particular solution for a Non-Homogeneous Recurrence Relation.
• Use Generating Functions to find the closed-form solution of a sequence.
• State the Master Theorem and apply it to find the time complexity of a given recurrence.

⇒14.2 Placement Interview Focus

• How does Combinatorics relate to calculating probabilities in technical puzzles?
• If an algorithm's complexity is $T(n) = 2T(n/2) + O(n)$, what algorithm is it likely representing? (Merge Sort / Quick Sort average case).
• Explain the intuition behind the Pigeonhole Principle in proving that a hashing algorithm must have collisions.