Pravidlo součtu

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

V matematickém oboru kombinatorika, pravidlo součtu nebo adiční princip je základní kombinatorický princip. Jednoduše řečeno, je to úvaha, že když máme a způsobů, jak něco udělat a b jak dělat něco jiné a nemožno dělat obojí ve stejném čase, pak existuje a + b způsobů jak vybrat 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. Tedy, když S_{1}, S_{2},..., S_{n} jsou vzájemně disjunktní množiny, pak platí:

|S_{1}|+|S_{2}|+\cdots+|S_{n}| = |S_{1} \cup S_{2} \cup \cdots \cup S_{n}|

 

 

 

 

Jednoduchý příklad[editovat | editovat zdroj]

Žena se dnes rozhodla nakoupit v jedném 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 nabytkářství nebo v bižuterii (3 možnosti). 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[editovat | editovat zdroj]

Hlavní článek: Princip inkluze a exkluze

Princip inluze a exkluze možno chápat jak 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 byli disjunktní). Tvrdí, že pokud A1, ..., 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 < j \le n}\left|A_i\cap A_j\right| \\
& {}\qquad +\sum_{i,j,k\,:\,1 \le i < j < k \le n}\left|A_i\cap A_j\cap A_k\right|-\ \cdots\ + \left(-1\right)^{n-1} \left|A_1\cap\cdots\cap A_n\right|.
\end{align}

Související principy[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Rule of sum na anglické Wikipedii.