Inclusion–exclusion: repair overlap systematically

For two finite sets, add their sizes and subtract the intersection once. A shared object initially contributed twice and should contribute once. For three sets, an object in all three initially contributes three times, then is subtracted in each of three pairwise intersections and contributes zero. Adding the triple intersection restores its contribution to one. Tracking a single object's coefficient is more reliable than trying to memorize a pattern of signs from a diagram.

In the general finite formula, an object belonging to exactly r sets appears in every intersection chosen from those r sets. Its total coefficient is the alternating sum of the nonempty binomial coefficients from row r, which equals one. An object belonging to no set contributes zero. This proves that the formula counts the union exactly once per member. Finiteness makes every sum and intersection count unambiguous without convergence questions.

To count objects with none of several properties, work inside a finite universe and subtract the union of the forbidden-property sets. Begin by describing an individual property and an intersection of several properties. A formula involving an intersection is useful only if it counts objects satisfying all selected requirements simultaneously. It does not mean objects satisfying exactly those requirements; other forbidden properties are still permitted within that intersection.

A derangement is a permutation of n labelled positions in which no position retains its original label. Let the ith forbidden set contain permutations fixing position i. Fixing a specified collection of j positions leaves n minus j labels to permute freely, giving n minus j factorial possibilities. There are n choose j collections of fixed positions. This uniform intersection count makes inclusion–exclusion collapse into a short sum indexed only by j.

Dividing the derangement count by n factorial gives the probability of no fixed position under a uniform random permutation. Its finite alternating sum tends to the exponential series value one over e as n grows. For a particular n, retain the finite sum when an exact answer is required. The limit does not mean fixed-position events are independent; they are dependent because fixing one position changes the available labels for every other position.

Inclusion–exclusion scales poorly when every intersection requires a separate difficult calculation, since there can be exponentially many terms. Symmetry made derangements tractable by giving all j-fold intersections the same size. In a new problem, search first for such shared structure. Also check impossible intersections explicitly: contradictory properties contribute zero rather than a guessed product. The technique handles overlap exactly, but it does not remove the need to understand the objects in each intersection.