The connection between Principle of Inclusion-Exclusion and Combination

The Principle of Inclusion-Exclusion, commonly known as the Inclusion-Exclusion Principle, is a fundamental concept in combinatorics and set theory. It provides a systematic way to count or calculate the size of sets that satisfy certain conditions.

The principle states that if we want to count the number of elements in the union of several sets, we cannot simply add up the sizes of each individual set. Instead, we need to consider the intersections between the sets and make appropriate adjustments.

In its simplest form, the principle can be stated as follows:

For three sets A, B, and C, the size of their union is given by: |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|.

In general, for any finite collection of sets, the size of their union is calculated by alternately adding and subtracting the sizes of the intersections of all possible combinations of the sets.

But how to prove that?

You can observe that the Principle of Inclusion-Exclusion looks like

$\begin{array}{c}1=(\genfrac{}{}{0ex}{}{n}{1})-(\genfrac{}{}{0ex}{}{n}{2})+(\genfrac{}{}{0ex}{}{n}{3})+...+(-1{)}^{n+1}(\genfrac{}{}{0ex}{}{n}{n})\end{array}$$1=\binom{n}{1}-\binom{n}{2}+\binom{n}{3}+...+(-1)^{n+1}\binom{n}{n}\\$

And consider $a$$a$ belongs to m sets among $A_1,A_2,A_3,...,A_n$$A_1,A_2,A_3,...,A_n$

$a$$a$ will be counted in $\begin{array}{c}\sum _{i=1}^n|A_i|\end{array}$$\sum_{i=1}^n|A_i|\\$ $\begin{array}{c}(\genfrac{}{}{0ex}{}{m}{1})\end{array}$$\binom{m}{1}\\$ times, will be counted in $\begin{array}{c}\sum _{1\le i<j\le n}|A_i\cap A_j|\end{array}$$\sum_{1\le i<j\le n}|A_i\cap A_j|\\$ $\begin{array}{c}(\genfrac{}{}{0ex}{}{m}{2})\end{array}$$\binom{m}{2}\\$ times...

Therefore it will be counted in $\begin{array}{c}\sum _{i=1}^n|A_i|-\sum _{1\le i<j\le n}|A_i\cap A_j|+...(-1{)}^{n+1}\sum |A_1\cap A_2\cap ...\cap A_n|\end{array}$$\sum_{i=1}^n|A_i|-\sum_{1\le i<j\le n}|A_i\cap A_j|+...(-1)^{n+1}\sum |A_1\cap A_2\cap...\cap A_n|\\$

$\begin{array}{c}(\genfrac{}{}{0ex}{}{m}{1})-(\genfrac{}{}{0ex}{}{m}{2})+(\genfrac{}{}{0ex}{}{m}{3})+...+(-1{)}^{m+1}(\genfrac{}{}{0ex}{}{m}{m})=1\end{array}$$\binom{m}{1}-\binom{m}{2}+\binom{m}{3}+...+(-1)^{m+1}\binom{m}{m}=1\\$ times.