Inkluziveco-ekskluda principo

Inkluziveco-ekskluda principo por tri aroj

Inkluziveco-ekskluda principo estas regulo de kombinatoriko, kiu ebligas kalkuli nombrojn de elementoj de kunaĵo de aroj. Aŭtoro probable estas Abraham de Moivre eĉ iufoje estas nomata el nomoj de matematikistoj James Joseph Sylvester kaj Henri Poincaré

Teoremo

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

$\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|+$

$+\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 $\left|A_{k}\right|$ signifas povon de aro $A_{k}\,$

Ekzemplo

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

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

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

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

Pruvo

Se elemento $a$ apartenas precize al $m$ en aroj $A_{1},A_{2}\dots A_{n}$. En kunaĵo $\left|\bigcup _{i=1}^{n}A_{i}\right|$ ĝi estas kalkulata unu fojon. En esprimo $\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$

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

nombro de kalkuloj de sola elemento estas:

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

$=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 $A_{1},A_{2}\dots A_{n}$, ${m \choose 2}$ en aroj $A_{i}\cap A_{j},1\leq i<j\leq n$ kpt.

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