Editing Inclusion–exclusion principle (section)

==Formula==
In its general formula, the principle of inclusion–exclusion states that for finite sets {{math|''A''<sub>1</sub>, ..., ''A<sub>n</sub>''}}, one has the identity

{{NumBlk|:|<math>\left|\bigcup_{i=1}^n A_i\right| = \sum_{i=1}^n |A_i| - \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| + \sum_{1 \leqslant i < j < k \leqslant n} |A_i \cap A_j\cap A_k| - \cdots + (-1)^{n+1} \left|A_1\cap\cdots\cap A_n\right|.</math>|{{EquationRef|1}}}}

[[Image:inclusion-exclusion-3sets.png|thumb|Each term of the inclusion–exclusion formula gradually corrects the count until finally each portion of the [[Venn diagram]] is counted exactly once.]]

This can be compactly written as

:<math>\left|\bigcup_{i=1}^n A_i\right| = \sum_{k=1}^n (-1)^{k+1} \left( \sum_{1 \leqslant i_1 < \cdots < i_k \leqslant n} | A_{i_1} \cap \cdots \cap A_{i_k} | \right)</math>

or

:<math>\left| \bigcup_{i=1}^n A_i\right| = \sum_{\emptyset\neq J\subseteq\{1,\ldots,n\}}(-1)^{|J|+1} \left |\bigcap_{j\in J} A_j\right|.</math>

In words, to count the number of elements in a finite union of finite sets, first sum the cardinalities of the individual sets, then subtract the number of elements that appear in at least two sets, then add back the number of elements that appear in at least three sets, then subtract the number of elements that appear in at least four sets, and so on. This process always ends since there can be no elements that appear in more than the number of sets in the union. (For example, if <math>n = 4,</math> there can be no elements that appear in more than <math>4</math> sets; equivalently, there can be no elements that appear in at least <math>5</math> sets.)

In applications it is common to see the principle expressed in its complementary form. That is, letting {{mvar|S}} be a finite [[universal set]] containing all of the {{math|''A<sub>i</sub>''}} and letting <math>\bar{A_i}</math> denote the complement of {{math|''A<sub>i</sub>''}} in {{mvar|S}}, by [[De Morgan's laws]] we have

:<math>\left|\bigcap_{i=1}^n \bar{A_i}\right| = \left|S - \bigcup_{i=1}^n A_i \right| =|S| - \sum_{i=1}^n |A_i| + \sum_{1 \leqslant i < j \leqslant n} |A_i\cap A_j| - \cdots + (-1)^n |A_1\cap\cdots\cap A_n|.</math>

As another variant of the statement, let {{math|''P''<sub>1</sub>, ..., ''P<sub>n</sub>''}} be a list of properties that elements of a set {{mvar|S}} may or may not have, then the principle of inclusion–exclusion provides a way to calculate the number of elements of {{mvar|S}} that have none of the properties. Just let {{math|''A<sub>i</sub>''}} be the subset of elements of {{mvar|S}} which have the property {{math|''P<sub>i</sub>''}} and use the principle in its complementary form. This variant is due to [[J. J. Sylvester]].<ref name="Roberts 2009 loc=pg. 405"/>

Notice that if you take into account only the first {{math|''m<n''}} sums on the right (in the general form of the principle), then you will get an overestimate if {{math|''m''}} is odd and an underestimate if {{math|''m''}} is even.