— — Princip inkluze a exkluze (PIE)

Princip inkluze a exkluze (PIE)

Příklad:

|A_{1} ∪ A_{2}| = |A_{1}| + |A_{2}| − |A_{1} ∩ A_{2}|

|A_{1} ∪ A_{2} ∪ A_{3}| = |A_{1}| + |A_{2}| + |A_{3}| − |A_{1} ∩ A_{2}| − |A_{1} ∩ A_{3}| − |A_{2} ∩ A_{3}| + |A_{1} ∩ A_{2} ∩ A_{3}|

VĚTA (PIE):

Jsou-li A_{1}, A_{2}, …, A_{n} konečné množiny:

| ⋃_{i=1}^{n} A_{i}| = ∑_{k=1}^{n} \underbrace{(−1)^{k+1}}_{(parita)} · ∑_{I∈\binom{\{1,..,n\}}{k}}| ⋂_{i∈I} A_{i}|

(Ve vnořené sumě sčítáme přes všechny k-prvkové podmnožiny množiny 1..n.)

DŮKAZ:

Nechť x je libovolný prvek z A_{1} ∪ A_{2} ∪ ⋯ ∪ A_{n}. Pro n = 1, n = 2 viz diagramy množin, nakreslit si, kam který prvek přispívá: +1 − 1 + 1 ⋯

Kolikrát je počítán x vlevo, kolikrát vpravo? Vlevo jednou — triviální.

Vpravo Nechť j označuje počet množin A_{i}, do kterých patří x. Příklad:

x ∈ A_{1}, …, A_{j}
x ∉ A_{j+1} , …, A_{n}

Pak platí:

#x = \binom{j}{1} − \binom{j}{2} + \binom{j}{3} − ⋯ + (−1)^{j−1} \binom{j}{j}

= ∑_{i=1}^{j}(−1)^{i−1} \binom{j}{i} + 1 − 1

Obracíme znaménko a paritu:

= 1 − ∑_{i=0}^{j}(−1)^{i}\binom{j}{i}

= 1 − (−1 + 1)^{j}

= 1

Q.E.D.

Příklad:

|X| = {1, …, n}, |Y | = {1, …, l}, n ≥ l

Kolik existuje zobrazení z X na Y? Všech zobrazení z X do Y je l^{n}. Nechceme počítat ta, ve kterých se na nějaký prvek Y

nezobrazuje žádný prvek z X:

∃ y ∈ Y : ∀x ∈ X, f(x) ≠ y.

— — Princip inkluze a exkluze (PIE)

Pro všechna i = 1, …, l platí:

A_{i} = {j: X → Y | ∀x ∈ X, f(x) ≠ i} = {j: X → Y − {i}}

|A_{i}| = (l − 1)^{n}

Pro i_{1} ≠ i_{2}:

A_{i_{1}} ∩ A_{i_{2}} = {f: X → Y − {i_{1}, i_{2}}}
|A_{i_{1}} ∩ A_{i_{2}}| = (l − 2)^{n}

Pro \{i_{1}, …, i_{k}\} ∈ \binom{\{1, …, l\}}{k}:

A_{i_{1}} ∩ ⋯ ∩ A_{i_{k}} = {f: X → Y − {i_{1}, …, i_{k}}} {A_{i_{1}} ∩ ⋯ ∩ A_{i_{k}}} = (l − k)^{n}

Počet zobrazení z X na Y je:

l^{n} − | ⋃_{i=1}^{l} A_{i}| =

= l^{n} − (\binom{l}{1}(l − 1)^{n} − \binom{l}{2}(l − 2)^{n} + \binom{l}{3}(l − 3)^{n} − ⋯ +

+(−1)^{l−2} \binom{l}{l − 1}(l − (l − 1)^{n}) + (−1)^{l−1} \binom{l}{l}(l − l)^{n}) =

= ∑_{k=0}^{l−1}(−1)^{k}\binom{l}{k}(l − k)^{n}