
- Discrete Mathematics - Home
- Discrete Mathematics Introduction
- Mathematical Statements and Operations
- Atomic and Molecular Statements
- Implications
- Predicates and Quantifiers
- Sets
- Sets and Notations
- Relations
- Operations on Sets
- Venn Diagrams on Sets
- Functions
- Surjection and Bijection Functions
- Image and Inverse-Image
- Mathematical Logic
- Propositional Logic
- Logical Equivalence
- Deductions
- Predicate Logic
- Proof by Contrapositive
- Proof by Contradiction
- Proof by Cases
- Rules of Inference
- Group Theory
- Operators & Postulates
- Group Theory
- Algebric Structure for Groups
- Abelian Group
- Semi Group
- Monoid
- Rings and Subring
- Properties of Rings
- Integral Domain
- Fields
- Counting & Probability
- Counting Theory
- Combinatorics
- Additive and Multiplicative Principles
- Counting with Sets
- Inclusion and Exclusion
- Bit Strings
- Lattice Path
- Binomial Coefficients
- Pascal's Triangle
- Permutations and Combinations
- Pigeonhole Principle
- Probability Theory
- Probability
- Sample Space, Outcomes, Events
- Conditional Probability and Independence
- Random Variables in Probability Theory
- Distribution Functions in Probability Theory
- Variance and Standard Deviation
- Mathematical & Recurrence
- Mathematical Induction
- Formalizing Proofs for Mathematical Induction
- Strong and Weak Induction
- Recurrence Relation
- Linear Recurrence Relations
- Non-Homogeneous Recurrence Relations
- Solving Recurrence Relations
- Master's Theorem
- Generating Functions
- Graph Theory
- Graph & Graph Models
- More on Graphs
- Planar Graphs
- Non-Planar Graphs
- Polyhedra
- Introduction to Trees
- Properties of Trees
- Rooted and Unrooted Trees
- Spanning Trees
- Graph Coloring
- Coloring Theory in General
- Coloring Edges
- Euler Paths and Circuits
- Hamiltonion Path
- Boolean Algebra
- Boolean Expressions & Functions
- Simplification of Boolean Functions
- Advanced Topics
- Number Theory
- Divisibility
- Remainder Classes
- Properties of Congruence
- Solving Linear Diophantine Equation
- Useful Resources
- Quick Guide
- Useful Resources
- Discussion
Principle of Inclusion and Exclusion in Discrete Mathematics
The Principle of Inclusion and Exclusion (PIE) is an important concept in Set Theory that helps in calculating the cardinality of the union of multiple sets; this is True even when those sets overlap. The basic idea is to include elements in the union but exclude those that have been counted multiple times with the overlapping sets. It is little bit complex at first, but we will break it down and understand how it works.
Principle of Inclusion and Exclusion
The Principle of Inclusion and Exclusion is useful for finding the size of the union of two or more sets. When these sets overlap, adding their sizes together this may lead to double-counting the elements. PIE corrects this by subtracting the sizes of the intersections. But if multiple intersections overlap, further adjustments are needed.
For two sets A and B, the union can be written as −
$$\mathrm{|A \:\cup\: B| \:=\: |A| \:+\: |B| \:-\: |A \:\cap\: B|}$$

This formula works because the term $\mathrm{|A| \:+\: |B|}$ counts the elements in both sets. The intersection $\mathrm{|A \:\cap\: B|}$ gets counted twice. Once in A and once in B. By subtracting $\mathrm{|A \:\cap\: B|}$, we correct this overcounting.
Example of Two Sets
Let us look at an example. Suppose we have two sets −
- A is the set of students who like math, and there are 10 students in this set.
- B is the set of students who like science, and there are 8 students in this set.
The intersection A ∩ B, representing students who like both math and science, contains 6 students.
We want to know how many students like either math or science or both. Applying the formula:
$$\mathrm{|A \:\cup\: B| \:=\: |A| \:+\: |B| \:-\: |A \:\cap\: B| \:=\: 10 \:+\: 8 \:-\: 6 \:=\: 12}$$
Thus, 12 students like either math, science, or both.
Extending to Three Sets
Let us extend this principle for three sets. The process becomes slightly more complex. The formula for the union of three sets A, B, and C is −
$$\mathrm{|A \:\cup\: B \:\cup \:C| \:=\: |A| \:+\: |B| \:+\: |C| \:-\: |A \:\cap\: B| \:-\: |A \:\cap\: C| \:-\: |B \:\cap\: C| \:+\: |A \:\cap\: B \:\cap\: C|}$$
This formula adds the sizes of the individual sets but subtracts the pairwise intersections to avoid double-counting. But, the triple intersection $\mathrm{|A \:\cap\: B \:\cap\: C|}$ gets subtracted three times. So we add it back in once.

Example of Three Sets
Consider the following example −
- A represents students who failed Algebra (12 students).
- B represents students who failed Biology (5 students).
- C represents students who failed Chemistry (8 students).
- There are 2 students who failed both Algebra and Biology,
- 6 who failed both Algebra and Chemistry,
- 3 who failed both Biology and Chemistry, and
- 1 student who failed all three subjects.
We want to find the number of students that failed at least one subject. Using the formula for three sets −
$$\mathrm{|A \:\cup\: B \:\cup\: C| \:=\: |A| \:+\: |B| \:+\: |C| \:-\: |A \:\cap\: B| \:-\: |A \:\cap\: C| \:-\: |B\: \cap\: C| \:+\: |A \:\cap\: B \:\cap\: C|}$$
$$\mathrm{|A \:\cup\: B \:\cup\: C| \:=\: 12 \:+\: 5 \:+\: 8 \:-\: 2 \:-\: 6 \:-\: 3 \:+\: 1 \:=\: 15}$$
So, 15 students failed at least one subject.

General Formula for n Sets
The Principle of Inclusion and Exclusion can be generalized for any number of sets. For instance, if we have n sets (A1, A2, …, An) the size of their union is given by −
$$\mathrm{|A_1 \:\cup\: A_2 \:\cup\: \dots \:\cup\: A_n| \:= \:\sum_{i=1}^n |A_i| \:-\: \sum_{1 \:\leq\: i \:\lt\: j \:\leq\: n} |A_i \:\cap\: A_j| \:+\: \sum_{1 \:\leq\: i \:\lt\: j \:\lt\: k \:\leq\: n} |A_i \:\cap\: A_j \:\cap\: A_k| \:-\: \dots}$$
The formula alternates between adding and subtracting. This is because intersections of increasing size.
An Example with Four Sets
Let us look at a slightly more complicated example with four sets.
A school is hosting an event. Here students can sign up for four different activities: football, badminton, hockey, and cricket.
- 30 students signed up for football.
- 25 students signed up for badminton.
- 20 students signed up for hockey.
- 15 students signed up for cricket.
- 10 students signed up for both football and badminton.
- 8 students signed up for both football and hockey.
- 5 students signed up for both football and cricket.
- 7 students signed up for both badminton and hockey.
- 4 students signed up for both badminton and cricket.
- 6 students signed up for both hockey and cricket.
- 3 students signed up for all four activities.
To find how many students are signed up for at least one activity, we can apply the Principle of Inclusion and Exclusion. Here the formula becomes more complicated with four sets. It is useful to break down the terms step by step. But in the end, using PIE helps us avoid counting the students multiple times.
Applications of Inclusion and Exclusion
The Principle of Inclusion and Exclusion is not just a theoretical tool. It has several practical applications, including −
- Counting Problems − When trying to count the number of elements that meet at least one criterion.
- Probability − It helps calculate the probability of the union of several events by correcting for overlapping events.
- Computer Science − Algorithms often use PIE to count specific combinations of data structures like sets, graphs, or networks.
Conclusion
In this chapter, we explained the Principle of Inclusion and Exclusion (in short PIE) in discrete mathematics. We started by discussing the basics, including how the principle works for two sets. We then moved on to three sets, showing how the formula becomes more complex but still follows the same core idea.
We used an example to demonstrate how to use the principle to count students in different activities or subjects. Finally, we presented the general formula for any number of sets and how the principle is applied in counting, probability, and computer science.