Princip inkluze a exkluze

• Princip inkluze a exkluze je často používaný kombinatorický princip
• Udává počet prvků sjednocení několika množin pomocí počtu prvků průniku jednotlivých množin
• Pro množiny $A_1,...,A_n$ platí $|A_1\cup A_2\cup ...\cup A_n|={\sum }_{\varnothing \ne l\subseteq \{1,2,...,n\}}(-1{)}^{|I|}|{\cap }_{i\in I}{A}_i|$
• Zastavme se nejdřív nad tím, co princip inkluze a exkluze říká.
  • Na levé straně rovnosti je počet prvků, které patří do sjednocení $A_1\cup ...\cup A_n$. tj. alespoň do jedné z $A_1,...A_n$.
  • Na pravé straně je součet výrazů $(-1{)}^{|I|+1}|{\cap }_{i\in I}{A}_i|$, kde $I$ probíhá přes všechny neprázdné podmnožiny množiny $set1,...,n$. $|{\cap }_{i+inI}{A}_i|$ je počet prvků průniku množiny, jejichž index patří do $I$
    • např. pro $I=\{2,3,5\}$ je to $|A_2\cap A_3\cap A_5|$. Výraz $(-1{)}^{|I|+1}$ je roven $1$, pokud $I$ obsahuje lichý počet prvků, a je roven $-1$, pokud $I$ obsahuje sudý počet prvků.
• Tedy v součtu na pravé straně jsou počty prvků všech možných průniků (jednočlenných, dvoučlenných, …, až po $n$-členné) utvořené z $A_1,...,A_n$, přitom počet prvků daného průniku je se znaménkem $+$ pro průniky lichého počtu množin a se znaménkem $-$ pro průníky sudého počtu množin.

Důkaz

Příklad

• V jedné malé základní škole fungují tři kroužky. Florbalový kroužek navštěvuje 18 dětí, výtvarný 14 dětí a šachový je osmičlenný. Z florbalistů jsou dva šachisté a čtyři výtvarníci. Do výtvarného a zároveň do šachového kroužku chodí tři děti. Jedno dítě chodí na všechny tři kroužky. Kolik dětí navštěvuje alespoň jeden ze tří uvedených kroužků?
  • Řešení: $|F\cup V\cup \check{S}|=18+14+8-2-4-3+1=32$

Navigace

Předchozí: Binomická věta Následující: Dirichletův princip Celý okruh: 1. Teoretické základy informačních technologií