Inkluziveco-ekskluda principo

El Vikipedio, la libera enciklopedio
Saltu al: navigado, serĉo
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 Abrahamowi de Moivre eĉ iufoje estas nomata el nomoj de matematistoj Jamesa Josepha Sylvestera kaj Henriego Poincaré

Teoremo[redakti | redakti fonton]

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 \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|-\ \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[redakti | redakti fonton]

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[redakti | redakti fonton]

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 \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|-\ \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 \le i < j \le n kpt.

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