Principle of Inclusion & Exclusion

Overview

The Principle of Inclusion and Exclusion (PIE) is a fundamental counting technique used to compute the cardinality of the union of finite sets by correcting for over-counting of elements that belong to multiple sets. It is widely used in combinatorics, probability, and counting problems that arise in computer science and engineering mathematics.

Two sets

For two finite sets A and B the principle gives:

n(A ∪ B) = n(A) + n(B) - n(A ∩ B)

Here n(X) denotes the number of elements (cardinality) of set X. The formula adds the elements of A and B, then subtracts the elements counted twice - those in A ∩ B.

Three sets

For three finite sets A, B and C the formula is:

n(A ∪ B ∪ C) = n(A) + n(B) + n(C) - n(A ∩ B) - n(B ∩ C) - n(C ∩ A) + n(A ∩ B ∩ C)

The signs alternate to remove over-counting: single sets are added, pairwise intersections are subtracted, and the triple intersection is added back because it was subtracted three times.

General form for n sets

Let A₁, A₂, ..., A_n be finite sets. Then

n(A₁ ∪ A₂ ∪ ... ∪ A_n) =

Σ n(A_i) - Σ n(A_i ∩ A_j) + Σ n(A_i ∩ A_j ∩ A_k) - ... + (-1)^n-1 n(A₁ ∩ ... ∩ A_n)

The first summation runs over all single sets, the second over all distinct pairs, the third over all distinct triples, and so on. The sign of each term is determined by the parity of the size of the intersection.

Proof idea (counting or indicator functions)

Every element x that belongs to exactly m of the sets contributes to the right-hand side an amount equal to

Σ_k=1^{m} (-1)^{k-1} C(m, k) = 1.

Hence the element is counted exactly once on the right-hand side. Summing over all elements yields the formula. The identity above follows from the binomial expansion of (1 - 1)^m = 0.

Derangement

Definition

A derangement is a permutation of n distinct objects with no object in its original position. The number of derangements of n objects is denoted by D_n (also called the subfactorial and sometimes written !n).

Formula via inclusion-exclusion

Use PIE by counting all permutations (n!) and subtracting permutations that fix at least one element.

D_n = n! × [1 - 1/1! + 1/2! - 1/3! + ... + (-1)ⁿ 1/n!]

This is an exact formula. As n grows large, D_n is approximately n!/e, and D_n is the nearest integer to n!/e.

Recurrence

The derangement numbers satisfy the recurrence:

D_n = (n - 1) × (D_n-1 + D_n-2)

with initial values D₀ = 1 and D₁ = 0.

Small values

• D₀ = 1
• D₁ = 0
• D₂ = 1
• D₃ = 2
• D₄ = 9
• D₅ = 44

Solved Examples of the Principle of Inclusion-Exclusion and Derangement

Example 1: Among a group of students, 49 study Physics, 37 study English and 21 study Biology. If 9 of these students study Maths Physics and English, 5 study English and Biology, 4 study Physics and Biology and 3 study Physics, English and Biology, find the number of students in the group.
(a) 91
(b) 92
(c) 86
(d) none of these

Solution.

P represent students who study Physics, E represent students who study English and B represent students who study Biology.

n(P) = 49

n(E) = 37

n(B) = 21

n(P ∩ E) = 9

n(E ∩ B) = 5

n(P ∩ B) = 4

n(P ∩ E ∩ B) = 3

Using PIE for three sets:

n(P ∪ E ∪ B) = n(P) + n(E) + n(B) - n(P ∩ E) - n(E ∩ B) - n(P ∩ B) + n(P ∩ E ∩ B)

n(P ∪ E ∪ B) = 49 + 37 + 21 - 9 - 5 - 4 + 3

n(P ∪ E ∪ B) = 92

Option b is the answer.

Example 2: Find the number of ways that you can put 7 letters into their respective envelopes such that exactly 3 go into the right envelope.
(a) 350
(b) 102
(c) 315
(d) 530

Solution.

Select which 3 letters are placed correctly. The number of ways to choose these 3 is C(7, 3).

C(7, 3) = 7 × 6 × 5 / (1 × 2 × 3) = 35

For the remaining 4 letters, none may be in the correct envelope, so we need the derangement D₄.

D₄ = 9

Total number of ways = C(7, 3) × D₄ = 35 × 9

Total number of ways = 315

Option c is the answer.

Applications and remarks

• Counting with restrictions: PIE is useful when we must count elements that avoid several properties (for example, counting strings that avoid certain substrings or permutations avoiding positions).
• Probability: To compute the probability that none of a set of events occur, PIE converts event probabilities into alternating sums of intersection probabilities.
• Algorithmic view: Inclusion-exclusion can be implemented in algorithms by iterating over subsets; it appears in exponential-time algorithms for some NP-hard problems and in dynamic programming on bitmasks.
• Derangements in practice: Derangements model problems such as secret Santa assignments, matching problems where fixed points are forbidden, and error-correcting arrangements.

Derivation of D_n by inclusion-exclusion (sketch)

Count all permutations of n objects: n!.

Let A_i be the set of permutations fixing element i. A permutation fixes at least one element if it lies in ∪ A_i. Use PIE to exclude permutations fixing one or more elements.

D_n = n! - C(n,1)(n-1)! + C(n,2)(n-2)! - ... + (-1)ⁿ C(n,n)(n-n)!.

Factor out n!: D_n = n! × [1 - 1/1! + 1/2! - ... + (-1)ⁿ 1/n!].

Useful identities

• Nearest integer formula: D_n = nearest integer to n!/e.
• Alternate closed form: D_n = ⌊n!/e + 1/2⌋ for n ≥ 1 (where ⌊·⌋ is floor), so D_n = round(n!/e).

Practice suggestions

• Use the PIE formula for unions of sets with up to 3-4 sets by hand; for larger numbers consider symmetry or complementary counting where possible.
• When counting derangements with additional constraints (for example some specific elements are forced or forbidden), combine combinations (to choose fixed items) with derangement numbers for the remainder.
• For algorithmic problems, implement inclusion-exclusion by iterating over all subsets and adding or subtracting counts according to subset parity; use bitmasks for efficiency.