Inclusion-exclusion principle

From Knowino
Jump to: navigation, search

The inclusion-exclusion principle is a theorem of combinatorics relating to the number of elements in a finite set defined as the union of a finite collection of finite sets. The general form of the theorem for n sets A_1,\cdots,A_n is |A_1\cup\cdots\cup A_n|=\sum_{1\leq i\leq n}|A_i|-\sum_{1\leq i<j\leq n}|A_i\cap A_j|+\sum_{1\leq i<j<k\leq n}|A_i\cap A_j\cap A_k|-\cdots+(-1)^{n+1}|A_1\cap\cdots\cap A_n|, where |A| denotes the number of elements in a finite set |A| (called also the cardinality of A) . This equality may be explained intuitively by stating that if we simply take as the cardinality of the union the sum of the cardinalities of the constituent sets, then we have counted those elements that lie in more than one of those sets more than once, so we subtract the sum of the cardinalities of two-way intersections. However, now we have subtracted those elements contained in three or more sets too many times, so we have to add back the sum of the three-way intersections. This creates an overcount once again, and so we continue, alternating sign as we go, until we reach the intersection of all of the sets in the collection.

Information.svg Some content on this page may previously have appeared on Citizendium.
Personal tools