# Zkouska 11.1.2007

<{ForumPost(poster="marie 56", timestamp=2007-01-12 17:31:12)}>
1. Odvodte vzorec pro pocet permutaci mnoziny {1,2,...,n} s prave jednim pevnym bodem.  
2.  
a) Definujte proste zobrazeni mnoziny X do mnoziny Y. Naleznete priklad mnoziny X a zobrazeni X -> X, ktere je proste ale neni na.  
b) Na mnozine X = {1, 2,...,8} definujeme relaci castecneho usporadani takto: aRb prave kdyz a=b nebo b>a+2. Nakreslete Hasseuv diagram teto usporadane mnoziny.  
c) usporadejte nasledujici funkce (kde promenna n je prirozene cislo) podle rychlosti rustu, tj. urcete, ktera z nich pro velke n nabyva nejvetsi hodnoty, druhe nejvetsi, atd.  
10^n    (2n)!    10n^5    2^n^2  
3. Bud G=(V,E) graf. Zobrazeni f: V->V nazveme automorfismem grafu G, pokud je to isomorfismus grafu G s nim samotnym. Kolik automorfismu maji Kn (uplny graf na n vrcholech), Pn (cesta delky n), Cn (kruznice delky n).  
4.Zformulujte a dokazte Erdosovo Szekeresovo lemma.
<{/ForumPost}>