Cesko.wiki Pravidlo součtu
Author
Albert FloresPravidlo součtu nebo adiční princip je základní kombinatorický princip v kombinatorice. Jednoduše řečeno se jedná o úvahu, že když máme a způsobů, jak něco udělat, a b, jak dělat něco jiného, a není možné dělat obojí ve stejnou chvíli, pak existuje a + b způsobů, jak vybrat některou činnost.
Víc formálně, pravidlo součtu je fakt o teorii množin. Tvrdí, že součet velikostí konečné kolekce disjunktních množin je velikost sjednocení těchto množin. +more Tedy, když S_{1}, S_{2},. , S_{n} jsou vzájemně disjunktní množiny, pak platí:.
{{vzorec||S_{1}|+|S_{2}|+\cdots+|S_{n}| = |S_{1} \cup S_{2} \cup \cdots \cup S_{n}| }}
Jednoduchý příklad
Žena se dnes rozhodla nakoupit v jednom obchodě, buď v severní, nebo jižní části města. Pokud navštíví sever města, nakupovat bude v nákupním centru, nebo v nábytkářství, nebo v bižuterii (3 možnosti). +more Pokud půjde na jih, nakoupí v textilním centru nebo v obuvnictví (2 možnosti).
Pak existuje 3+2=5 obchodů, v kterých může žena dnes nakoupit.
Souvislost s principem inkluze a exkluze
Princip inkluze a exkluze možno chápat jako zobecnění pravidla součtu v tom smyslu, že také vypočítává počet prvků v sjednocení nějakých množin (ale nepožaduje, aby množiny byly disjunktní). Tvrdí, že pokud A1, . +more, An jsou konečné množiny, pak.
: \begin{align} \biggl|\bigcup_{i=1}^n A_i\biggr| & {} =\sum_{i=1}^n\left|A_i\right| -\sum_{i,j\,:\,1 \le i