Kombinatorika a grafy II - Jelínek 16.1.2020

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.