Combinatorics

Overview

In the study of computer science, we are fundamentally concerned with discrete structures and the algorithms that operate upon them. Combinatorics, the branch of mathematics dealing with the enumeration, combination, and permutation of sets of elements, provides the essential language and toolkit for this analysis. It is the art and science of counting—not merely by listing, but by developing systematic methods to determine the number of possible outcomes or arrangements under specified constraints. A firm grasp of combinatorial techniques is therefore indispensable for the analysis of algorithms, the design of data structures, and the understanding of discrete probability, all of which are central to the GATE syllabus.

This chapter is structured to build a comprehensive understanding of combinatorial problem-solving, from foundational principles to more advanced methodologies. We begin with the fundamental Counting Principles, including the sum and product rules, permutations, and combinations, which form the bedrock of all enumeration. Subsequently, we shall explore Recurrence Relations, a powerful formalism for describing sequences and problems that possess a recursive structure, such as the complexity analysis of many divide-and-conquer algorithms. The solution of these relations, particularly linear recurrences of the form $a_n = c_1 a_{n-1} + c_2 a_{n-2} + \dots$, is a frequently tested skill.

Finally, we introduce the concept of Generating Functions. This advanced technique provides a unified and elegant algebraic framework for solving complex counting problems and recurrence relations. By encoding a sequence of numbers as the coefficients of a formal power series, we can manipulate the series to extract information that might be difficult to obtain through direct combinatorial arguments. Mastery of the topics presented herein is not merely an academic exercise; it is a prerequisite for tackling a significant portion of questions in the Engineering Mathematics and Discrete Mathematics sections of the GATE examination.

---

Chapter Contents

| # | Topic | What You'll Learn |
|---|-------|-------------------|
| 1 | Counting Principles | Mastering fundamental rules for counting objects. |
| 2 | Recurrence Relations | Solving problems using recursive definitions/methods. |
| 3 | Generating Functions | Using power series to solve enumerations. |

---

Learning Objectives

After completing this chapter, you will be able to:

Apply the sum and product rules, permutations, and combinations represented by $\binom{n}{k}$, to solve fundamental counting problems.

Formulate recurrence relations for combinatorial problems and solve linear homogeneous and non-homogeneous recurrence relations using characteristic equations.

Utilize the Principle of Inclusion-Exclusion and the Pigeonhole Principle to address more complex enumeration scenarios.

Employ generating functions to model and solve intricate counting problems and recurrence relations.

---

We now turn our attention to Counting Principles...
## Part 1: Counting Principles

Key Definitions

---

Essential Formulas

This framework is critical for solving a wide variety of distribution problems. Identify if items (balls) and containers (bins) are distinct or identical.

| Items ($k$) | Bins ($n$) | Any # per bin | $\geq 1$ per bin |
|--------------|------------|-----------------|----------------|
| Distinct | Distinct | $n^k$ | $\sum_{i=0}^{n} (-1)^i \binom{n}{i} (n-i)^k$ |
| Identical| Distinct| $\binom{n+k-1}{k}$ | $\binom{k-1}{n-1}$ |
| Distinct | Identical| $\sum_{i=1}^n S(k,i)$ | $S(k,n)$ |
| Identical| Identical| Partitions of $k$ into at most $n$ parts | Partitions of $k$ into exactly $n$ parts |

Note: $S(k,n)$ is the Stirling Number of the Second Kind. The formula in the first row is the PIE application for surjective functions.

---

Must Remember

Distinct or Identical? First, classify the items being counted (balls) and the containers they are placed into (bins). This is the most crucial step.

Order Matters? If the order of selection or arrangement creates a new outcome, use Permutations. If not, use Combinations.

Use Complementary Counting: For "at least one" problems, it is often simpler to calculate the total number of cases and subtract the number of cases where the condition is not met ("none").

Element-by-Element Choices: For problems involving subsets or properties (e.g., forming pairs $(A,B)$ such that $A \subseteq B$), consider the choices available for each individual element of the universal set. For an element $x$, it can be in $A$ and $B$, in $B$ but not $A$, or in neither.

---

Common Mistakes

❌ Permutation vs. Combination: Using $\binom{5}{3}$ to find the number of 3-digit numbers from {1,2,3,4,5} without repetition. The order of digits matters (123 $\neq$ 321).
✅ Correct: This is an arrangement, so use Permutation: $P(5,3) = \frac{5!}{2!} = 60$.

❌ Identical vs. Distinct Items in Bins: Counting ways to distribute 5 identical chocolates to 3 distinct children as $3^5$. This formula is for distinct items.
✅ Correct: This is "identical items, distinct bins" (Stars and Bars). Use $\binom{3+5-1}{5} = \binom{7}{5} = 21$.

❌ Forgetting Constraints: When distributing 5 identical items into 3 distinct bins such that no bin is empty, using the standard Stars and Bars formula.
✅ Correct: First, place one item in each bin. Then distribute the remaining $5-3=2$ items normally: $\binom{3+2-1}{2} = \binom{4}{2} = 6$. This is equivalent to $\binom{k-1}{n-1}$.

---

Quick Practice

type="MCQ" question="How many binary strings of length 8 are there that start with a '1' or end with '00'?" options=["160", "156", "192", "128"] answer="160" hint="Use the Principle of Inclusion-Exclusion: $|A \cup B| = |A| + |B| - |A \cap B|$." solution="Let A be the set of strings starting with '1'. The first bit is fixed, the other 7 can be anything. So, $|A| = 2^7 = 128$.
Let B be the set of strings ending with '00'. The last two bits are fixed, the other 6 can be anything. So, $|B| = 2^6 = 64$.
$A \cap B$ is the set of strings starting with '1' AND ending with '00'. The first bit and last two bits are fixed. The remaining $8-1-2=5$ bits can be anything. So, $|A \cap B| = 2^5 = 32$.
By PIE,

Answer: \boxed{160}"

type="NAT" question="In how many ways can 5 distinct research papers be assigned to 3 identical review panels such that each panel receives at least one paper?" answer="25" hint="This is a problem of partitioning a set of distinct items into a fixed number of non-empty identical subsets. This maps directly to a specific counting number." solution="This is a direct application of Stirling Numbers of the Second Kind, $S(k,n)$, for distributing $k$ distinct items into $n$ identical bins with no bin empty. Here, $k=5$ and $n=3$.
The recurrence relation is

We need to calculate $S(5,3)$.

We need to calculate the base values:
$S(n,1) = 1$, $S(n,n) = 1$.



Finally,

Answer: \boxed{25}"

---

Remember

> The foundation of all counting is breaking down a problem into two questions: (1) Are the items/positions distinct or identical? (2) Does the order of selection matter?

See full notes for detailed explanations!

---

---

Part 2: Recurrence Relations

Key Definitions

An equation that defines a sequence recursively, where each term is a function of preceding terms. Example: The Fibonacci sequence $F(n) = F(n-1) + F(n-2)$.

---

Essential Formulas

The two primary methods for solving common recurrence relations are the Characteristic Equation method for linear recurrences and the Master Theorem for divide-and-conquer recurrences.

| Case | Condition on $f(n)$ | Asymptotic Solution $T(n)$ |
|---|---|---|
| Case 1 | $f(n) = O(n^{\log_b a - \epsilon})$ for some $\epsilon > 0$ | $\Theta(n^{\log_b a})$ |
| Case 2 | $f(n) = \Theta(n^{\log_b a} \log^k n)$ for some $k \ge 0$ | $\Theta(n^{\log_b a} \log^{k+1} n)$ |
| Case 3 | $f(n) = \Omega(n^{\log_b a + \epsilon})$ for some $\epsilon > 0$, AND the regularity condition holds: $a f(n/b) \le c f(n)$ for some constant $c < 1$ and large $n$. | $\Theta(f(n))$ |

---

Must Remember

Identify the Recurrence Type:

* Linear: Form $c_0 a_n + c_1 a_{n-1} + \dots = F(n)$. Use the characteristic equation method.
* Divide and Conquer: Form $T(n) = aT(n/b) + f(n)$. Use the Master Theorem.
* Non-standard: Form $T(n) = T(\sqrt{n}) + \dots$. Use substitution (e.g., let $n=2^k$ or $n=2^{2^k}$).

Solving Non-Homogeneous Relations: For $a_n = (\text{LHRR part}) + F(n)$, the total solution is $a_n = a_n^{(h)} + a_n^{(p)}$.

* $a_n^{(h)}$ is the solution to the homogeneous part.
* $a_n^{(p)}$ is the particular solution. Guess its form based on $F(n)$.

The Particular Solution Trap: If your guess for the particular solution $a_n^{(p)}$ is already part of the homogeneous solution $a_n^{(h)}$, you must multiply your guess by $n^m$, where $m$ is the multiplicity of the corresponding root in the characteristic equation.

Dominant Term: For asymptotic analysis of LHRRs, the complexity is determined by the root with the largest absolute value. If $|r_{max}|$ is the largest magnitude root, the complexity is $\Theta(|r_{max}|^n)$.

---

Common Mistakes

---

Quick Practice

type="MCQ" question="A recurrence relation is defined by $T(n) = 6T(n-1) - 9T(n-2)$ for $n \ge 2$, with initial conditions $T(0) = 1$ and $T(1) = 6$. What is the asymptotic bound for $T(n)$?" options=["$\Theta(3^n)$","$\Theta(n 3^n)$","$\Theta(n^2 3^n)$","$\Theta(6^n)$"] answer="$\Theta(n 3^n)$" hint="Form the characteristic equation and check for repeated roots." solution="The characteristic equation is

which is

This gives a repeated root $r=3$ with multiplicity 2. The general solution is

Using initial conditions:


The solution is

The dominant term is $n3^n$, so the complexity is $\Theta(n3^n)$.
Answer: \boxed{\Theta(n3^n)}"

type="NAT" question="Consider the recurrence $T(n) = T(n-1) + 2n - 1$ for $n \ge 1$, with the base case $T(0) = 0$. Calculate the value of $T(10)$." answer="100" hint="Unfold the recurrence or recognize the sum. $T(n) = \sum_{i=1}^{n} (2i-1)$." solution="This recurrence represents the sum of the first $n$ odd integers. The sum of the first $n$ odd integers is $n^2$.

...

Therefore,

Answer: \boxed{100}"

---

Remember

> First, classify the recurrence relation (Linear, Divide-and-Conquer, or Other). Then, apply the corresponding standard technique systematically.

See full notes for detailed derivations and more complex examples!

---

---

Part 3: Generating Functions

Key Definitions

An Ordinary Generating Function (OGF) for an infinite sequence $\{a_0, a_1, a_2, \dots\}$ is a formal power series where the coefficient of $x^n$ is the $n$-th term of the sequence, $a_n$. It acts as a "clothesline" for the sequence.

The OGF $A(x)$ is defined as:

Here, $x$ is a formal variable, not a number to be evaluated.

---

Essential Formulas

The core of using generating functions is recognizing and manipulating their closed-form representations.

---

Must Remember

Operations on generating functions correspond directly to operations on their sequences. This is their primary utility. Let $A(x) \leftrightarrow \{a_n\}$ and $B(x) \leftrightarrow \{b_n\}$.

Addition/Subtraction: Adding two generating functions corresponds to adding their respective sequences term by term.

Multiplication (Convolution): Multiplying two generating functions results in a new generating function whose coefficients are the convolution of the original sequences. This is the most powerful tool for solving partition and combination problems.

* Example: Finding the number of ways to make change for $n$ cents using pennies and nickels. The GF for pennies is $(1+x+x^2+\dots)$ and for nickels is $(1+x^5+x^{10}+\dots)$. The product's $x^n$ coefficient gives the answer.

Finding a specific coefficient: The primary goal is often finding $[x^n]A(x)$, which means "the coefficient of $x^n$ in the series expansion of $A(x)$". This coefficient is the answer to a counting problem for size $n$.

---

Common Mistakes

---

Quick Practice

type="NAT" question="A problem can be modeled by finding the coefficient of $x^{10}$ in the expansion of the generating function $A(x) = (\frac{1}{1-x})^4$. What is the numerical value of this coefficient?" answer="286" hint="This is equivalent to finding the number of non-negative integer solutions to $e_1+e_2+e_3+e_4 = 10$. Use the formula for the coefficient of $x^n$ in $(1-x)^{-k}$." solution="We need to find $[x^{10}]$ in $(1-x)^{-4}$. The formula for the coefficient of $x^n$ in the expansion of $(1-x)^{-k}$ is $\binom{n+k-1}{k-1}$. Here, $n=10$ and $k=4$.
The coefficient is

Answer: \boxed{286}"

type="MCQ" question="Which generating function models the problem of selecting $n$ items from three distinct types, where the first type must be selected an even number of times, the second an odd number of times, and the third any number of times?" options=["$\frac{1}{(1-x^2)(1-x)}$","$\frac{x}{(1-x^2)(1-x)}$","$\frac{x}{(1-x)^2(1+x)^3}$","$\frac{x}{(1-x)^3(1+x)^2}$"] answer="$\frac{x}{(1-x)^3(1+x)^2}$" hint="Construct the generating function for each constraint separately and multiply them together. The GF for even powers is $1/(1-x^2)$ and for odd powers is $x/(1-x^2)$." solution="GF for even selections (type 1):

GF for odd selections (type 2):

GF for any number of selections (type 3):

The combined generating function is the product:

Simplifying the denominator:

Thus,

Answer: \boxed{\frac{x}{(1-x)^3(1+x)^2}}"

---

Remember

> Generating functions transform complex combinatorial counting problems into problems of algebraic manipulation of power series. Your goal is almost always to find the coefficient of $x^n$.

See full notes for detailed explanations!

---

Chapter Summary

In this chapter, we have explored the fundamental principles of counting and their application in solving complex problems. A thorough understanding of these concepts is indispensable for success in the GATE examination. The most critical points to retain are as follows:

• The Fundamental Principles of Counting: We have established that the Sum and Product Rules are the foundational axioms upon which combinatorial analysis is built. The ability to correctly identify whether a scenario requires addition (for disjoint choices) or multiplication (for sequential tasks) is a primary skill.

• Permutations and Combinations: We have drawn a clear distinction between arrangements where order matters (permutations) and selections where it does not (combinations). Mastery of the associated formulas, including those for arrangements with repetitions and circular permutations, is essential for a wide range of problems. The core formulas are $P(n, k) = \frac{n!}{(n-k)!}$ and $C(n, k) = \binom{n}{k} = \frac{n!}{k!(n-k)!}$.

• The Principle of Inclusion-Exclusion: For counting problems involving non-disjoint sets, we have seen that a simple application of the Sum Rule is insufficient. The Principle of Inclusion-Exclusion provides a systematic method for handling such cases by alternately adding and subtracting the cardinalities of intersecting sets.

• Recurrence Relations: We have learned to model counting problems recursively, defining a term in a sequence based on its predecessors. A key technique introduced was the solution of linear homogeneous recurrence relations with constant coefficients by finding the roots of the characteristic equation.

• Generating Functions: We have introduced generating functions as a powerful algebraic tool for solving counting problems and recurrence relations. A sequence $\{a_n\}$ can be encoded as a power series $G(x) = \sum_{n=0}^{\infty} a_n x^n$, transforming a combinatorial problem into one of manipulating algebraic expressions. The coefficient of $x^n$ in the resulting series provides the solution $a_n$.

---

Chapter Review Questions

type="MCQ" question="Let $a_n$ denote the number of bit strings of length $n$ that do not contain the substring '11'. Which of the following recurrence relations, along with its initial conditions, correctly describes $a_n$?" options=["$a_n = a_{n-1} + 2a_{n-2}$ for $n \ge 2$; $a_0=1, a_1=2$","$a_n = a_{n-1} + a_{n-2}$ for $n \ge 2$; $a_0=1, a_1=2$","$a_n = 2a_{n-1} - a_{n-2}$ for $n \ge 2$; $a_0=1, a_1=2$","$a_n = a_{n-1} + a_{n-2}$ for $n \ge 2$; $a_0=1, a_1=1$"] answer="B" hint="Consider a valid bit string of length $n$. It can end with either a '0' or a '1'. Analyze the constraints on the prefix of length $n-1$ or $n-2$ in each case." solution="Let $a_n$ be the count of valid bit strings of length $n$. We can construct such a string by considering its last bit.

Case 1: The string ends with '0'.
If the last bit is '0', the prefix of length $n-1$ can be any valid bit string of length $n-1$ that does not contain '11'. The number of such prefixes is, by definition, $a_{n-1}$.

Case 2: The string ends with '1'.
If the last bit is '1', the bit at position $n-1$ cannot be '1' (to avoid the substring '11'). Therefore, the bit at position $n-1$ must be '0'. This means the string must end in '01'. The prefix of length $n-2$ can be any valid bit string of length $n-2$. The number of such prefixes is $a_{n-2}$.

Since these two cases are exhaustive and disjoint, we can use the Sum Rule to write the recurrence relation:

Now, we must establish the initial conditions.

• For $n=0$: The empty string is a valid string. So, $a_0 = 1$.


• For $n=1$: The strings are "0" and "1". Both are valid. So, $a_1 = 2$.

Let's check our recurrence with these values for $n=2$:

The valid strings of length 2 are "00", "01", "10". The invalid string is "11". The count is indeed 3.
Thus, the correct recurrence is $a_n = a_{n-1} + a_{n-2}$ with initial conditions $a_0=1, a_1=2$. This corresponds to the Fibonacci sequence, shifted.
Answer: \boxed{B}"

type="NAT" question="A committee of 5 members is to be formed from a group of 6 men and 4 women. In how many ways can the committee be formed if it must contain at least 2 men and at least 2 women?" answer="180" hint="The constraints are 'at least 2 men' and 'at least 2 women'. Since the committee size is fixed at 5, this leaves only a few specific compositions. Calculate the number of ways for each valid composition and sum them up." solution="
The total number of members is 6 men and 4 women. The committee size is 5.
The constraints are:

Number of men $\ge 2$

Number of women $\ge 2$

Let $m$ be the number of men and $w$ be the number of women in the committee. We must have $m+w=5$.
We can enumerate the possible compositions of the committee that satisfy the given constraints:

Case 1: 2 men and 3 women
The number of ways to choose 2 men from 6 is $\binom{6}{2}$.
The number of ways to choose 3 women from 4 is $\binom{4}{3}$.
Total ways for this case =

Case 2: 3 men and 2 women
The number of ways to choose 3 men from 6 is $\binom{6}{3}$.
The number of ways to choose 2 women from 4 is $\binom{4}{2}$.
Total ways for this case =

Are there any other cases? If we select 4 men, we can only select 1 woman, which violates the 'at least 2 women' constraint. Similarly, if we select 4 women, we can only select 1 man, violating the 'at least 2 men' constraint.

Therefore, the total number of ways to form the committee is the sum of the ways from the two disjoint cases:
Total ways = (Ways for Case 1) + (Ways for Case 2) = $60 + 120 = 180$.
Answer: \boxed{180}"

type="MCQ" question="What is the coefficient of $x^{10}$ in the expansion of the generating function $G(x) = \frac{x^2}{(1-2x)^3}$?" options=["$45 \cdot 2^7$","$55 \cdot 2^8$","$66 \cdot 2^8$","$45 \cdot 2^8$"] answer="D" hint="Recall the generalized binomial theorem, specifically the expansion for $(1-z)^{-k}$. You will need to account for the $x^2$ term in the numerator." solution="
We are asked to find the coefficient of $x^{10}$ in the expression $G(x) = x^2 \cdot (1-2x)^{-3}$.
This is equivalent to finding the coefficient of $x^8$ in the expansion of $(1-2x)^{-3}$.
Using the generalized binomial theorem, we have:

In our problem, we have $z=2x$ and $k=3$. We need the term where the power of $x$ is 8, so we set $n=8$.
The coefficient of $x^n$ in $(1-2x)^{-3}$ is $\binom{n+3-1}{3-1} 2^n = \binom{n+2}{2} 2^n$.
For $n=8$, the coefficient is:

Now, we calculate the binomial coefficient:

Thus, the coefficient is $45 \cdot 2^8$.
Answer: \boxed{D}"

type="NAT" question="In a university, every student must take at least one course from the following three: Computer Science (CS), Electronics (EC), and Mathematics (MA). In a batch of 200 students, it is known that 150 students have taken CS, 100 have taken EC, and 80 have taken MA. If 60 students have taken both CS and EC, 50 have taken both EC and MA, and 70 have taken both CS and MA, how many students have taken all three courses?" answer="30" hint="Use the Principle of Inclusion-Exclusion for three sets. The total number of students in the union of the three sets is given in the problem." solution="
Let $S$ be the set of all students in the batch. Let $C$, $E$, and $M$ be the sets of students who have taken Computer Science, Electronics, and Mathematics, respectively.
We are given the following information:

• Total number of students, $|S| = 200$.


• Every student takes at least one course, so $|C \cup E \cup M| = 200$.


• $|C| = 150$


• $|E| = 100$


• $|M| = 80$


• $|C \cap E| = 60$


• $|E \cap M| = 50$


• $|C \cap M| = 70$

We need to find the number of students who have taken all three courses, which is $|C \cap E \cap M|$.

We use the Principle of Inclusion-Exclusion for three sets:

Substituting the given values into the formula:



Solving for $|C \cap E \cap M|$:

Therefore, 30 students have taken all three courses.
Answer: \boxed{30}"

---

What's Next?

Combinatorics is a foundational pillar of discrete mathematics, with profound implications across computer science and engineering. As you advance, you will find these principles interwoven with other critical areas:

• Set Theory: The concepts of permutations and combinations are built upon the fundamental definitions and operations of set theory, providing a quantitative lens to analyze set structures.
• Probability: Combinatorial techniques are indispensable for calculating probabilities, especially in discrete probability spaces where outcomes are finite and equally likely. Understanding "how many ways" an event can occur is the first step to determining "how likely" it is.
• Analysis of Algorithms: Recurrence relations are the primary tool for analyzing the time and space complexity of recursive algorithms, particularly those employing divide-and-conquer strategies. Generating functions offer an alternative, often more elegant, method for solving these recurrences.
• Graph Theory: Many graph problems, such as counting paths, cycles, or spanning trees, rely heavily on combinatorial reasoning and techniques.

By mastering combinatorics, you are not just learning to count; you are developing a powerful analytical toolkit that will serve you throughout your studies and career in computer science.