Z poslední přednášky: Načali jsme "problém šátnářky", zjišťovali jak "veliké" je n!. Zadefinovali jsme X nad k, kde X je množina a k číslo. To se nám bude nyní hodit pro dokončení důkazu Principu inluze a exkluze, kteroužto jsme skončili.

K důkazu Principu inkluze a exkluze: skončili jsme v momentě, kdy máme ověřené pro n=1,2, předpokládáme n a ověřujeme n+1.
Sjednocení velikosti n+1 množin A_i můžeme rozdělit na sjednocení A_i i=1,..,n a velikost A_n+1 a odečíst průnik sjednocení A_i pro i=1,..,n a A_n+1. Tady vlastně přesně vycházíme z důkazu pro n=2, kde jednou množinou je sjednocení A_i i=1,..,n a druhou množinou je A_n+1. To je myslím v principu velice jednoduché.
Pokud tedy pokračuji, dostanu se až do okamžiku kdy budu sčítat všechny A_i při i=1,..,n a odčítat součty velikosti průniku dvou A_i a A_j při 1<=i<j<=n. Skončil jsem s dvouprvkovými průniky, pokračuji přičítáním velikosti tříprvkových průniků atd... až do posledního členu rozkladu velikosti sjednocení A_i pro i=1,..,n. Tím mám za sebou první ze dvou množin (na začátku jsme si je rozdělili na A_i s i=1,..,n a A_n+1. To jsme pak rozvedli podle indukce pro dvě množiny, mám tady tedy ještě velikost sjednocení A_i pro i=1,..,n v průniku s A_n+1) a pokračuji dále. Přičtu tedy velikost množiny A_n+1 (mohl bych efektivně tím, že bych první člen nesčital pouze do n, ale do n+1, ale to je teď jedno) a pokračuji rozkladem velikosti sjednocení A_i s průnikem A_n+1. Pokračovat bych měl opět stejně, tedy nejprve součet jednotlivých podmnožin A_i, pokračovat odečtením při průniku dvou z nich apod.. ovšem nyní pro nás jednu množinu představuje průnik A_i a A_n+1 a to celé ještě se záporným znaménkem. Prvním členem tedy bude záporný součet velikostí průniku A_i a A_n+1 sčítáno přes i=1,..,n, dalším členem pak bude součet průníku A_i, A_j a A_n+1, je to tedy zcela obdobné jen nesmím zapomenout na množinu A_n+1. Znaménko druhého členu bude kladné, třetího záporné apod.. díky tomu že rozebíráme člen se záporným znaménkem, všechny se nám tedy otáčí. Posledním členem tedy bude (-1)ⁿ⁺²|průnik A_i pro i=1,..,n+1|. (-1) na n+2 je proto, že nám záporným znaménkem přibyl jeden "obrat" znaménka, tedy +1 do exponentu znaménka. Nyní když se na to podíváme, můžeme si všimnout, že v jeden moment odčítáme velikost průniku A_i a A_j, kde 1<=i<j<=n a o kousek dál odečítáme velikost průniku A_i a A_n+1 pro i=1,..,n. To ale můžeme zjednodušeně napsat jako, že odečítáme velikost průniku A_i a A_j při 1<=i<j<=n+1. Podíváme-li se na to celé nakonec stejné, či přesněji, jednodušeji zapsatelné členy najdeme i pro sčítání velikostí průniku tří množin a stejně tak i dalších. A tím jsme vlastně hotovy. :-)

Ale zpět k šatnářce: víme, že počet všech kombinací odpovídá počtu všech permutací na množině {1,..,n} což je n!. Potřebujeme ale zjistit počet permutací na tytéž množině, kde se žádné k nezobrazuje na k, tedy žádný pán nedostane svůj klobouk.
Označme si tedy A_i množinu všech permutací kde i je pevným bodem, tedy i se zobrazí na i (to jsou ty rozdání kdy někdo dostane svůj klobouk, tedy odečteme-li všechny tyto permutace od n! máme hledaný výsledek :-)). Označíme-li si třeba X množinu všech permutací na {1,..,n} pak to co hledáme je |X - sjednocení A_i pro i=1,..,n|, tedy velikost množiny permutací po odstranění těch s pevným bodem. No a to vede rovnou na princip inkluze a exkluze... máme tady sjednocení množin A_i. My ale potřebujeme znát velikosti, zjistěme tedy kolika prvkové množiny A_i jsou ! Představíme-li si množinu A_i víme, že jeden prvek je pevný a to i-tý, ten je zobrazen na i (z def. A_i - máme i-tý prvek jako pevný), ale zbylých n-1 prvků se různě zobrazuje. Počet permutací a tedy počet prvků v A_i (A_i je množina permutací) je tedy (n-1)!. Počet prvků průniku dvou A_i (různých) je pak (n-2)! (opět jednoduché - bereme jednu kde je pevné i a druhou kde je pevné k. Máme tedy dva pevné body, neboť bereme jen ty permutace, které jsou v obou množinách, ostatní se ale zobrazují různě, tedy (n-2)!).
Teď již můžeme členy v rozkladu sjednocení podle PIE nahradit pouze velikostmi, jediné co zbývá je uvědomit si kolikrát každou z velikostí bereme. To můžeme poměrně snadno, vzpomeneme-li si na Tvrzení(2) z předchozí přednášky. Tam se tvrdilo, že počet k-prvkových podmnožin množiny X je roven kombinatorickému číslu velikosti X nad k. To je takové to tvrzení, kde jsou dva zápisy "nad" a jen se přesune absolutní hodnota, tedy v tomto případě velikost množiny.
Protože při sčítání velikosti průniku dvou A_i můžeme říct, že průniky děláme přes všechny dvouprvkové podmnožiny množiny {1,..,n} (podobně u průniku tří množin, přes všechny tříprvkové podmnožiny, apod..) a těch je právě n nad 2-ma (právě podle zmiňovaného tvrzení) je patrné, že velikost průniku dvou množin A_i budu přičítat (pozor, skutečně přičítat, na počátku je mínus, obracíme znaménka !) n nad 2-ma krát. Obdobně tří množin n nad 3-ma krát, apod... (najdu právě tolik k-prvkových podmnožin, provedu tedy právě tolik průniků k množin A_i a tolikrát se mi objeví v sumě velikostí jednotlivých průniků).
Obecný člen tedy bude vypadat (-1)^l(n nad l)(n-l)!. ((-1)-ka je na l-tou právě z toho důvodu, že máme X-sjednocení A_i (mínus !)). Rozpíšeme-li kombinatorická čísla, zjistíme, že můžeme snadno z celého součtu vytknout n! a následovat bude již pouze součet (1- (1/(1!)) + (1/(2!)) - ... (-1)ⁿ(1/(n!))) což se celé bliží k n!(1/e) kde e je skutečně pověstné e, tedy základ přirozeného logaritmu.

Latinský obdélník: dalším bodem byl pak Latinský obdelník, který se poměrně podobá problému šatnářce, je však více obecný. Představme si obdélník o k řádcích a n sloupcích, kde k<=n a v každém řádku se vyskytují všechna čísla 1,..,n, tj. každé právě jednou a v každém sloupci se vyskytuje každé z nich nejvýše jednou ! (Souvislost s šatnářkou ? Jednoduchá - v každém sloupci může být každé číslo 1,..,n nejvýše jednou, jsou to tedy obdélníky (případně čtverec :-)) kde neexistují žádné pevné body, žádné i se nezobrazí na i a to v žádném řádku (problém šatnářky je obdobný latinskému obdélníku s dvěma řádky a n sloupci !)).
Jednoduchá otázka pak je - kolik je Latinských trojúhelníků ?
Odpověď už ovšem tak jednoduchá není :-). Obecná a přesná odpověď se nezná. Můžeme řešit jednotlivé případy: je-li počet řádků 1, pak všech takových obdélníku je n! (počet všech kombinací n prvků o umístění do jednotlivých sloupců). Jsou-li řádky 2, pak jsme se dostali přesně k problému šatnářky, je to tedy n!(1/e) ale ještě krát n! neboť tolikrát můžeme uspořádat první řádek, což jsme u problému šatnářky neměli, tam byl uspořádán v pořadí 1,..,n. Tady však můžeme mít první řádek v libovolné kombinaci, tedy n! a druhý má vůči každé kombinaci prvního řádku n!/e uspořádání tak aby se neobjevil pevný bod, tedy (n!)²/e.
Odhadem pro libovolné k,n je (n!)^k/e^k-1. Je to horní odhad, tedy počet LO je <=. Dá se říci, že odhad je brán, jako bychom každý další řádek kontrolovali na pevné body pouze proti prvnímu řádku, nekontrolujeme tedy druhý řádek s třetím apod.. počet všech LO bude tedy jistě nižší, jak moc nižší však nevíme.

Poznámka: Charakteristická fce množin M v X. - Je funkce která nabývá hodnoty 1 pro x která patří do M a hodnoty 0 pro x co nepatří do M. M je podmnožina X. Funkce vlastně charakterizuje prvky množiny M vůči X. Počet všech podmnožin množiny X je 2^|X|, to můžeme snadno odvodit uvědomíme-li si co vlastně děláme. Jde o zobrazení X -> {0,1}. Pokud si připomeneme kolik je zobrazení množiny V -> Z což je |Z|^|V| (je poměrně jasné, určitě tedy z obrázku, ale popíšeme-li to - jde o to že každému bodu ze Z můžu přiřadit |V| možností. Druhému bodu můžu také |V|, neboť se jedná o zobrazení a není tedy podmínkou, že se body z V nesmí "použít" vícekrát). V případě počtu podmnožin jde tedy o zobrazení X -> {0,1}, nula je pak neexistence x v M, jednička existence. Pak je tedy |{0,1}|^|M|=2^|M|.

Definice: X; R podmnožina XxX. (X,R) relace na X.
(X,R) je uspořádání (úplné, lineární) jestliže R splňuje:
1) (x,x) e R     Tkz. podmínka reflexivity
2) (x,y) e R, (y,x) e R => x=y     podmínka antisymetrie (slábá)
3) (x,y) e R, (y,z) e R => (x,z) e R     podmínka transitivity
4) Pro každé dva prvky x,y buď (x,y) e R nebo (y,x) e R      podmínka úplnosti

Definice: (X,R) je částečné uspořádání jestliže splňuje 1,2,3 z předchozí definice o úplném uspořádání.

Definujme relaci R na P(X) kde P(X) je množina všech podmnožin X. (M,N) jsou v relaci R právě tehdy když M je podmnožinou (menší nebo rovno) množiny N.
Pak pozorujeme: (P(X), <=) je částečné uspořádaná množina:
1) M obsahuje M (reflexivita)
2) M obsahuje N, N obsahuje M => M=N (antisymetrie)
3) N obsahuje M, P obsahuje N => P obsahuje M
Není lineárně (úplně) uspořádaná, neplatí 4).

Nakreslili jsme si Hasseův diagram částečně uspořádané množiny.

Izomorfismus: Mějme uspořádané dvojice (X,R) a (Y,S).
f: X -> Y nazveme izomorfismus (X,R) a (Y,S) jestliže (i) f je prosté
(ii) f je na
(iii) (x,y) e R => (f(x),f(y)) e S
(iv) (f(x),f(y)) e S => (x,y) e R

Definice: f je vnoření splňuje-li (i), (ii), (iv) z předchozí definice.

Věta: Pro každou částečně uspořádanou množinu (X,R) existuje množina Y a zobrazení f: X -> P(X), které je vnoření (X,R) do (P(Y), <=).