Poincaré's sieve

We write |A| for the cardinality of a finite set A—that is, its number of elements.

Thus, |A₁ $\cup \backslash cup$ A₂| = |A₁| + |A₂| − |A₁ $\cap \backslash cap$ A₂|,

|A₁ $\cup \backslash cup$ A₂ $\cup \backslash cup$ A₃| = |A₁| + |A₂| + |A₃| − (|A₁ $\cap \backslash cap$ A₂| + |A₂ $\cap \backslash cap$ A₃| + |A₁ $\cap \backslash cap$ A₃|) + |A₁ $\cap \backslash cap$ A₂ $\cap \backslash cap$ A₃|, and so on.

This formula is also known as the inclusion–exclusion principle. It is used in counting problems, of which the hat-check problem is a classic example: if the hats belonging to a gathering of n people are randomly distributed, what is the probability that no one leaves with their own hat? Let A*_i be the event that person i left with their own hat. Poincaré's sieve formula shows that this probability tends to 1/e* (approximately 36.8%).