Inclusion-Exclusion

Enumerate overlapping die events and trace the singles, pair and triple corrections that count their union exactly once.

Inclusion-Exclusion Principle

Concept Overview

The Inclusion-Exclusion Principle is a counting technique which generalizes the familiar method of obtaining the number of elements in the union of two finite sets; symbolically expressed as |A ∪ B| = |A| + |B| - |A ∩ B|.

Worked Example

Consider a 6-sided die, so the universe is U = {1, 2, 3, 4, 5, 6}. Let the sets be:

A = {2, 4, 6} (Even numbers, |A| = 3)
B = {3, 6} (Divisible by 3, |B| = 2)
C = {4, 5, 6} (Threshold t=4, |C| = 3)

Single terms sum: |A| + |B| + |C| = 3 + 2 + 3 = 8. Pairs: A ∩ B = {6}, A ∩ C = {4, 6}, B ∩ C = {6}. Pairs sum: 1 + 2 + 1 = 4. Triple: A ∩ B ∩ C = {6} (|A ∩ B ∩ C| = 1).

Union: 8 - 4 + 1 = 5. The true union A ∪ B ∪ C is {2, 3, 4, 5, 6}, which has size 5. The exact probability is 5/6.

Experiment

To verify this in the Inclusion-Exclusion module:

Set the Sides control to 6.
Set the Threshold t control to 4.
Set the Terms control to 3.

Observe that the Single Sum is 8, Pair Sum is 4, and Triple is 1. The True Union is 5, with probability 5/6 (0.833333). If you next set Threshold t to 1 and Terms to 1, the Partial Term Sum is 11/6, which is correctly labelled as a partial sum exceeding 1, not a valid probability.

Limitations

This model assumes a perfectly fair, uniform N-sided die, which may not exist physically for arbitrary N. The visualization is limited to three specific sets (Even, Divisible by 3, ≥ t). Calculating terms beyond three sets requires significantly more pairwise, triple, and higher-order intersections which this UI does not display. Additionally, exact fractions stay visible alongside decimal approximations rounded to six decimal places.

References

The mathematical background of this principle is found in the following resources:

Probability for Computer Scientists: OR (Inclusion-Exclusion) - Explains the fundamental probability of unions using inclusion-exclusion.