fundamental.cz
ZÁKLADNÍ POJMYVĚTY A POUČKYZAJÍMAVOSTIÚLOHYNÁSTROJEZÁKLADNÍ ŠKOLANĚCO KE ČTENÍ

Důkaz vztahu pro počet všech podmnožin n-prvkové množiny

Chceme dokázat, že počet všech podmnožin množiny o n prvcích je roven 2n. Uvedené tvrzení je možné dokázat například matematickou indukcí nebo pomocí binomické věty. My zde použijeme ještě jiný způsob:

Pro ilustraci uvedeme příklad:


Máme určit počet všech podmnožin množiny A = {a,b,c}.

Je tedy n = 3, pořadí prvků ponecháme abc. Největší 3-ciferné binární číslo je 111(2), počet všech podmnožin je tedy roven 111(2) + 1(2) = 1000(2) = 23(10).

Výše uvedený myšlenkový postup si můžeme znázornit. Použijeme dva sloupce, do levého budeme zapisovat podmnožiny naší množiny A a do pravého sloupce jejich reprezentaci pomocí jedniček a nul:

{ } 000 prázdná množina

{ c} 001

{ b } 010

{ bc} 011

{a } 100

{a c} 101

{ab } 110

{abc} 111 množina A

Posloupnosti jedniček a nul v pravém sloupci považujeme za binární čísla. Všimneme si, že nabývají všech hodnot mezi nulou a největším číslem tvořeném n ciframi (řádky jsou uspořádané od nejmenší hodnoty po největší, na prvním řádku je nula, číslo na každém dalším řádku je o jedničku větší než na předchozím řádku). Mezi podmnožiny zahrnujeme jak prázdnou množinu tak i množinu A samotnou.