What is the inclusion-exclusion principle?

The inclusion-exclusion principle is a counting technique for finding the size of a union of overlapping sets. It adds the sizes of individual sets, subtracts pairwise intersections to correct double-counting, adds back triple intersections, and continues with alternating signs until all intersections are accounted for.

What is the inclusion-exclusion formula for two sets?

For two sets A and B, the formula is |A ∪ B| = |A| + |B| - |A ∩ B|. Elements in both sets are counted twice when adding |A| and |B|, so subtracting |A ∩ B| removes the extra count and gives the correct size of the union.

How does inclusion-exclusion extend to n sets?

For n sets, the formula sums |A_i| over singles, subtracts |A_i ∩ A_j| over pairs, adds triple intersections, and continues with alternating signs through the n-fold intersection. The total number of terms is 2^n - 1, one for each non-empty subset of the n sets.

What is the complementary form of inclusion-exclusion?

The complementary form counts elements belonging to none of the sets A_1, ..., A_n inside a universal set U. It equals |U| minus the inclusion-exclusion expansion of the union. This form solves problems like derangements, surjective function counting, and arrangements with forbidden positions.

When is inclusion-exclusion used?

Inclusion-exclusion is used whenever counting requires correcting for overlap. Common applications include counting derangements, surjective functions, integers coprime to a set of primes, arrangements avoiding forbidden positions, and probabilities of unions of non-disjoint events.

Inclusion-Exclusion

Two Sets

Three Sets

The General Formula

The Complementary Form

Application: Counting Derangements

Worked Examples

Related Concepts

Inclusion–Exclusion at a Glance

The Overlap Problem

The addition rule computes the size of a union by adding the sizes of its pieces — but only when those pieces are mutually exclusive. The moment two sets share elements, simply adding their sizes counts the shared elements twice.

The inclusion–exclusion principle is the systematic correction. Add the sizes of individual sets, subtract the sizes of pairwise intersections to remove the double-counting, add back the sizes of triple intersections to compensate for the over-correction, and continue with alternating signs until all intersections are accounted for.

This page builds the principle from the two-set case to the general formula, then turns to its complementary form — counting elements that belong to none of the listed sets. That complementary form produces the derangement count and other "none" results.

Two Sets

For two sets

A

and

B

, the size of the union is

Inclusion-Exclusion Principle (Two Sets)

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

Learn more about this formula: Inclusion-Exclusion Principle (Two Sets) →

Browse all combinatorics formulas →

Every element of

A \cup B

should be counted once on the left side. On the right, an element belonging to only

A

is counted once (by

|A|

), an element belonging to only

B

is counted once (by

|B|

), and an element in both is counted twice — once by

|A|

and once by

|B|

. Subtracting

|A \cap B|

removes that extra count, restoring the correct total.

Example

In a group of 30 students, 18 take French and 15 take Spanish, with 7 taking both. The number taking at least one of the two languages is

18 + 15 - 7 = 26.

The remaining 4 students take neither.

Three Sets

For three sets, the same logic extends with one more correction:

Inclusion-Exclusion Principle (Three Sets)

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

Learn more about this formula: Inclusion-Exclusion Principle (Three Sets) →

Browse all combinatorics formulas →

An element belonging to exactly one of the three sets is counted once on the right. An element in exactly two is counted twice by the singles and subtracted once by its single pairwise intersection — net count

1

. An element in all three is counted three times by the singles, subtracted three times by the pairwise intersections, and added back once by the triple intersection — net count

3 - 3 + 1 = 1

. Every element ends up counted exactly once.

Example

Among the integers from 1 to 100, the number divisible by 2, 3, or 5 is computed by applying the three-set formula to the divisibility sets. With

|A| = 50

(multiples of 2),

|B| = 33

(multiples of 3),

|C| = 20

(multiples of 5), and the pairwise and triple intersections counting multiples of

6

10

15

, and

30

50 + 33 + 20 - 16 - 10 - 6 + 3 = 74.

The General Formula

For

n

sets

A_1, A_2, \ldots, A_n

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

In compact form,

Inclusion-Exclusion Principle (General)

\left| \bigcup_{i=1}^{n} A_i \right| = \sum_{k=1}^{n} (-1)^{k+1} \sum_{1 \le i_1 < i_2 < \cdots < i_k \le n} |A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}|.

Learn more about this formula: Inclusion-Exclusion Principle (General) →

Browse all combinatorics formulas →

Structure of the Formula

The number of terms at level

k

— meaning the number of

k

-fold intersections being summed — is $\binom{n}{k}$, one term for each

k

-subset of the

n

sets. The total number of terms across all levels is

\sum_{k=1}^{n} \binom{n}{k} = 2^n - 1,

which is the number of non-empty subsets of the

n

sets. Every non-empty subset contributes exactly one term to the formula.

Why the Alternating Signs Work

An element belonging to exactly

m

of the

n

sets is counted

\binom{m}{1} - \binom{m}{2} + \binom{m}{3} - \cdots + (-1)^{m+1} \binom{m}{m}

times by the right-hand side. By the binomial theorem with

a = 1

and

b = -1

\sum_{k=0}^{m} (-1)^k \binom{m}{k} = 0,

\binom{m}{0} = 1

minus the alternating sum from

k=1

m

gives

1

. Every element in the union is counted exactly once, as required.

The Complementary Form

Often the question is not how many elements belong to some of the

A_i

, but how many belong to none of them. If

U

is a universal set containing all candidate elements, the elements outside every

A_i

form the intersection of the complements:

Inclusion-Exclusion Complementary Form

\left| \overline{A_1} \cap \overline{A_2} \cap \cdots \cap \overline{A_n} \right| = |U| - \left| A_1 \cup A_2 \cup \cdots \cup A_n \right|.

Learn more about this formula: Inclusion-Exclusion Complementary Form →

Browse all combinatorics formulas →

Expanding the right side using the general formula gives a direct expression for the count of elements satisfying none of the conditions defined by

A_1, \ldots, A_n

|U| - \sum_{i} |A_i| + \sum_{i<j} |A_i \cap A_j| - \sum_{i<j<k} |A_i \cap A_j \cap A_k| + \cdots + (-1)^n |A_1 \cap \cdots \cap A_n|.

This is the natural form for problems phrased as "how many elements avoid all of the following conditions" — derangements, surjective functions, arrangements with forbidden positions, and divisibility problems requiring relative primality to several primes.

Application: Counting Derangements

A derangement of

\{1, 2, \ldots, n\}

is a permutation in which no element appears in its original position. The derangement formula is derived by applying the complementary form of inclusion–exclusion to the set of all permutations.

Setup

For each

i

, let

A_i

denote the set of permutations of

\{1, \ldots, n\}

in which position

i

is fixed (the element

i

remains in its original position). The derangements are the permutations belonging to none of

A_1, A_2, \ldots, A_n

Intersection Sizes

The size of any

k

-fold intersection

A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_k}

equals

(n-k)!

— fixing

k

specific positions leaves the remaining

n-k

positions to be permuted freely. The size depends only on

k

, not on which

k

positions are chosen.

Derivation

The total number of permutations is

n!

. Applying the complementary form of inclusion–exclusion:

!n = n! - \binom{n}{1}(n-1)! + \binom{n}{2}(n-2)! - \cdots + (-1)^n \binom{n}{n} \cdot 0!.

Simplifying each term using

\binom{n}{k}(n-k)! = \frac{n!}{k!}

gives the explicit derangement formula:

!n = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!}.

The permutations page states this formula and applies it. The derivation above is what justifies it.

Worked Examples

Three standard problem types beyond derangements.

Divisibility

How many integers from 1 to 100 are divisible by none of 2, 3, or 5?

Let

A_i

be the set of integers divisible by the

i

-th prime in the list. From the three-set example above,

|A \cup B \cup C| = 74

. The complementary count is

100 - 74 = 26.

These are the integers from 1 to 100 that share no prime factor with 30.

Surjective Functions

How many functions from a set of size

n

to a set of size

k

are surjective (every element of the codomain has at least one preimage)?

For each element

i

of the codomain, let

A_i

be the set of functions that miss

i

— that is, no element of the domain maps to

i

. A surjective function avoids every

A_i

. The size of any

j

-fold intersection

A_{i_1} \cap \cdots \cap A_{i_j}

(k-j)^n

, since the domain elements may map freely to the remaining

k-j

codomain elements. The total count of functions is

k^n

. By inclusion–exclusion:

Surjective Functions Count

\#\{\text{surjections } [n] \to [k]\} = \sum_{j=0}^{k} (-1)^j \binom{k}{j} (k-j)^n.

Learn more about this formula: Surjective Functions Count →

Browse all combinatorics formulas →

Arrangements With Forbidden Positions

In how many ways can

n

items be arranged so that none of them occupies a specified set of

m

forbidden positions? Define

A_i

as the set of arrangements where item

i

does occupy its forbidden position. The complementary count, computed via inclusion–exclusion on the

A_i

, gives the answer. The derangement formula is the special case where each of the

n

items has exactly one forbidden position and the forbidden positions are all distinct.

Problem type	What to count	Define A_i as	Final formula
Divisibility / coprimality	integers in 1..N divisible by none of given primes	integers in 1..N divisible by the i-th prime	N − \|A₁ ∪ A₂ ∪ … ∪ A_n\|
Surjective functions	surjections from an n-set to a k-set	functions missing codomain element i; \|j-fold intersection\| = (k − j)ⁿ	Σ_j=0^k (−1)^j C(k, j) (k − j)ⁿ
Derangements	permutations of 1..n with no fixed point	permutations fixing position i; \|k-fold intersection\| = (n − k)!	!n = n! · Σ_k=0ⁿ (−1)^k ⁄ k!
Forbidden positions	arrangements of n items avoiding specified forbidden positions	arrangements with item i in its forbidden position	n! − \|A₁ ∪ … ∪ A_n\| via inclusion–exclusion (derangements are the special case)

Related Concepts

• Set Theory — unions, intersections, complements, and the cardinality identities are the formal structure inclusion–exclusion operates on.

• Probability — the probabilistic version of inclusion–exclusion is the standard tool for computing the probability of a union of non-disjoint events.

Inclusion–Exclusion at a Glance

The page built the principle from two sets to the general n-set formula, derived its complementary form, and applied that form to derangements and several other standard problems. The table below collects the formula variants alongside the situations each one solves.

Form	Formula	When to use	Example
Two sets	\|A ∪ B\| = \|A\| + \|B\| − \|A ∩ B\|	two overlapping groups; correct for the double-count once	18 French + 15 Spanish − 7 both = 26
Three sets	singles − pairs + triple	three overlapping conditions; one over-correction needs adding back	multiples of 2, 3, or 5 in 1..100: 74
n sets (union form)	Σ_k=1ⁿ (−1)^k+1 Σ \|k-fold intersections\|; 2ⁿ − 1 terms total	general count of a union of n overlapping sets	any union problem with explicit intersection sizes
n sets (complementary form)	\|U\| − Σ \|A_i\| + Σ \|A_i ∩ A_j\| − … + (−1)ⁿ \|A₁ ∩ … ∩ A_n\|	"satisfy NONE of the conditions" / "avoid all forbidden cases"	integers in 1..100 coprime to 30: 26
Derangement specialization	!n = n! · Σ_k=0ⁿ (−1)^k ⁄ k! ≈ n! ⁄ e	no item lands in its own original position	shuffled hats: probability no one gets own hat → 1⁄e