inklusjoneksklusjonprinsippet

The principle of inclusion-exclusion is a counting technique used in combinatorics to determine the number of elements in the union of multiple sets. It is particularly useful when dealing with overlapping sets where simply summing the sizes of individual sets would lead to overcounting elements present in multiple sets.

The basic idea of the principle can be illustrated with two sets, A and B. The number of elements in the union of A and B, denoted as |A ∪ B|, is calculated by adding the number of elements in A and the number of elements in B, and then subtracting the number of elements in their intersection (|A ∩ B|). This subtraction corrects for the elements that were counted twice, once in A and once in B.

For three sets, A, B, and C, the principle is extended. The size of the union |A ∪ B ∪ C| is found by summing the sizes of the individual sets, subtracting the sums of the sizes of all pairwise intersections, and then adding back the size of the intersection of all three sets. This alternating addition and subtraction pattern continues for any number of sets, with the sign depending on the number of sets being intersected.

The inclusion-exclusion principle is a fundamental tool for solving various counting problems, such as determining the number of integers in a given range that are divisible by a specific set of numbers, or counting derangements (permutations where no element appears in its original position).