∪

Inclusion-Exclusion Calculator

Set Union · PIE Formula · Venn Diagram · Probability

Compute |A∪B∪C∪D| for 2, 3, or 4 sets using the Principle of Inclusion-Exclusion. Full formula substitution, step-by-step calculation, and optional probability output.

Quick Examples

Individual Sets

|A|

|B|

Intersections

|A∩B|

Optional

|U| (Universal set)

|A∪B|

—

Union size

Terms Added

—

Positive terms

Terms Subtracted

—

Negative terms

Step-by-Step Solution

Venn Diagram

Region Breakdown (15 Non-empty Subsets)

Each row shows one intersection term, its sign in the formula, its value, and running total.

Term	Sign	Value	Running Total

What Is the Principle of Inclusion-Exclusion?

The Principle of Inclusion-Exclusion (PIE) is a fundamental counting technique in combinatorics and set theory. It provides an exact formula for the size of the union of overlapping finite sets by alternately adding and subtracting the sizes of intersections. The key insight is that when you naively sum the sizes of several sets, elements belonging to multiple sets are counted more than once — inclusion-exclusion corrects this by subtracting over-counted elements and then adding back under-counted ones, ensuring each element is counted exactly once.

For two sets A and B, the formula is simply: |A∪B| = |A| + |B| − |A∩B|. Adding |A| and |B| counts elements in A∩B twice, so we subtract |A∩B| once to compensate. This familiar identity from Venn diagrams generalizes to any number of sets.

The General Formula for n Sets

For n sets A₁, A₂, …, A_n, the inclusion-exclusion formula is:

|A₁∪…∪A_n| = Σ|A_i| − Σ|A_i∩A_j| + Σ|A_i∩A_j∩A_k| − … + (−1)ⁿ⁺¹|A₁∩…∩A_n|

The sum contains 2ⁿ−1 terms (one per non-empty subset of the n sets). The sign is positive for subsets of odd size and negative for subsets of even size. For 2 sets there are 3 terms; for 3 sets, 7 terms; for 4 sets, 15 terms.

The 3-Set Formula

The most commonly tested form is the three-set formula:

|A∪B∪C| = |A|+|B|+|C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|

Here, elements in exactly two sets (e.g., A∩B but not C) are added twice and subtracted once, netting one count. Elements in all three sets are added three times, subtracted three times, and added back once, also netting one count. This confirms the formula counts every element exactly once.

Venn Diagrams and Region Counts

A Venn diagram for n sets has 2ⁿ regions (including the exterior), each representing a unique membership pattern. For 2 sets: A-only, B-only, A∩B, and neither. For 3 sets: 7 non-empty interior regions. For 4 sets: up to 15 interior regions (represented by 4 overlapping ellipses since four circles cannot produce all 15 distinct regions). The region counts can be derived from the intersection sizes by inclusion-exclusion applied in reverse.

Inclusion-Exclusion in Probability

In probability theory, the same principle applies to event probabilities: P(A∪B∪C) = P(A)+P(B)+P(C) − P(A∩B) − P(A∩C) − P(B∩C) + P(A∩B∩C). When the universal set size |U| is known, each probability is simply the count divided by |U|. The probability of the complement event (none of the events occurring) is P(A^c∩B^c∩C^c) = 1 − P(A∪B∪C).

Applications of the Inclusion-Exclusion Principle

Derangements: The number of derangements of n elements is D_n = n! × Σ_k=0ⁿ (−1)^k/k!, derived by applying inclusion-exclusion to the sets of permutations that fix at least one element.
Euler's Totient Function: φ(n) = n × ∏_p|n(1 − 1/p), where the product is over prime factors of n, is derived via inclusion-exclusion over sets of multiples of each prime factor.
Sieve of Eratosthenes: The sieve's counting step is essentially inclusion-exclusion over sets of multiples of small primes.
Bonferroni Inequalities: Truncating the inclusion-exclusion series gives alternating upper and lower bounds on the union size, useful when exact computation is intractable.
Chromatic polynomials: Counting proper colorings of graphs uses inclusion-exclusion over edge sets.
Survey analysis: Computing the number of respondents holding at least one opinion from overlapping survey categories is a direct application.

Worked Example: Divisibility in 1–100

How many integers from 1 to 100 are divisible by 2, 3, or 5? Let A = multiples of 2 (⌊100/2⌋ = 50), B = multiples of 3 (33), C = multiples of 5 (20). Intersections: A∩B = multiples of 6 (16), A∩C = multiples of 10 (10), B∩C = multiples of 15 (6), A∩B∩C = multiples of 30 (3). By inclusion-exclusion: |A∪B∪C| = 50+33+20−16−10−6+3 = 74. So 26 integers from 1 to 100 are not divisible by 2, 3, or 5.

Quick Reference Table

Sets	Formula Terms	Signs	Total Terms
2	\|A\|, \|B\|, \|A∩B\|	+, +, −	3
3	Singles, pairs, triple	+, −, +	7
4	Singles, pairs, triples, quad	+, −, +, −	15
n	All non-empty subsets	Alternating by size	2ⁿ−1

Frequently Asked Questions

What is the inclusion-exclusion principle?

The inclusion-exclusion principle (PIE) is a counting technique that computes the size of the union of overlapping sets by alternately adding and subtracting intersection sizes. For n sets it states: |A₁∪…∪A_n| equals the sum of individual sizes minus sum of pairwise intersections plus sum of triple intersections, and so on, with alternating signs. The alternating pattern ensures every element is counted exactly once regardless of how many sets it belongs to.

What is the formula for the union of three sets?

For three sets A, B, and C: |A∪B∪C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|. The three pairwise intersections are subtracted to fix double-counting, and the triple intersection is added back because it was subtracted three times and needs to be added once to net a count of one per element.

How is inclusion-exclusion used in probability?

In probability, the inclusion-exclusion formula applies to events: P(A∪B∪…) = ΣP(A_i) − ΣP(A_i∩A_j) + …. When a universal set size |U| is provided, convert counts to probabilities as P = count / |U|. The complement probability P(none of the events) = 1 − P(union), useful in problems asking "what is the chance no condition is met?"

What are Bonferroni inequalities?

Bonferroni inequalities are bounds obtained by truncating the inclusion-exclusion series. Stopping after an odd-numbered term gives an upper bound on |union|; stopping after an even-numbered term gives a lower bound. They are especially valuable in statistics when not all higher-order intersection probabilities are known, allowing you to bound the union probability using only the available data.

How does inclusion-exclusion relate to Euler's totient function?

Euler's totient φ(n) counts integers from 1 to n that are coprime to n. The integers not coprime to n are those divisible by at least one prime factor of n. Applying inclusion-exclusion over sets of multiples of each prime factor p_i yields φ(n) = n × ∏_p|n(1 − 1/p). This elegant product formula is a direct consequence of PIE applied to sets of multiples.

Can inclusion-exclusion be used for more than 4 sets?

Yes, the principle extends to any n sets. The formula sums over all 2ⁿ−1 non-empty subsets with sign (−1)^k+1 for subsets of size k. For n=5 this means 31 terms; for n=10, 1023 terms. This calculator handles up to 4 sets (15 terms). For larger n, the combinatorial explosion of intersection terms makes manual computation impractical, but the pattern is always the same alternating-sign sum.

What is a Venn diagram?

A Venn diagram represents sets as overlapping shapes — typically circles for 2–3 sets and ellipses for 4 sets. Each region corresponds to a unique membership pattern: elements in exactly those sets. For n sets there are 2ⁿ regions including the exterior. The overlapping regions visually correspond to intersections in the inclusion-exclusion formula, making the formula's structure immediately intuitive.