Inclusion-Exclusion

Definition For any two events $A$ and $B$ in a probability model,

as in The Addition Rule. For any three events $A$, $B$ and $C$,

The same identities hold for the numbers of elements of finite sets, with $\lvert A \rvert$ in place of $P(A)$. Neither version needs independence or equally likely outcomes. Equal likelihood matters only when counts are turned into probabilities by dividing by the size $\lvert \Omega \rvert$ of a finite sample space $\Omega$. The reason for the signs is visible one outcome at a time. An outcome in exactly one of the events is counted once by the first three terms and never again. An outcome in exactly two is counted twice and subtracted once. An outcome in all three is counted three times, subtracted three times and added back once. So every outcome of the union is counted exactly once, and outcomes outside the union are never counted. For more events the pattern continues with alternating signs, adding the probabilities of the single events, subtracting those of all pairwise intersections, adding those of all triple intersections and so on. Later cards use the shorthand

in which the three-event formula reads $P(A \cup B \cup C) = S_1 - S_2 + S_3$.

Definition For three events $A$, $B$ and $C$, the pairwise intersections are $A \cap B$, $A \cap C$ and $B \cap C$. The event $A \cap B$ contains every outcome that lies in both $A$ and $B$, including the outcomes that also lie in $C$. The outcomes in $A$ and $B$ but not in $C$ form the smaller event $A \cap B \cap C^{c}$, with

Inclusion-exclusion uses the full pairwise intersections, not these smaller pieces.

Definition The triple intersection $A \cap B \cap C$ is the event that all three events occur. The single and pairwise probabilities do not determine it in general, so it has to be given or found separately. Once they are fixed, the triple probability determines every other piece of the diagram, and it can take exactly those values for which all eight disjoint regions described in the next card have nonnegative probability.

Definition Three events split the sample space into eight disjoint regions, one for each choice of being inside or outside each event, from $A \cap B \cap C$ to $A^{c} \cap B^{c} \cap C^{c}$. Every outcome lies in exactly one region, so the eight region probabilities add up to $1$, and the seven regions inside the union add up to $P(A \cup B \cup C)$. The regions with exactly two events come from the pairwise card, the outside region has probability $1 - P(A \cup B \cup C)$, and the region with only $A$ has probability

with the same pattern for only $B$ and only $C$. Supplied single, pairwise and triple values describe a possible model exactly when all eight regions computed this way are nonnegative.

Definition The event that exactly one of $A$, $B$ and $C$ occurs is the union of the three disjoint regions $A \cap B^{c} \cap C^{c}$, $A^{c} \cap B \cap C^{c}$ and $A^{c} \cap B^{c} \cap C$, so its probability is the sum of their probabilities. In the shorthand of the first card,

To check the weights, follow one outcome. An outcome in exactly one event contributes $1$ to the right side. An outcome in exactly two events contributes $2 - 2 \cdot 1 = 0$, and an outcome in all three contributes $3 - 2 \cdot 3 + 3 \cdot 1 = 0$.

Definition The event that exactly two of $A$, $B$ and $C$ occur is the union of the three disjoint regions $A \cap B \cap C^{c}$, $A \cap B^{c} \cap C$ and $A^{c} \cap B \cap C$. Each pairwise intersection contains the triple intersection, so $S_2$ includes every outcome of $A \cap B \cap C$ three times and every outcome in exactly two events once. Therefore