Matfyz Wiki

Kombinatorika a grafy II - Jelínek 16.1.2020

borek at 2020-02-01 14:27:46

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 http://latex.codecogs.com/gif.latex?$%20%5Bn%5D=%7B1%2C2%2C...%2Cn%7D%20${: alt="[n]={1,2,...,n} [n]=\{1,2,...,n\} " type="image/"}. 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 http://latex.codecogs.com/gif.latex?$%202%5E%7Bn-1%7D%20${: alt="2n−1 2^{n-1} " type="image/"}, například tak, že vybereme jeden prvek, který budou všechny obsahovat, a dáme k němu všechny podmnožiny zbylých http://latex.codecogs.com/gif.latex?$n-1${: alt="n−1n-1" type="image/"} prvků. Proč jich nemůžeme vybrat víc? Uvědomíme si, že oněch http://latex.codecogs.com/gif.latex?$%202%5E%7Bn-1%7D%20${: alt="2n−1 2^{n-1} " type="image/"} 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.