Skip to content
Home » Principle of Inclusion and Exclusion

Principle of Inclusion and Exclusion

Here is a simple, clear, and exam-oriented explanation of the Principle of Inclusion and Exclusion (PIE) — perfect for BCA/MCA/Engineering/Discrete Mathematics exams.

⭐ Principle of Inclusion and Exclusion (PIE)

The Principle of Inclusion and Exclusion is a powerful counting technique used when:

✔ We want to find the number of elements in the union of sets
✔ Sets overlap, so direct addition overcounts
✔ We must correct for overcounting by subtracting intersections

PIE allows us to count the number of elements satisfying at least one condition.

⭐ 1. PIE for Two Sets

For sets A and B:

[
|A \cup B| = |A| + |B| – |A \cap B|
]

Explanation:

  • Add |A| and |B|
  • Subtract |A ∩ B| because it is counted twice

✔ Example

40 students play cricket,
30 play football,
15 play both.

How many play at least one game?

[
|A \cup B| = 40 + 30 – 15 = 55
]

⭐ 2. PIE for Three Sets

For 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|
    ]

Explanation:

  • Add sizes of all 3 sets
  • Subtract pairwise intersections
  • Add back the triple intersection

✔ Example

In a class:
A = like Maths = 30
B = like Physics = 25
C = like Chemistry = 20
A∩B = 10
A∩C = 8
B∩C = 7
A∩B∩C = 5

Find number who like at least one subject.

[
= 30 + 25 + 20 – 10 – 8 – 7 + 5
= 55
]

⭐ 3. General Inclusion–Exclusion Formula

For n sets (A_1, A_2, \dots, A_n):

[
\left|\bigcup_{i=1}^n A_i\right|

\sum |A_i|

  • \sum |A_i \cap A_j|
  • \sum |A_i \cap A_j \cap A_k|
  • \cdots
  • (-1)^{n-1}|A_1 \cap A_2 \cap \cdots \cap A_n|
    ]

The pattern is:

  • Add single sets
  • Subtract intersections of 2
  • Add intersections of 3
  • Subtract intersections of 4
  • Continue alternating signs

⭐ 4. PIE for Counting Elements That Satisfy None of the Conditions

If the universal set has N elements:

[
|\text{none}| = N – |A \cup B \cup C \cup \cdots|
]

✔ Example

Out of 100 students, 80 like maths, 70 like science, 60 like English, 40 like all three.

Assume known intersections:

Using PIE:

[
|A \cup B \cup C| = \text{use formula}
]

Students who like none =
[
100 – |A \cup B \cup C|
]

⭐ 5. PIE Application in Counting Problems

✔ Example: How many numbers from 1 to 100 are divisible by 2 or 3?

Let
A = divisible by 2
B = divisible by 3

|A| = 50
|B| = 33
|A∩B| = divisible by 6 = 16

[
|A \cup B| = 50 + 33 – 16 = 67
]

✔ Example: How many 4-digit numbers have NO repeated digits?

Total 4-digit numbers = 9000 (1000–9999)

Let Ai = numbers where digit i repeats
Use PIE.
This is a common exam problem (I can explain if needed).

⭐ 6. PIE for Derangements (advanced application)

Derangement = permutation with no fixed point.

Number of derangements of n items:

[
D_n = n!\left(1 – \frac{1}{1!} + \frac{1}{2!} – \cdots + (-1)^n\frac{1}{n!}\right)
]

Derived using inclusion–exclusion.

⭐ Quick Exam Summary

PIE for two sets:

[
|A \cup B| = |A| + |B| – |A \cap B|
]

PIE 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|
    ]

General formula:

Alternate adding & subtracting intersections.

Applications:

  • Counting union of sets
  • Probability
  • Derangements
  • Divisibility problems
  • Survey problems
  • Scheduling
  • Number theory