Principle of Inclusion-Exclusion (PIE) | JEE Combinatorics

Why PIE Matters in JEE

The Principle of Inclusion-Exclusion is a fundamental counting technique that helps us accurately count elements in the union of multiple sets by systematically correcting for overcounting.

🎯 The Core Idea

When counting elements in multiple sets:

If we simply add sizes of sets, we overcount elements in intersections
PIE gives us a systematic way to include, exclude, and re-include elements
The pattern alternates between inclusion and exclusion

Fundamental Concept Essential

The PIE Formulas

For 2 Sets: A and B

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

We add individual sizes, then subtract the intersection we counted twice.

A

B

A∩B

Visualizing why we subtract the intersection

For 3 Sets: A, B, and C

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

We add all sets, subtract pairwise intersections (over-subtracted), then add back the triple intersection (over-corrected).

General Pattern for n Sets

$$ \left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \cdots \cap A_n| $$

Alternating sum of sizes of intersections of all possible combinations.

📚 Example: Student Clubs

In a class of 50 students:

25 students in Math Club
20 students in Physics Club
15 students in Chemistry Club
10 students in both Math and Physics
8 students in both Math and Chemistry
6 students in both Physics and Chemistry
4 students in all three clubs

How many students are in at least one club?

$|M \cup P \cup C| = 25 + 20 + 15 - 10 - 8 - 6 + 4 = 40$ students

Classic Application Medium

Application 1: Derangements

A derangement is a permutation where no element appears in its original position.

🎯 The Hat-Check Problem

n people check their hats. The hats are returned randomly. What's the probability that no one gets their own hat back?

This is the classic derangement problem!

Derangement Formula using PIE

Let $A_i$ be the set of permutations where element $i$ is in its original position.

Using PIE, the number of derangements $D_n$ is:

$$ D_n = n! - \sum |A_i| + \sum |A_i \cap A_j| - \sum |A_i \cap A_j \cap A_k| + \cdots + (-1)^n |A_1 \cap A_2 \cap \cdots \cap A_n| $$

Which simplifies to:

$$ D_n = n! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + (-1)^n \frac{1}{n!}\right) $$

📚 Example: 4 Letters to 4 People

4 people write letters to each other. If letters are randomly distributed, what's the probability that no one gets their own letter?

Total permutations: $4! = 24$

Derangements: $D_4 = 4! \left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!}\right) = 24 \left(1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24}\right) = 9$

Probability: $\frac{9}{24} = \frac{3}{8}$

💡 Quick Derangement Values

$D_1 = 0$

$D_2 = 1$

$D_3 = 2$

$D_4 = 9$

$D_5 = 44$

JEE Favorite Easy

Application 2: Counting Divisible Numbers

PIE is perfect for counting numbers divisible by certain integers within a range.

🎯 Classic JEE Problem

How many numbers from 1 to 1000 are divisible by 2, 3, or 5?

📚 Step-by-Step Solution

Step 1: Define sets:

$A$ = numbers divisible by 2
$B$ = numbers divisible by 3
$C$ = numbers divisible by 5

Step 2: Calculate individual sizes:

$|A| = \lfloor 1000/2 \rfloor = 500$
$|B| = \lfloor 1000/3 \rfloor = 333$
$|C| = \lfloor 1000/5 \rfloor = 200$

Step 3: Calculate pairwise intersections:

$|A \cap B|$ = divisible by 6 = $\lfloor 1000/6 \rfloor = 166$
$|A \cap C|$ = divisible by 10 = $\lfloor 1000/10 \rfloor = 100$
$|B \cap C|$ = divisible by 15 = $\lfloor 1000/15 \rfloor = 66$

Step 4: Calculate triple intersection:

$|A \cap B \cap C|$ = divisible by 30 = $\lfloor 1000/30 \rfloor = 33$

Step 5: Apply PIE:

$|A \cup B \cup C| = 500 + 333 + 200 - 166 - 100 - 66 + 33 = 734$

🔢 Quick Divisibility Rules

Numbers divisible by $a$ and $b$ = divisible by $\text{LCM}(a,b)$
Numbers divisible by $a$, $b$, and $c$ = divisible by $\text{LCM}(a,b,c)$
Count from 1 to $n$: use floor division $\lfloor n/x \rfloor$

Advanced Application Hard

Application 3: Counting Surjective Functions

A function $f: A \to B$ is surjective (onto) if every element in B has at least one preimage in A.

🎯 The Surjective Counting Problem

How many surjective functions are there from a set with $m$ elements to a set with $n$ elements?

Surjective Functions Formula using PIE

Let $A_i$ be the set of functions where element $i$ in the codomain has no preimage.

Using PIE, the number of surjective functions is:

$$ \text{Surj}(m,n) = n^m - \binom{n}{1}(n-1)^m + \binom{n}{2}(n-2)^m - \cdots + (-1)^n \binom{n}{n}0^m $$

Or more compactly:

$$ \text{Surj}(m,n) = \sum_{k=0}^n (-1)^k \binom{n}{k} (n-k)^m $$

📚 Example: 5 Balls to 3 Boxes

How many ways to distribute 5 distinct balls into 3 distinct boxes such that no box is empty?

This is equivalent to surjective functions from balls (domain) to boxes (codomain).

Using the formula:

$\text{Surj}(5,3) = \sum_{k=0}^3 (-1)^k \binom{3}{k} (3-k)^5$
$= \binom{3}{0}3^5 - \binom{3}{1}2^5 + \binom{3}{2}1^5 - \binom{3}{3}0^5$
$= 1 \cdot 243 - 3 \cdot 32 + 3 \cdot 1 - 1 \cdot 0 = 243 - 96 + 3 = 150$

🎯 When to Use This Formula

Surjective functions: Every element in codomain gets at least one preimage
Distribution problems: Distributing distinct objects into distinct containers with no empty containers
Occupancy problems: Ensuring all categories/boxes get at least one item

🚀 PIE Problem-Solving Framework

Step-by-Step Approach

Identify the sets you're taking union of
Calculate individual sizes $|A_i|$
Calculate pairwise intersections $|A_i \cap A_j|$
Calculate triple intersections $|A_i \cap A_j \cap A_k|$ (if needed)
Apply PIE formula with alternating signs
Verify with small cases if possible

Common Pitfalls to Avoid

Forgetting to alternate signs in PIE
Missing some intersection terms
Incorrectly counting intersection sizes
Applying PIE when direct counting is easier
Confusing union with intersection in word problems

📝 Test Your Understanding

Try these JEE-style problems to reinforce your PIE skills:

1. How many numbers from 1 to 500 are divisible by 3, 5, or 7?

Hint: Use PIE with 3 sets

2. In how many ways can 4 couples be seated around a circular table such that no couple sits together?

Hint: This is a derangement problem with circular arrangement

3. How many surjective functions are there from a set of 6 elements to a set of 4 elements?

Hint: Use the surjective function formula

Challenge: Solve all three in under 10 minutes to ensure JEE readiness!

Master PIE for JEE Success!

These three applications cover 90% of PIE problems in JEE Main and Advanced

The Principle of Inclusion-Exclusion (PIE): Counting What You Must