Inkluziveco-ekskluda principo

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

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

| ⋃_{i = 1}^{n} A_{i} | = \sum_{i = 1}^{n} | A_{i} | - \sum_{i, j : 1 \leq i < j \leq n} | A_{i} \cap A_{j} | +

+ \sum_{i, j, k : 1 \leq i < j < k \leq n} | A_{i} \cap A_{j} \cap A_{k} | - \dots + (- 1)^{n - 1} | A_{1} \cap \dots \cap A_{n} |

,

kie $| A_{k} |$ 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:

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

- | A_{1} \cap A_{2} | - | A_{1} \cap A_{3} | - | A_{2} \cap A_{3} | +

+ | A_{1} \cap A_{2} \cap A_{3} |

Pruvo

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

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

nombro de kalkuloj de sola elemento estas:

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

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

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

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

Inkluziveco-ekskluda principo

Teoremo

Ekzemplo

Pruvo

Navigada menuo

Serĉi