Inkluziveco-ekskluda principo

Se ${\displaystyle A_{1},A_{2}\dots A_{n}}$ estas laŭvolaj aroj, tiam

${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|+}$

${\displaystyle +\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \dots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|}$ ,

kie ${\displaystyle \left|A_{k}\right|}$ signifas povon de aro ${\displaystyle A_{k}\,}$

Ekzemplo

Por tri fina aroj ${\displaystyle A_{1},A_{2},A_{3}}$ nombro de elementoj de ilia kunaĵo estas:

${\displaystyle \left|A_{1}\cup A_{2}\cup A_{3}\right|=\left|A_{1}\right|+\left|A_{2}\right|+\left|A_{3}\right|-}$

${\displaystyle -\left|A_{1}\cap A_{2}\right|-\left|A_{1}\cap A_{3}\right|-\left|A_{2}\cap A_{3}\right|+}$

${\displaystyle +\left|A_{1}\cap A_{2}\cap A_{3}\right|}$

Se elemento ${\displaystyle a}$ apartenas precize al ${\displaystyle m}$ en aroj ${\displaystyle A_{1},A_{2}\dots A_{n}}$ . En kunaĵo ${\displaystyle \left|\bigcup _{i=1}^{n}A_{i}\right|}$ ĝi estas kalkulata unu fojon. En esprimo ${\displaystyle \sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|+\sum _{i,j,k\,:\,1\leq i<j<k\leq n}\left|A_{i}\cap A_{j}\cap A_{k}\right|-\ \dots }$

${\displaystyle \ \dots +(-1)^{n-1}\left|A_{1}\cap \cdots \cap A_{n}\right|}$

nombro de kalkuloj de sola elemento estas:

${\displaystyle m-{m \choose 2}+{m \choose 3}+\dots +(-1)^{m}{m \choose {m-1}}+(-1)^{m+1}1=}$

${\displaystyle =1-{m \choose 0}+{m \choose 1}+\dots +(-1)^{m}{m \choose {m-1}}+(-1)^{m+1}{m \choose m}}$ ,

ĉar ĝi estas en m-aroj en ${\displaystyle A_{1},A_{2}\dots A_{n}}$ , ${\displaystyle {m \choose 2}}$ en aroj ${\displaystyle A_{i}\cap A_{j},1\leq i<j\leq n}$ kpt.

Ĉar dunomo de Newton esprimo estas ${\displaystyle 1-(1-1)^{m}=1-0=1}$ , kio pruvas veron de Inkluziveco-ekskluda principo.