section_path: Principle of inclusion and exclusion
section_name: Principle of inclusion and exclusion
paragraph_text: Principle of inclusion and exclusion
  
  The inclusion–exclusion principle is a technique for counting the elements in a union of two finite sets in terms of the sizes of the two sets and their intersection. It can be expressed symbolically as | A ∪ B | = | A | + | B | − | A ∩ B |. {\displaystyle |A\cup B|=|A|+|B|-|A\cap B|.}
  
  A more general form of the principle gives the cardinality of any finite union of finite sets: | A 1 ∪ A 2 ∪ A 3 ∪ … ∪ A n | = (| A 1 | + | A 2 | + | A 3 | + … | A n |) − (| A 1 ∩ A 2 | + | A 1 ∩ A 3 | + … | A n − 1 ∩ A n |) + … + (− 1) n − 1 (| A 1 ∩ A 2 ∩ A 3 ∩ … ∩ A n |). {\displaystyle {\begin{aligned}\left|A_{1}\cup A_{2}\cup A_{3}\cup \ldots \cup A_{n}\right|=&\left(\left|A_{1}\right|+\left|A_{2}\right|+\left|A_{3}\right|+\ldots \left|A_{n}\right|\right)\\&{}-\left(\left|A_{1}\cap A_{2}\right|+\left|A_{1}\cap A_{3}\right|+\ldots \left|A_{n-1}\cap A_{n}\right|\right)\\&{}+\ldots \\&{}+\left(-1\right)^{n-1}\left(\left|A_{1}\cap A_{2}\cap A_{3}\cap \ldots \cap A_{n}\right|\right).\end{aligned}}}