Addition principle

Inclusion–exclusion principle

The inclusion–exclusion principle (also known as the sieve principle) can be thought of as a generalization of the rule of sum in that it too enumerates the number of elements in the union of some sets (but does not require the sets to be disjoint). It states that if A₁, ..., A_n are finite sets, then $${\displaystyle \left|\bigcup _{i=1}^n{A}_i\right|=\sum _{i=1}^n\left|A_i\right|-\sum _{i,j:1\le i<j\le n}\left|A_i\cap A_j\right|+\sum _{i,j,k:1\le i<j<k\le n}\left|A_i\cap A_j\cap A_k\right|-\cdots +(-1{)}^{n-1}\left|A_1\cap \cdots \cap A_n\right|.}$$

Subtraction principle

Similarly, for a given finite set S, and given another set A, if ${\displaystyle A\subset S}$, then ${\displaystyle |A^c|=|S|-|A|}$. To prove this, notice that ${\displaystyle |A^c|+|A|=|S|}$ by the addition principle.

Applications

The addition principle can be used to prove Pascal's rule combinatorially. To calculate ${\displaystyle (\genfrac{}{}{0ex}{}{n+1}{k})}$, one can view it as the number of ways to choose k people from a room containing n children and 1 teacher. Then there are ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k})}$ ways to choose people without choosing the teacher, and ${\displaystyle (\genfrac{}{}{0ex}{}{n}{k-1})}$ ways to choose people that includes the teacher. Thus ${\displaystyle (\genfrac{}{}{0ex}{}{n+1}{k})=(\genfrac{}{}{0ex}{}{n}{k})+(\genfrac{}{}{0ex}{}{n}{k-1})}$.

The addition principle can also be used to prove the multiplication principle.