In combinatorics (combinatorial
mathematics), 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
where A and B are two finite
sets and |S| indicates the cardinality of a set S (which may be considered as the number of
elements of the set, if the set is finite).
The formula expresses the fact that the sum of the sizes of the two sets may be
too large since some elements may be counted twice. The double-counted elements
are those in the intersection of
the two sets and the count is corrected by subtracting the size of the
intersection.

The principle is more clearly seen in the case of
three sets, which for the sets A, B and C is given by

This formula can be verified by counting how many
times each region in the Venn diagram figure is
included in the right-hand side of the formula. In this case, when removing the
contributions of over-counted elements, the number of elements in the mutual
intersection of the three sets has been subtracted too often, so must be added
back in to get the correct total

## 0 comments:

## Post a Comment

Let us know your responses and feedback