Kombinatorika a grafy II - Jelínek 16.1.2020

Vše co není uvedeno jinde

Kombinatorika a grafy II - Jelínek 16.1.2020

Příspěvekod borek » 1. 2. 2020 14:27

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.
borek
Matfyz(ák|ačka) level I
 
Příspěvky: 4
Registrován: 1. 2. 2020 12:33
Typ studia: Informatika Bc.

Zpět na Ostatní

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník