Pravidlo součtu

Pravidlo 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. 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

Ž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). 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 A₁, ..., A_n jsou konečné množiny, pak

{\begin{aligned}{\biggl |}\bigcup _{i=1}^{n}A_{i}{\biggr |}&{}=\sum _{i=1}^{n}\left|A_{i}\right|-\sum _{i,j\,:\,1\leq i<j\leq n}\left|A_{i}\cap A_{j}\right|\\&{}\qquad +\sum _{i,j,k\,:\,1\leq i<j<k\leq 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{aligned}}

Reference

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

Související principy