Below is a simple, clear, and exam-oriented explanation of Generating Functions — perfect for BCA/MCA/engineering/discrete mathematics exams.
⭐ Generating Functions – Introduction
A generating function is a powerful tool used in combinatorics and recurrence relations.
It converts a sequence of numbers into a power series, making it easier to analyze or solve.
⭐ Definition
Let ({a_n}) be a sequence.
The generating function of this sequence is:
[
G(x) = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots
]
This is called an ordinary generating function (OGF).
⭐ Why Generating Functions?
Generating functions help in:
✔ Solving recurrence relations
✔ Counting combinatorial objects
✔ Finding closed-form formulas
✔ Summing series
✔ Working with partitions and permutations
✔ Probability problems
They convert complex recurrence problems into simple algebra problems.
⭐ Example 1: Basic Generating Function
Sequence:
[
1, 1, 1, 1, 1, \dots
]
Generating function:
[
G(x) = 1 + x + x^2 + x^3 + \cdots = \frac{1}{1 – x}
]
(Geometric series)
⭐ Example 2: Sequence ({a_n} = n)
[
G(x) = 0 + 1x + 2x^2 + 3x^3 + 4x^4 + \cdots
]
This equals:
[
G(x) = \frac{x}{(1 – x)^2}
]
⭐ Types of Generating Functions
1️⃣ Ordinary Generating Function (OGF)
[
G(x) = \sum_{n=0}^{\infty} a_n x^n
]
2️⃣ Exponential Generating Function
[
G(x) = \sum_{n=0}^{\infty} \frac{a_n x^n}{n!}
]
Used for labeled structures (graphs, permutations).
3️⃣ Probability Generating Function
Used in probability and random variables.
⭐ Solving Recurrence Relations Using Generating Functions
This is one of the most common applications.
⭐ Example 1: Fibonacci Recurrence
Given:
[
F_0 = 0, ; F_1 = 1, ; F_n = F_{n-1} + F_{n-2}
]
Step 1: Write generating function:
[
G(x) = \sum F_n x^n
]
Step 2: Multiply recurrence by (x^n) and sum.
You get:
[
G(x) = \frac{x}{1 – x – x^2}
]
This is the generating function for Fibonacci numbers.
⭐ Example 2: Recurrence
[
a_n = 2a_{n-1}, \quad a_0 = 1
]
Sequence:
[
1, 2, 4, 8, 16, \dots
]
Generating function:
[
G(x) = \sum_{n=0}^{\infty} 2^n x^n
= \frac{1}{1 – 2x}
]
⭐ Operations on Generating Functions
✔ 1. Shifting (index shift)
If
[
G(x) = a_0 + a_1x + a_2x^2 + \cdots
]
Then
[
xG(x) = a_0x + a_1x^2 + a_2x^3 + \cdots
]
Shift right by 1 index.
✔ 2. Differentiation
Differentiating G(x):
[
G'(x) = a_1 + 2a_2x + 3a_3x^2 + \cdots
]
Useful for solving recurrences.
✔ 3. Multiplying by a polynomial
Multiplying by (1 − x) simplifies many problems.
⭐ Generating Functions in Counting Problems
Example:
How many ways to choose items with unlimited repetition?
For each item, the generating function is:
[
1 + x + x^2 + x^3 + \cdots = \frac{1}{1 – x}
]
For k items:
[
\left(\frac{1}{1-x}\right)^k
]
Coefficient of (x^n) gives the number of solutions.
⭐ Example Problem
Find the number of nonnegative integer solutions to:
[
x_1 + x_2 + x_3 = n
]
Each variable has generating function:
[
1 + x + x^2 + x^3 + \cdots = \frac{1}{1 – x}
]
So joint generating function:
[
\left(\frac{1}{1 – x}\right)^3
]
Coefficient of (x^n):
[
\binom{n + 2}{2}
]
This is a very common exam problem.
⭐ Quick Exam-Oriented Summary
Definition:
Generating Function of sequence ({a_n}):
[
G(x) = \sum_{n=0}^{\infty} a_n x^n
]
Uses:
- Solve recurrence relations
- Count combinations
- Convert sequences to algebraic form
Common Generating Functions:
| Sequence | G(x) |
|---|---|
| 1,1,1,… | 1/(1−x) |
| 1,2,3,… | x/(1−x)² |
| 1,r,r²,… | 1/(1−rx) |
| Fibonacci | x/(1−x−x²) |
Types:
Ordinary, Exponential, Probability
Important concepts:
- Shifting
- Differentiating
- Series multiplication
Pigeon Hole Principle
Here is a clear, simple, and exam-oriented explanation of the Pigeonhole Principle — perfect for BCA/MCA/Engineering/Discrete Mathematics exams.
⭐ Pigeonhole Principle (PHP)
The Pigeonhole Principle is a fundamental counting rule used when objects are placed into boxes (containers, categories).
It states:
⭐ Basic (Simple) Pigeonhole Principle
If more than n objects are placed into n boxes,
then at least one box contains 2 or more objects.
In formula form:
If k > n,
and k objects are placed into n boxes,
then at least one box will have at least ⌈k/n⌉ objects.
⭐ Example 1
If 13 socks are placed into 12 drawers,
→ At least one drawer has ≥ 2 socks.
⭐ Example 2
There are 367 people in a hall.
Number of possible birthdays = 366 (including leap day).
→ By pigeonhole principle, at least 2 people share the same birthday.
⭐ Generalized (Strong) Pigeonhole Principle
If k objects are placed into n boxes,
then at least one box contains at least:
[
\left\lceil \frac{k}{n} \right\rceil
]
objects.
✔ Example
If 100 chocolates are placed into 9 jars:
[
\left\lceil \frac{100}{9} \right\rceil = \left\lceil 11.11 \right\rceil = 12
]
→ At least one jar must contain 12 chocolates.
⭐ Applications of Pigeonhole Principle
It is widely used in:
✔ Combinatorics
✔ Probability
✔ Algorithm design
✔ Number theory
✔ Graph theory
✔ Coding theory
✔ Real-life problems
⭐ Popular Pigeonhole Problems
1️⃣ Example: Hair Count Problem
If city has 1 million people,
maximum possible number of hairs on a human head = 150,000.
→ By PHP, two people have exactly the same number of hairs.
2️⃣ Example: Socks Problem
You have 10 pairs of socks mixed in a drawer.
How many socks must you pick to guarantee getting a matching pair?
There are 10 types (colors) of socks.
Using PHP:
Pick 11 socks → ensures at least one pair matches.
3️⃣ Example: Friendship Problem (Ramsey Theory)
In any group of 6 people,
there are either:
- 3 mutual friends, or
- 3 mutual strangers
PHP helps prove this.
4️⃣ Example: Integers Problem
Choose any 5 integers from the set {1, 2, 3, …, 8}.
Prove that two chosen numbers are consecutive.
Divide {1–8} into 4 boxes:
- {1,2}
- {3,4}
- {5,6}
- {7,8}
If we choose 5 numbers → 4 boxes
PHP → at least one box has 2 numbers → those are consecutive.
⭐ 5️⃣ Geometry Example
In a square of side length 2, if you place 5 points,
you can divide the square into 4 smaller squares of side 1.
By PHP, at least one small square has ≥ 2 points.
⭐ 6️⃣ Numbers and Remainders
Among n + 1 integers, there are at least 2 integers with the same remainder when divided by n.
This is because there are only n possible remainders:
0, 1, 2, …, n−1.
⭐ 7️⃣ Sum Problem
Take any 10 numbers from {1–18}.
Two of them must sum to 19.
Pairs (boxes):
- (1,18), (2,17), (3,16), … (9,10) → 9 boxes
Choosing 10 numbers → by PHP at least one box contains both numbers → sum = 19.
⭐ 8️⃣ People in a Room
If there are n people, at least two people have the same degree (number of friends) in a group/network.
Used in graph theory (Handshaking Lemma).
⭐ Exam-Oriented Summary
Basic PHP
If k > n, placing k objects into n boxes implies a box has ≥ 2 objects.
General PHP
[
\text{Max in a box} \ge \left\lceil \frac{k}{n} \right\rceil
]
Uses:
- Guarantees existence
- Counting without exact arrangements
- Number theory
- Probability
- Graph theory
- Geometry
- Combinatorics