Combinatorics

Overview

Combinatorics is a fundamental branch of discrete mathematics concerned with the systematic enumeration, combination, and arrangement of elements within finite or discrete structures. In the context of Computer Science, its principles are not merely abstract exercises but form the bedrock for analyzing algorithms, understanding data structures, and solving problems in areas such as network design, cryptography, and database theory. The ability to precisely count the number of possible outcomes, configurations, or computational steps is essential for determining the efficiency and feasibility of a given solution.

In this chapter, we shall embark on a structured exploration of this field, beginning with the foundational Counting Principles that govern basic enumeration. We will then progress to the study of Recurrence Relations, a powerful formalism for modeling problems that can be defined in terms of smaller, similar subproblems—a concept intimately familiar from the analysis of recursive algorithms. Finally, we will introduce Generating Functions, an elegant algebraic technique that provides a unified framework for solving complex recurrence relations and counting problems. A thorough command of these topics is indispensable for the GATE examination, where questions frequently test the application of combinatorial reasoning to assess algorithmic complexity and problem-solving aptitude.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Counting Principles | Systematic enumeration using permutations and combinations. |
| 2 | Recurrence Relations | Modeling problems via recursively defined sequences. |
| 3 | Generating Functions | Solving recurrences using polynomial representations. |

---

Learning Objectives

---

We now turn our attention to Counting Principles...

Part 1: Counting Principles

Introduction

In the study of discrete structures, combinatorics is the branch of mathematics concerned with counting. At its core, it seeks to answer the fundamental question: "How many ways can a certain task be done?" For the computer science student, a firm grasp of counting principles is not merely an academic exercise; it is foundational to the analysis of algorithms, the study of probability, the design of data structures, and the understanding of network protocols. The number of possible inputs to an algorithm, the size of a search space in artificial intelligence, or the number of possible network addresses are all problems rooted in combinatorics.

We begin our formal study by establishing the elementary rules upon which all combinatorial analysis is built. These principles, though simple in their statement, are remarkably powerful in their application. We will then proceed to the more structured concepts of permutations and combinations, which provide the vocabulary for discussing ordered and unordered arrangements. Finally, we will synthesize these ideas to tackle complex distribution problems, a frequent subject of inquiry in competitive examinations like GATE, by developing a systematic framework for their solution.

---

The Fundamental Rules of Counting

All sophisticated counting techniques are ultimately derived from two elementary principles: the Rule of Sum and the Rule of Product. Understanding when and how to apply these rules is the first and most critical step in solving any combinatorial problem.

1. The Rule of Sum

The Rule of Sum applies when we must make a choice between two or more mutually exclusive tasks. If a task can be done in $n_1$ ways and a second, separate task can be done in $n_2$ ways, and the two tasks cannot be performed simultaneously, then there are $n_1 + n_2$ ways to perform one of these tasks.

Consider a student who must choose one elective course. If there are 5 courses available from the Mathematics department and 4 courses available from the Physics department, and the student can only choose one course in total, the number of choices is $5 + 4 = 9$. The key is that the choices are disjoint; selecting a math course precludes selecting a physics course.

2. The Rule of Product

The Rule of Product applies when a procedure consists of a sequence of independent tasks. If a procedure can be broken down into a sequence of two tasks, and there are $n_1$ ways to do the first task and for each of these ways, there are $n_2$ ways to do the second task, then there are $n_1 \times n_2$ ways to do the entire procedure.

For instance, to form a 2-character license plate where the first character must be a letter from {A, B, C} and the second must be a digit from {1, 2, 3, 4}, we apply the Rule of Product. There are 3 choices for the first position and 4 choices for the second. The total number of unique license plates is $3 \times 4 = 12$.

3. The Principle of Complementation

Often, counting the number of outcomes in an event $E$ is complicated, whereas counting the number of outcomes not in $E$ (denoted $E'$) is significantly simpler. If $U$ is the universal set of all possible outcomes, then the number of outcomes in $E$ is given by $|E| = |U| - |E'|$. This is known as complementary counting.

This principle is particularly useful for problems involving phrases like "at least one" or "not all".

Worked Example:

Problem: How many binary strings of length 8 contain at least one '1'?

Solution:

Step 1: Define the universal set $U$ and the event $E$.
The universal set $U$ is the set of all binary strings of length 8. The event $E$ is the set of such strings with at least one '1'.

Step 2: Calculate the size of the universal set, $|U|$.
Each of the 8 positions in the string can be either a '0' or a '1'. By the Rule of Product, the total number of strings is:

Step 3: Define the complement event $E'$ and calculate its size.
The complement event $E'$ is the set of strings with no '1's. This means the string must consist of all '0's. There is only one such string: "00000000".

Step 4: Apply the Principle of Complementation.

Answer: There are 255 binary strings of length 8 containing at least one '1'.

---

---

Permutations and Combinations

We now turn our attention to two of the most central concepts in combinatorics: permutations and combinations. The critical distinction between them lies in whether the order of selection is relevant.

1. Permutations: Ordered Arrangements

A permutation is an arrangement of objects in a specific order.

The number of $k$-permutations of a set of $n$ distinct objects is denoted by $P(n, k)$ or $^nP_k$.

A special case arises when we arrange all $n$ objects ($k=n$). The number of permutations is $P(n,n) = n!$.

Worked Example:

Problem: From a group of 10 students, a president, a vice-president, and a treasurer are to be chosen. In how many ways can these positions be filled?

Solution:

Step 1: Identify $n$ and $k$.
We are selecting 3 students from a group of 10 to fill distinct roles. Thus, the order of selection matters.
$n = 10$ (total students)
$k = 3$ (positions to fill)

Step 2: Apply the permutation formula.
This is a problem of finding the number of 3-permutations from a set of 10.

Step 3: Simplify the expression.

Step 4: Compute the final answer.

Answer: There are 720 ways to fill the positions.

2. Combinations: Unordered Selections

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

The number of $k$-combinations of a set of $n$ distinct objects is denoted by $C(n, k)$, $\binom{n}{k}$, or $^nC_k$.

Worked Example:

Problem: From a group of 10 students, a committee of 3 is to be formed. In how many ways can this be done?

Solution:

Step 1: Identify $n$ and $k$.
We are selecting 3 students from a group of 10. Since it is a committee, all members have equal standing, and the order of selection is irrelevant.
$n = 10$ (total students)
$k = 3$ (committee size)

Step 2: Apply the combination formula.
This is a problem of finding the number of 3-combinations from a set of 10.

Step 3: Simplify the expression.

Step 4: Compute the final answer.

Answer: There are 120 ways to form the committee.

---

Advanced Counting: The Distribution Framework

Many combinatorial problems can be framed as distributing $n$ objects into $k$ boxes. The solution strategy depends critically on whether the objects and boxes are distinguishable (distinct) or indistinguishable (identical).

1. Distinct Objects into Distinct Boxes

This is the most straightforward case. Each of the $n$ distinct objects can be placed into any of the $k$ distinct boxes. By the Rule of Product, there are $k$ choices for the first object, $k$ for the second, and so on.

The total number of ways is $k^n$.

Constraint: Every box must receive at least one object (Surjections).
This is a more complex scenario that arises frequently. We seek the number of surjective (onto) functions from a set of size $n$ to a set of size $k$. This can be calculated using the Principle of Inclusion-Exclusion.

2. Identical Objects into Distinct Boxes (Stars and Bars)

When objects are identical, we are only concerned with how many objects are in each distinct box. We can model this problem by arranging $n$ identical items (stars) and $k-1$ dividers (bars). The number of stars before the first bar is the count for the first box, the number between the first and second bar is for the second box, and so on.

This is equivalent to finding the number of non-negative integer solutions to the equation $x_1 + x_2 + \dots + x_k = n$.

Worked Example:

Problem: In how many ways can 10 identical chocolates be distributed among 4 distinct children?

Solution:

Step 1: Identify the model, $n$, and $k$.
This is a problem of distributing identical objects (chocolates) into distinct boxes (children). We can use the Stars and Bars formula.
$n = 10$
$k = 4$

Step 2: Apply the formula.
We need to find the number of ways to arrange $10$ stars and $4-1=3$ bars. The total number of positions is $10+3=13$. We need to choose $3$ positions for the bars (or $10$ for the stars).

Step 3: Calculate the result.

Answer: There are 286 ways to distribute the chocolates.

3. Identical Objects into Identical Boxes (Integer Partitions)

This is the most constrained case. Since both objects and boxes are identical, the only thing that matters is the size of the groups of objects. This problem is equivalent to finding the number of partitions of the integer $n$ into at most $k$ parts.

There is no simple closed-form formula for this. For GATE-level problems, this is typically solved by careful, systematic enumeration.

Worked Example:

Problem: Find the number of ways to distribute 6 identical balls into 3 identical bins.

Solution:

Step 1: Frame the problem as an integer partition.
We need to find the number of ways to write 6 as a sum of at most 3 positive integers. The order of the summands does not matter since the bins are identical.

Step 2: Systematically enumerate all possible partitions of 6.
Let the number of balls in the bins be $(b_1, b_2, b_3)$ such that $b_1 + b_2 + b_3 = 6$ and $b_1 \ge b_2 \ge b_3 \ge 0$.

* Partition into 1 part (2 bins are empty):
$(6, 0, 0)$ - This is one way. The grouping is just $\{6\}$.

* Partitions into 2 parts (1 bin is empty):
$(5, 1, 0)$
$(4, 2, 0)$
$(3, 3, 0)$

* Partitions into 3 parts (no bins are empty):
$(4, 1, 1)$
$(3, 2, 1)$
$(2, 2, 2)$

Step 3: Count the total number of unique partitions.
Summing up the possibilities: $1$ (from 1 part) + $3$ (from 2 parts) + $3$ (from 3 parts) = $7$.

Answer: There are 7 ways to distribute the balls.

---

Problem-Solving Strategies

---

Common Mistakes

---

---

Practice Questions

:::question type="NAT" question="A programming team of 5 members is to be formed from a group of 6 senior programmers and 8 junior programmers. The team must have at least 2 senior programmers. How many such teams can be formed?" answer="1526" hint="Consider the possible cases for the number of senior programmers (2, 3, 4, or 5) and sum the results. Alternatively, use complementary counting." solution="
Method 1: Case-by-case Analysis

The team must have at least 2 senior programmers. The total team size is 5.
Let $S$ denote Senior programmers and $J$ denote Junior programmers.

Case 1: 2 Seniors and 3 Juniors
Number of ways = (Ways to choose 2 $S$ from 6) $\times$ (Ways to choose 3 $J$ from 8)

Case 2: 3 Seniors and 2 Juniors

Case 3: 4 Seniors and 1 Junior

Case 4: 5 Seniors and 0 Juniors

Total ways:

Method 2: Complementary Counting

Total number of ways to form a team of 5 from 14 programmers ($6S + 8J$) is:

The unwanted cases are teams with 0 or 1 senior programmer.
Unwanted Case 1: 0 Seniors and 5 Juniors

Unwanted Case 2: 1 Senior and 4 Juniors

Total unwanted ways = $56 + 420 = 476$.

Result:
Required ways = Total ways - Unwanted ways

Answer: $\boxed{1526}$
"
:::

:::question type="MCQ" question="In how many ways can the letters of the word 'ENGINEER' be arranged such that the arrangement does not start and end with 'E'?" options=["3360","2400","960","3000"] answer="3000" hint="Use complementary counting. Find the total number of arrangements and subtract the number of arrangements where the first and last letters are both 'E'." solution="
Step 1: Calculate the total number of arrangements of the word 'ENGINEER'.
The word 'ENGINEER' has 8 letters.
The letter 'E' appears 3 times.
The letter 'N' appears 2 times.
The letters 'G', 'I', 'R' appear 1 time each.
Total arrangements = $\frac{8!}{3!2!}$

Step 2: Calculate the number of 'unwanted' arrangements, where the string starts and ends with 'E'.
Fix 'E' at the first position and 'E' at the last position.
The remaining 6 letters to arrange are {N, G, I, N, E, R}.
In this set, 'N' appears 2 times.
Number of ways to arrange these 6 letters = $\frac{6!}{2!}$

Step 3: Apply the principle of complementation.
Number of desired arrangements = Total arrangements - Unwanted arrangements

Answer: $\boxed{3000}$
"
:::

:::question type="NAT" question="Let $S = \{1, 2, 3, \dots, 12\}$. The number of ordered pairs of subsets $(A, B)$ of $S$ such that $|A \cap B| = 2$ is ________." answer="3897234" hint="First, choose the 2 elements that will be in the intersection. Then, for each of the remaining elements in S, determine its possible location with respect to sets A and B." solution="
Step 1: Choose the 2 elements for the intersection $A \cap B$.
The universal set $S$ has 12 elements. We need to choose 2 elements that will belong to both $A$ and $B$.
Number of ways to choose these 2 elements = $\binom{12}{2}$.

Step 2: Consider the remaining elements.
There are $12 - 2 = 10$ elements remaining in $S$. For any element $x$ from these 10 elements, there are three possibilities for its membership in $A$ and $B$:

$x \in A$ and $x \notin B$ (i.e., $x \in A \setminus B$)

$x \notin A$ and $x \in B$ (i.e., $x \in B \setminus A$)

$x \notin A$ and $x \notin B$ (i.e., $x \notin A \cup B$)

These 10 elements cannot be in $A \cap B$ as we have already chosen the 2 elements for the intersection.

Step 3: Apply the Rule of Product for the remaining 10 elements.
Each of the 10 elements has 3 independent choices for its location.
So, the number of ways to place these 10 elements is $3^{10}$.

Step 4: Combine the results from Step 1 and Step 3.
The total number of ordered pairs $(A, B)$ is the product of the number of ways to choose the intersection and the number of ways to place the remaining elements.

Answer: $\boxed{3897234}$
"
:::

:::question type="MSQ" question="Which of the following statements are correct for distributing 5 distinct jobs to 3 distinct processors?" options=["The total number of ways to distribute the jobs without any restrictions is 243.","The number of ways to distribute the jobs such that each processor gets at least one job is 150.","If one specific processor must get exactly 2 jobs, the number of ways is 80.","The number of ways such that no processor is idle is 90."] answer="A,B,C" hint="For A, use the basic distinct-to-distinct formula. For B, use the surjection formula (Inclusion-Exclusion). For C, first choose the 2 jobs for the specific processor, then distribute the rest. For D, check if it matches B." solution="
Let $n=5$ (distinct jobs) and $k=3$ (distinct processors).

Option A: Total number of ways without restrictions.
Each of the 5 jobs can be assigned to any of the 3 processors.
By the Rule of Product, total ways = $3^5 = 243$.
Thus, statement A is correct.

Option B: Each processor gets at least one job (no processor is idle).
This is a surjection problem. We use the Principle of Inclusion-Exclusion.

Thus, statement B is correct.

Option C: One specific processor must get exactly 2 jobs.
Step C1: Choose 2 jobs for the specific processor (say P1) out of 5. This can be done in $\binom{5}{2}$ ways.

Step C2: The remaining $5-2=3$ jobs must be distributed among the remaining $3-1=2$ processors (P2, P3).
Each of these 3 jobs can go to either P2 or P3. So, there are $2^3 = 8$ ways.
Step C3: Total ways = (Ways to choose jobs for P1) $\times$ (Ways to distribute remaining jobs)
Total ways = $10 \times 8 = 80$.
Thus, statement C is correct.

Option D: The number of ways such that no processor is idle is 90.
From our calculation for Option B, the number of ways such that no processor is idle is 150.
Thus, statement D is incorrect.

Answer: $\boxed{A,B,C}$
"
:::

---

Summary

---

What's Next?

---

---

Part 2: Recurrence Relations

Introduction

A recurrence relation is a mathematical equation that recursively defines a sequence of values. Each term of the sequence is defined as a function of the preceding terms. In the context of computer science, recurrence relations arise naturally in the analysis of recursive algorithms, where they describe the computational complexity, or running time, as a function of the input size. The process of finding a closed-form, non-recursive expression for a sequence defined by a recurrence relation is known as "solving" the recurrence.

Mastery of this topic is indispensable for the GATE examination, as it forms the bedrock of algorithm analysis. Questions frequently test the ability to solve various classes of recurrences, from simple linear forms to more complex divide-and-conquer relations. We shall explore the principal methods for solving these relations, focusing on the techniques most relevant to the competitive examination setting.

---

Key Concepts

1. Linear Homogeneous Recurrence Relations

We begin with one of the most common forms of recurrence relations encountered in discrete mathematics.

A recurrence relation is said to be linear if the terms of the sequence appear only in the first power and are not multiplied together. It is homogeneous if every term involves a term of the sequence. It has constant coefficients if the coefficients of the sequence terms are fixed constants. The general form of a $k$-th order linear homogeneous recurrence relation with constant coefficients is:

where $c_i \in \mathbb{R}$ are constants and $c_k \neq 0$.

To solve such a relation, we assume a solution of the form $a_n = r^n$ for some constant $r \neq 0$. Substituting this into the relation yields:

Dividing by $r^{n-k}$ (since $r \neq 0$), we obtain the characteristic equation:

The solution to the recurrence is determined by the roots of this polynomial.

Case A: Distinct Roots

If the characteristic equation has $k$ distinct roots $r_1, r_2, \dots, r_k$, the general solution to the recurrence relation is a linear combination of these roots raised to the power of $n$:

The constants $\alpha_1, \alpha_2, \dots, \alpha_k$ are determined using the given initial conditions.

Worked Example (Distinct Roots):

Problem: Solve the recurrence relation $a_n = a_{n-1} + 6a_{n-2}$ for $n \ge 2$, with initial conditions $a_0 = 1$ and $a_1 = 8$.

Solution:

Step 1: Formulate the characteristic equation.
The recurrence is $a_n - a_{n-1} - 6a_{n-2} = 0$. We assume a solution of the form $a_n = r^n$.

Step 2: Find the roots of the characteristic equation.
Factoring the quadratic equation gives:

The roots are distinct: $r_1 = 3$ and $r_2 = -2$.

Step 3: Write the general form of the solution.
Since the roots are distinct, the general solution is:

Step 4: Use the initial conditions to find the constants $\alpha_1$ and $\alpha_2$.
For $n=0$:

For $n=1$:

We now have a system of two linear equations. Multiplying equation (1) by 2 and adding it to equation (2) gives:



Substituting $\alpha_1 = 2$ into equation (1) gives:

Step 5: State the final closed-form solution.

Answer: The solution is $\boxed{a_n = 2 \cdot 3^n - (-2)^n}$.

Case B: Repeated Roots

If a root $r_1$ of the characteristic equation has multiplicity $m$, then the part of the general solution corresponding to this root is:

This polynomial in $n$ is multiplied by $r_1^n$. The same principle applies to all repeated roots.

---

---

2. Linear Non-Homogeneous Recurrence Relations

A linear non-homogeneous recurrence relation with constant coefficients has the form:

The term $f(n)$ is the non-homogeneous part. The solution to such a relation is the sum of two parts:

where $a_n^{(h)}$ is the solution to the associated homogeneous recurrence (i.e., with $f(n)=0$), and $a_n^{(p)}$ is a particular solution that depends on the form of $f(n)$.

Finding $a_n^{(h)}$ is done using the characteristic equation method described previously. To find $a_n^{(p)}$, we use the method of undetermined coefficients, where we guess a solution form for $a_n^{(p)}$ that mirrors $f(n)$.

| Form of $f(n)$ | Guess for Particular Solution $a_n^{(p)}$ |
| :------------------------------------------------- | :---------------------------------------- |
| Constant, $C$ | Constant, $A$ |
| Polynomial in $n$ of degree $d$, $P(n)$ | Polynomial in $n$ of degree $d$ |
| Exponential, $C \cdot s^n$ | $A \cdot s^n$ |
| Polynomial $\times$ Exponential, $P(n) \cdot s^n$ | (Polynomial of degree $d$) $\cdot s^n$ |

Worked Example (Non-Homogeneous):

Problem: Find the asymptotic behavior of $T(n) = 2T(n-1) + n2^n$ for $n>0$, with $T(0)=1$.

Solution:

Step 1: Find the solution to the associated homogeneous recurrence.
The homogeneous part is $T(n) - 2T(n-1) = 0$. The characteristic equation is:

The homogeneous solution is $T_n^{(h)} = \alpha_1 (2^n)$.

Step 2: Determine the form of the particular solution.
The non-homogeneous part is $f(n) = n2^n$, which is a polynomial of degree 1 multiplied by an exponential term $2^n$. The base of the exponential term, $s=2$, matches the characteristic root $r=2$. This is a root collision.

Our initial guess would be $(An+B)2^n$. Because $s=2$ is a characteristic root of multiplicity $m=1$, we must multiply our guess by $n^m = n^1 = n$.
The correct form for the particular solution is:

Step 3: Substitute the particular solution into the original recurrence to find the coefficients.

Divide the entire equation by $2^{n-1}$:

Simplifying by canceling terms:

For this equation to hold for all $n$, the coefficients of the powers of $n$ must be zero.
Coefficient of $n$:

Constant term:

Step 4: Write the particular and general solutions.
The particular solution is:

The general solution is $T(n) = T_n^{(h)} + T_n^{(p)}$:

(Finding $\alpha_1$ using $T(0)=1$ is possible but not required for asymptotic analysis).

Step 5: Determine the asymptotic behavior.
The general solution is dominated by the term with the highest growth rate. Comparing $\alpha_1 2^n$ with $\frac{n(n+1)}{2}2^n$, the latter term, which is $\Theta(n^2 2^n)$, grows faster.

Answer: $\boxed{T(n) = \Theta(n^2 2^n)}$.

---

3. Divide-and-Conquer Recurrences: The Master Theorem

Many recursive algorithms follow a divide-and-conquer strategy, leading to recurrences of a specific form. The Master Theorem provides a "cookbook" method for solving such recurrences.

Worked Example (Master Theorem):

Problem: Analyze the recurrence $T(n) = 3T(n/4) + n \log n$.

Solution:

Step 1: Identify the parameters $a, b,$ and $f(n)$.
From the recurrence, we have:
$a = 3$
$b = 4$
$f(n) = n \log n$

Step 2: Calculate the critical exponent $c_{crit} = \log_b a$.

Step 3: Compare $f(n)$ with $n^{c_{crit}}$.
We are comparing $f(n) = n \log n$ with $n^{\log_4 3}$.
Clearly, $n \log n$ grows faster than $n^{0.792}$.
Formally, $f(n) = n \log n = \Omega(n^{\log_4 3 + \epsilon})$ for some $\epsilon > 0$. For instance, we can choose $\epsilon = 1 - 0.792 = 0.208$, since $n \log n = \Omega(n^1)$. This points us to Case 3.

Step 4: Verify the regularity condition for Case 3.
We must check if $a f(n/b) \le c f(n)$ for some $c < 1$.

We need to show that $\frac{3}{4} n \log n - \frac{3}{4} n \log 4 \le c \cdot n \log n$ for some $c < 1$.
For large $n$, the $n \log n$ term dominates. We can see that the leading coefficient is $3/4$, which is less than 1. So, we can choose $c = 3/4$ (or any value between $3/4$ and 1), and the condition holds for sufficiently large $n$.

Step 5: Apply the conclusion of Case 3.
Since the conditions for Case 3 are met, the solution is $T(n) = \Theta(f(n))$.

Answer: $\boxed{T(n) = \Theta(n \log n)}$.

---

---

4. Transformation of Variables (Substitution Method)

Some recurrence relations do not fit the standard forms but can be transformed into one by a suitable change of variables. This is a powerful technique for unusual arguments like $\sqrt{n}$ or $\log n$.

The general strategy is to define a new sequence $S(k)$ in terms of $T(n)$ by substituting $n$ with an expression involving $k$, typically $n=2^k$.

Worked Example (Transformation):

Problem: Solve the recurrence $T(n) = \sqrt{n}T(\sqrt{n}) + n$ for $n > 1$, with $T(2)=1$.

Solution:

Step 1: Introduce a change of variables.
The argument $\sqrt{n}$ suggests a substitution that simplifies repeated square roots. Let $n = 2^m$. This implies $m = \log_2 n$.
The recurrence becomes:

Step 2: Define a new sequence to simplify the relation further.
Let $S(m) = T(2^m)$. The recurrence in terms of $S$ is:

This form is still not standard. Let us divide the entire equation by $2^m$:

Step 3: Introduce a second change of variables.
Let $U(m) = \frac{S(m)}{2^m}$. The recurrence now becomes:

This is a very common recurrence relation.

Step 4: Solve the simplified recurrence.
By expansion (or Master Theorem), we can solve $U(m) = U(m/2) + 1$.

The recursion stops when $m/2^k$ is a small constant, say $1$. Then $m=2^k$, so $k=\log_2 m$.
Thus, $U(m) = \Theta(\log m)$.

Step 5: Substitute back to find the solution for $T(n)$.
First, substitute back for $S(m)$:

Next, substitute back for $T(n)$:
$S(m) = T(2^m) = T(n)$.
$m = \log_2 n$.
So,

Answer: $\boxed{T(n) = \Theta(n \log \log n)}$.

---

Problem-Solving Strategies

---

Common Mistakes

---

Practice Questions

:::question type="MCQ" question="A sequence is defined by the recurrence relation $a_n = 2a_{n-1} - a_{n-2}$ for $n \ge 2$, with $a_0 = 3$ and $a_1 = 5$. What is the value of $a_{10}$?" options=["15","23","25","21"] answer="23" hint="This is a linear homogeneous recurrence. Find the characteristic equation and check for repeated roots." solution="
Step 1: Form the characteristic equation.
The recurrence is $a_n - 2a_{n-1} + a_{n-2} = 0$.
The characteristic equation is:

Step 2: Find the roots.

We have a repeated root $r_1 = r_2 = 1$ with multiplicity 2.

Step 3: Write the general solution for repeated roots.

This is an arithmetic progression.

Step 4: Use initial conditions to find the constants.

Step 5: Write the closed-form solution.

Step 6: Calculate $a_{10}$.

Answer: \boxed{23}
"
:::

:::question type="NAT" question="Consider the recurrence relation $T(n) = 8T(n/2) + n^3 \log n$. If the solution is given by $T(n) = \Theta(n^k \log^p n)$, what is the value of $k+p$?" answer="5" hint="Use the Master Theorem. Identify $a, b,$ and $f(n)$ and determine which case applies." solution="
Step 1: Identify parameters for the Master Theorem.
$a = 8$, $b = 2$, $f(n) = n^3 \log n$.

Step 2: Calculate the critical exponent.

Step 3: Compare $f(n)$ with $n^{c_{crit}}$.
We compare $f(n) = n^3 \log n$ with $n^3$.
We see that $f(n) = \Theta(n^3 \log^1 n) = \Theta(n^{c_{crit}} \log^1 n)$.

Step 4: Apply the appropriate case of the Master Theorem.
This fits the extended Case 2, where $f(n) = \Theta(n^{c_{crit}} \log^k n)$ with $k=1$.
The solution is $T(n) = \Theta(n^{c_{crit}} \log^{k+1} n)$.
Substituting our values, we get:

Step 5: Determine the values of $k$ and $p$.
Comparing $\Theta(n^3 \log^2 n)$ with the given form $\Theta(n^k \log^p n)$, we have:
$k = 3$
$p = 2$

Step 6: Calculate the final result.

Answer: \boxed{5}
"
:::

:::question type="MCQ" question="What is the solution to the recurrence $T(n) = 3T(n-1) + 4^n$ for $n \ge 1$, with $T(0)=1$?" options=["$T(n) = 4^{n+1} - 3^{n+1}$","$T(n) = 5 \cdot 3^n - 4 \cdot 4^n$","$T(n) = 2 \cdot 4^n - 3^n$","$T(n) = 4^n$"] answer="$T(n) = 4^{n+1} - 3^{n+1}$" hint="This is a linear non-homogeneous recurrence. Find the homogeneous and particular solutions separately, then combine them using the initial condition." solution="
Step 1: Solve the homogeneous part $T_n^{(h)}$.
The characteristic equation for $T(n) - 3T(n-1) = 0$ is $r-3=0$, so $r=3$.

Step 2: Find the particular solution $T_n^{(p)}$.
The non-homogeneous term is $f(n) = 4^n$. The base $s=4$ is not a characteristic root.
So, we guess a particular solution of the form $T_n^{(p)} = A \cdot 4^n$.
Substitute this into the recurrence:

Divide by $4^{n-1}$:


So, $T_n^{(p)} = 4 \cdot 4^n = 4^{n+1}$.

Step 3: Write the general solution.

Step 4: Use the initial condition $T(0)=1$ to find $\alpha_1$.

Step 5: State the final solution.

Answer: \boxed{T(n) = 4^{n+1} - 3^{n+1}}
"
:::

:::question type="MSQ" question="A recurrence is defined as $f(n) = f(\lfloor n/3 \rfloor) + f(\lceil n/3 \rceil) + n$ for $n \ge 3$, with $f(1)=1, f(2)=2$. Which of the following statements are TRUE?" options=["$f(n) = \Omega(n \log n)$","$f(n) = O(n^2)$","$f(n) = \Theta(n)$","$f(n) = \Theta(n (\log n)^2)$"] answer="A,B" hint="This recurrence is similar to Merge Sort's recurrence. Analyze its behavior using a recursion tree or by comparing it to a standard form like $T(n) = 2T(n/3) + n$." solution="
Let's analyze the recurrence using a recursion tree.
At the root, the cost is $n$.
At the next level, the sum of the non-recursive costs from the two subproblems is $\lfloor n/3 \rfloor + \lceil n/3 \rceil = n$.
This pattern continues down the tree. At each level, the total work done (excluding recursive calls) sums to $n$.
The depth of the recursion tree is $\log_3 n$.
The total cost is the sum of work at each level, which is (depth) $\times$ (work per level).
Total cost $= \log_3 n \cdot n = \Theta(n \log n)$.
So, $f(n) = \Theta(n \log n)$.

Let's check the options based on $f(n) = \Theta(n \log n)$:
A. $f(n) = \Omega(n \log n)$: True, since $\Theta(n \log n)$ implies $f(n)$ is bounded below by $n \log n$.
B. $f(n) = O(n^2)$: True, since $n \log n$ grows slower than $n^2$.
C. $f(n) = \Theta(n)$: False, as $n \log n$ grows faster than $n$.
D. $f(n) = \Theta(n (\log n)^2)$: False, as $n \log n$ grows slower than $n (\log n)^2$.

Therefore, statements A and B are correct.
Answer: \boxed{A,B}
"
:::

---

Summary

---

What's Next?

---

---

Part 3: Generating Functions

Introduction

Generating functions provide a powerful and elegant algebraic method for solving a wide variety of counting problems in combinatorics. At its core, a generating function is a formal power series whose coefficients encode a sequence of numbers. Instead of working with the sequence directly, we manipulate the compact, closed-form expression of the power series. This abstraction allows us to solve complex problems, such as finding the number of integer solutions to an equation with constraints or partitioning integers, by using standard algebraic operations like multiplication and differentiation.

For the GATE examination, a foundational understanding of generating functions is valuable for certain advanced combinatorial problems. The primary focus is on translating a counting problem into its corresponding generating function, manipulating the function to find a specific coefficient, and interpreting that coefficient as the solution to the original problem. We will primarily concern ourselves with Ordinary Generating Functions (OGFs), which are used for problems involving combinations or selections of indistinguishable objects.

---

---

---

Key Concepts

1. Representing Sequences with Closed-Form Expressions

The utility of generating functions arises from our ability to represent infinite power series with compact, finite expressions known as closed forms. The most fundamental of these is the geometric series.

Consider the sequence $(1, 1, 1, \dots)$, where $a_n = 1$ for all $n \ge 0$. Its generating function is:

This is a geometric series with first term 1 and common ratio $x$. For $|x| < 1$, this series converges to a simple closed form. In the context of formal power series, we use this identity without concern for convergence.

Another crucial identity is the Binomial Theorem, particularly its generalized form.

---

2. Application to Combinatorial Problems

The primary application in the GATE context is solving problems that can be modeled as finding the number of non-negative integer solutions to an equation with constraints.

Let us consider the problem of finding the number of integer solutions to the equation:

subject to certain constraints on each $e_i$. We can model this problem by constructing a generating function where each variable $e_i$ corresponds to a polynomial factor. The exponents in each factor represent the allowed values for that variable. The number of solutions is then the coefficient of $x^n$ in the product of these factors.

Let $P_i(x)$ be the polynomial (or series) representing the choices for $e_i$. Then the overall generating function is:

The answer to the problem is $[x^n]G(x)$.

Worked Example:

Problem: Find the number of non-negative integer solutions to the equation $e_1 + e_2 + e_3 = 5$.

Solution:

Step 1: Define the constraints and corresponding polynomials for each variable.
For each variable $e_i$, the allowed values are $\{0, 1, 2, 3, \dots\}$. The generating function for the choices of a single variable is therefore:

Step 2: Construct the total generating function for the equation.
Since there are three variables ($e_1, e_2, e_3$) with the same constraints, the total generating function $G(x)$ is the product of their individual generating functions.

Step 3: Find the coefficient of $x^5$ in the expansion of $G(x)$.
We need to find $[x^5](1-x)^{-3}$. Using the generalized binomial theorem, we know that the coefficient of $x^n$ in $(1-x)^{-k}$ is $\binom{n+k-1}{n}$.

Here, $n=5$ and $k=3$.

Step 4: Compute the final value.

Answer: There are 21 non-negative integer solutions.

---

Problem-Solving Strategies

---

Practice Questions

:::question type="MCQ" question="Which of the following expressions is the generating function for the number of ways to choose $n$ items from three distinct types, subject to the constraints that we must choose an even number of the first type, an odd number of the second type, and any number of the third type?" options=["$\frac{x}{(1-x^2)^2(1-x)}$","$\frac{x}{(1-x^2)(1-x)^2}$","$\frac{1}{(1-x^2)(1-x)}$","$\frac{x}{(1-x^2)(1-x)}$"] answer="$\frac{x}{(1-x^2)^2(1-x)}$" hint="Construct the generating function for each constraint separately and then multiply them together." solution="
Step 1: Determine the generating function for the first type (even number of items).
The allowed number of items is $\{0, 2, 4, \dots\}$. The corresponding series is $x^0 + x^2 + x^4 + \dots$.
This is a geometric series with first term 1 and common ratio $x^2$.

Step 2: Determine the generating function for the second type (odd number of items).
The allowed number of items is $\{1, 3, 5, \dots\}$. The corresponding series is $x^1 + x^3 + x^5 + \dots$.
We can factor out $x$ to get $x(1 + x^2 + x^4 + \dots)$.

Step 3: Determine the generating function for the third type (any number of items).
The allowed number of items is $\{0, 1, 2, \dots\}$. The corresponding series is $1 + x + x^2 + \dots$.

Step 4: Multiply the individual generating functions to get the total generating function.
The total generating function $G(x)$ is the product $P_1(x)P_2(x)P_3(x)$.

Result: The correct expression is $\frac{x}{(1-x^2)^2(1-x)}$.
"
:::

:::question type="NAT" question="Find the number of ways to distribute 10 identical candies to 4 children such that each child receives at least one candy." answer="84" hint="This is equivalent to finding the number of positive integer solutions to $c_1+c_2+c_3+c_4=10$. Model this with a generating function where each factor is of the form $(x+x^2+x^3+\dots)$." solution="
Step 1: Formulate the problem as an integer solution equation.
Let $c_i$ be the number of candies received by child $i$. The problem is to find the number of integer solutions to:

with the constraint that $c_i \ge 1$ for $i=1, 2, 3, 4$.

Step 2: Construct the generating function for a single child.
Since each child must receive at least one candy, the choices for each $c_i$ are $\{1, 2, 3, \dots\}$. The generating function for one child is:

Step 3: Construct the total generating function for the problem.
Since there are 4 children with identical constraints, the total generating function $G(x)$ is $[P(x)]^4$.

Step 4: Identify the required coefficient.
We need to find the number of ways to get a total of 10 candies, which is the coefficient of $x^{10}$ in $G(x)$.

This is equivalent to finding the coefficient of $x^{10-4} = x^6$ in the expansion of $(1-x)^{-4}$.

Step 5: Apply the generalized binomial theorem.
The coefficient of $x^n$ in $(1-x)^{-k}$ is $\binom{n+k-1}{n}$. Here, $n=6$ and $k=4$.

Step 6: Calculate the final value.

Answer: $\boxed{84}$
"
:::

---

---

Summary

---

What's Next?

Chapter Summary

---

Chapter Review Questions

:::question type="MCQ" question="How many integers between 1 and 1000 (inclusive) are divisible by neither 5 nor 7?" options=["686","714","286","700"] answer="A" hint="Use the Principle of Inclusion-Exclusion to find the number of integers that are divisible by at least one of the numbers, and subtract this from the total." solution="
Let $S$ be the set of integers from 1 to 1000. We have $|S| = 1000$.
Let $A$ be the set of integers in $S$ divisible by 5.
Let $B$ be the set of integers in $S$ divisible by 7.

We want to find the number of integers that are in neither $A$ nor $B$, which is given by $|S| - |A \cup B|$.
Using the Principle of Inclusion-Exclusion, we know that $|A \cup B| = |A| + |B| - |A \cap B|$.

Calculate $|A|$, the number of integers divisible by 5:

Calculate $|B|$, the number of integers divisible by 7:

Calculate $|A \cap B|$, the number of integers divisible by both 5 and 7 (i.e., by their LCM, which is 35):

Now, we find the number of integers divisible by at least one of them:

Finally, the number of integers divisible by neither 5 nor 7 is:

Thus, the correct option is A.
"
:::

:::question type="NAT" question="Consider the recurrence relation $a_n = 5a_{n-1} - 6a_{n-2}$ with initial conditions $a_0 = 1$ and $a_1 = 4$. What is the value of $a_5$?" answer="454" hint="First, find the general solution to this linear homogeneous recurrence relation using its characteristic equation. Then, use the initial conditions to find the specific constants." solution="
The given recurrence relation is a second-order linear homogeneous relation with constant coefficients:

Form the characteristic equation: We substitute $a_n = r^n$ into the relation to get:

Find the roots of the characteristic equation: Factoring the quadratic equation, we get:

The roots are $r_1 = 2$ and $r_2 = 3$.

Write the general solution: Since the roots are distinct, the general solution is of the form:

Use the initial conditions to find the constants $c_1$ and $c_2$:

For $n=0$, we have $a_0 = 1$:

For $n=1$, we have $a_1 = 4$:

Solve the system of linear equations: Multiply Eq. 1 by 2 to get $2c_1 + 2c_2 = 2$. Subtract this from Eq. 2: $(2c_1 + 3c_2) - (2c_1 + 2c_2) = 4 - 2 \implies c_2 = 2$. Substitute $c_2 = 2$ back into Eq. 1: $c_1 + 2 = 1 \implies c_1 = -1$.

Write the specific solution: The solution to the recurrence relation is:

Calculate $a_5$: Substitute $n=5$ into the specific solution:

Alternatively, we can compute the terms iteratively:

"
:::

:::question type="MCQ" question="A committee of 4 people is to be formed from a group of 5 men and 4 women. In how many ways can this be done if the committee must contain at least one woman?" options=["126","120","121","125"] answer="C" hint="Use the complementary counting technique. Calculate the total number of ways to form the committee without any restrictions, and then subtract the single case that violates the condition." solution="
The total number of people is $5$ men $+ 4$ women $= 9$ people. The size of the committee to be formed is 4.

We will use the principle of complementary counting, which is often simpler for problems involving 'at least one' constraints. The total number of ways to form the committee minus the number of ways that violate the condition gives the desired result.

Calculate the total number of ways to form a committee of 4 from 9 people, without any restrictions:

Identify and calculate the number of ways for the case that violates the condition:

The condition is that the committee must contain 'at least one woman'. The only composition that violates this condition is a committee containing zero women (i.e., a committee composed entirely of men).

Calculate the number of ways to form a committee of 4 using only men:

We need to choose 4 men from the available 5 men.

Subtract the violating case from the total:

The number of ways to form a committee with at least one woman is:

Thus, the correct option is C.
"
:::

---

What's Next?