Kombinatorika a grafy II - Jelínek 16.1.2020

Vše co není uvedeno jinde
borek
Matfyz(ák|ačka) level I
Příspěvky: 5
Registrován: 1. 2. 2020 12:33
Typ studia: Informatika Bc.

Kombinatorika a grafy II - Jelínek 16.1.2020

Příspěvek od borek »

Standardně dvě otázky, problém a věta:
1) Napište a dokažte lemma o velikosti orbity a stabilizátoru.
2) Mějme množinu $ [n]=\{1,2,...,n\} $. Kolik jejích podmnožin můžeme vybrat tak, aby každé dvě měly průnik?

Řešení:
1) Viz přednáška.
2) Rozmyslíme si, že jich můžeme vybrat $ 2^{n-1} $, například tak, že vybereme jeden prvek, který budou všechny obsahovat, a dáme k němu všechny podmnožiny zbylých $n-1$ prvků. Proč jich nemůžeme vybrat víc? Uvědomíme si, že oněch $ 2^{n-1} $ podmnožin je právě polovina všech. Proč právě polovina? Protože když vybereme nějakou podmnožinu, tak její doplněk již vybrat nemůžeme.
Odpovědět

Zpět na „Ostatní“