Pravidlo součtu - Rule of sum

v kombinatorika, pravidlo součtu nebo princip sčítání je základní princip počítání. Jednoduše řečeno, jde o myšlenku, že pokud ano A způsoby, jak něco udělat a B způsoby, jak dělat jinou věc, a nemůžeme dělat oba současně, pak existují A + B způsoby, jak vybrat jednu z akcí.

Formálně je pravidlo součtu faktem teorie množin. Uvádí, že součet velikostí konečné kolekce párů disjunktní sady je velikost spojení těchto množin. To je, pokud ${ displaystyle S_ {1}, S_ {2}, ..., S_ {n}}$ jsou párové disjunktní množiny, pak máme:

${ displaystyle | S_ {1} | + | S_ {2} | + cdots + | S_ {n} | = | S_ {1} cup S_ {2} cup cdots cup S_ {n} |}$

Jednoduchý příklad

Žena se dnes rozhodla nakupovat v jednom obchodě, a to buď v severní části města, nebo v jižní části města. Pokud navštíví severní část města, bude nakupovat v obchodech, obchodech s nábytkem nebo klenotnictví (3 způsoby). Pokud navštíví jižní část města, bude nakupovat v obchodě s oděvy nebo v obuvi (2 způsoby).

Existuje tedy 3 + 2 = 5 možných obchodů, kde by žena dnes mohla nakupovat.

Princip začlenění - vyloučení

Princip zahrnutí - vyloučení lze považovat za zobecnění pravidla součtu v tom, že také vyjmenovává počet prvků ve spojení některých množin (ale nevyžaduje disjunkce množin). Uvádí se v něm, že pokud A₁, ..., A_n jsou tedy konečné množiny

${ displaystyle { begin {aligned} { biggl |} bigcup _ {i = 1} ^ {n} A_ {i} { biggr |} & {} = sum _ {i = 1} ^ {n } left | A_ {i} right | - sum _ {i, j ,: , 1 leq i$

Viz také

• Kombinatorický princip
• Pravidlo produktu
• Princip začlenění - vyloučení

tento článek ne uvést žádný Zdroje. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Pravidlo součtu“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Březen 2009) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)