# Domácí úkoly 3 ## usp ### 1. Ano - reflexivita a antisymetrie díky "rovno", tranzitivita díky "menší než". Nejmenším a minimálním prvkem je $(1,1)$, jelikož bude v relaci s každou jinou dvojicí. Maximální prvek neexistuje, jelikož množina $\mathbb N$ je nekonečná (není omezená shora). Uspořádání není lineární, jelikož například $(4,4) \leq_A (6,4) \land (4,4) \leq_A (4,6)$ platí , ale již neplatí, že $(6,4) \leq_A (4,6)$. HD: https://ibb.co/7QYSJcb ### 2. Nejedná se o sl.antisymetrickou relaci (a tedy ne ani uspořádání) - jelikož $(4,6) \leq_B (6,4) \land (6,4) \leq_B (4,6)$ a přitom se jedná o rozdílné (uspořádané) dvojice. ### 3. Jedná se o uspořádání a je lineární, jelikož všechny dvojice jsou jednoznačně porovnatelné (nejprve srovnávám $a$ s $c$ a podle toho rozhoduji, zdali má smysl srovnávat $b$ s $d$) Opět platí, že nejmenším a i minimálním prvkem je $(1,1)$ a největší ani maximální prvky neexistují. HD: https://ibb.co/FqMWkkC ### 4. Relace splňuje všechny vlastnosti uspořádání (stejně jako v prvním příkladě se dají dokázat individuálním porovnáním $a$ s $c$, $b$ s $d$). Každý prvek je v alespoň jedné relaci oběma směry ($c = a \pm 1$ nebo $d = b \pm 1$), takže zde nenalezneme žádný minimální/maximální/největší/nejmenší prvek. HD:https://ibb.co/w7BzRXT ## diag Jedná se o relaci, která je jak symetrická, tak slabě antisymetrická. Prohozením prvků $x$ samozřejmě bude relace platit (jelikož se jedná o stejné proměnné) a jelikož $x = x$, je splněna i podmínka antisymetrie. Podmínky reflexivity a tranzitivity musí být také splněny - tyto dvě vlastnosti jsou společné jak pro ekvivalenci, tak částečné uspořádání. Aby byla relace reflexivní, musí obsahovat všechny prvky na diagonále (každý prvek v relaci sám se sebou) - čili menší relace (podmnožina) by tuto podmínku nesplňovala. Do této relace však ani nemůžeme přiřadit žádnou jinou, jelikož z podmínky symetrie bychom museli přiřadit i opačnou dvojici, což by zase narušilo podmínku antisymetrie. Z toho, že do relace nemůžeme přiřadit žádné prvky, ani žádné odebrat, znamená to, že se jedná o jedinou takovou relaci. ## poctyrel Obecně: počet k-prvkových podmnožin množiny o n prvcích je $n \choose k$. Zapíšeme-li kartézský součin tabulkou, pak vytvoření relací je zaškrtnutí $(0,1,2,3...n*n )$ libovolně zvolených čtverečků. Počet kombinací je založen na "volném" výběru, takže z celkového počtu kombinací odečtu ty prvky, které jsou "pevně" určeny - tzn. závisí na výběru předchozích prvků. Níže určím vždy maximální množinu - tedy kolik polí ($x$) můžu libovolně vybrat - a počet relací je roven počtu jejích podmnožin, tedy $2^x$ ### 1. Jedná se samozřejmě o počet podmnožin $N \times N$, čili množiny o $n \times n$ prvcích, což je rovno $(2^{(n * n)})$ ### 2. Pole na diagonále jsou předvyplněna (aby byla zaručena podmínka). Zbývá $n*(n-1)$ polí, která lze vyplnit libovolně. Relací by tedy mělo být $2^{n*(n-1)}$. ### 3. Symetrická matice se dá zjednodušit "odříznutím" horního trojúhelníku bez diagonály (platí-li relace $(32)$, pak bude platit i $(23)$, tzn. je vyplněna "automaticky"). Ten má rozměr odvěsen $(n-1)$ polí, takže z celé tabulky odřezávám $n*(n-1)/2$ polí. Platí $n*n - n*(n-1)/2 = \frac{n^2 + n}{2}$ (což se dá brát i tak, že tabulku přeříznu přesně v půlce a vrátím ($+$) půlku diagonály. ) Relací je celkem ${2^ \frac{n*n + n}{2}}$. ### 4. Antisymetrická relace se dá innterpretovat i jako relace, která není symetrická (očividně) - ale u slabé AS s výjimkou diagonály. Není jich tedy (počet všech $-$ počet symetrických), což by platilo pro silnou antisymetrii, ale je jich stejně jako symetrických, jelikož "povinnost vyplnit opačné pole" má pro variabilitu stejný důsledek jako "zákaz vyplnit opačné pole" (Pro ujasnění, "opačné pole" má prohozené souřadnice, v našem případě pořadí prvku v relaci) Relací je celkem ${2^ \frac{n*n + n}{2}}$. ## komb3 ### 1. Levá strana se dá přepsat na $r \choose 0$ $+$ $r+1 \choose 1$ $+$ $r+2 \choose 2$ $+ \dots$ (kombinační symetrie, místo prvního členu $r \choose r$ píšu $r \choose 0$) . Zamysleme se nad posledním členem. Ten je roven $n \choose r-1$, to se dá ale zapsat i (vzhledem k pravé straně) jako $(n+1)-1 \choose (r+1)-2$. Co to kombinačně vyjadřuje? Je to počet kombinací, které dostanu, když jeden prvek (řekněme zprava) fixovaně vyberu - tím se nám sníží variabilita o 1 prvek, z kterých můžu vybírat (horní část KČ) a také o 1 výběr (dolní část KČ). Předposlední prvek z levé strany pak vyjadřuje počet kombinací, kde jsou již dva prvky vyjmuty z množiny - tím pádem vybírám $r - 1$ prvků z této podmnožiny o $n - 1$ prvcích. Například ${3 \choose 3}+ {4 \choose 3}+{5 \choose 3} = {3 \choose 0}+ {4 \choose 1}+{5 \choose 2} = {6 \choose 4}$. Nabízí se ovšem otázka, proč se na začátku sníží $r$ o $2$? Důvodem je, že možnost "všechny prvky jsme vybrali zprava" je obsažena v předchozím sčítanci. Vybereme - li z šesti prvků fixovaně poslední, máme ještě do výběru 3 prvky, tedy dostáváme celkem $5 \choose 3$. kombinací. To je ovšem, jak předpokládáme, rovno ${3 \choose 0}+ {4 \choose 1}.$ Jinými slovy, pokud jsme vybrali šestý a pátý prvek (a celkem můžeme vybírat čtyři prvky) pro naši podmnožinu, tak počet těchto podmnožin je roven tomu, jako kdybychom vybírali podmnožiny o dvou prvcích ze množiny o čtyřech prvcích. Výpočet: Zkouším použít vzorec $n+1 \choose r+1$ $=$ ${n} \choose r$ $+$ $n \choose {r+1}$ = ${n-1} \choose r-1$ $+$ ${n-1} \choose r$ $+$ $n \choose {r+1}$ $=$ ${n-2} \choose r-2$ $+$ ${n-2} \choose r-1$ $+$ ${n-1} \choose r$ $+$ $n \choose {r+1}$ ### 2. Platí, že $k + (r - k) = r$, takže součet spodních stran kombinačních čísel bude v sumě stálý - tzn. na levé straně vybíráme stále stejné množství prvků, nezávisle na $k$. Náš výběr do podmnožiny bude probíhat takto: nejprve vybereme $k$ prvků z množiny $N$ ($|N|= n$), poté $r-k$ prvků z množiny $M$ (předpokládáme, že množiny jsou disjunktní), a podle kombinatorického pravidla součinu dostaneme různé kombinace tím, že počet různých výběrů vynásobíme mezi sebou. Tím nám vznikne množina, která obsahuje $r$ prvků, a vybírali jsme z $n+m$ prvků - tzn. pravá strana. ### 3. $\sum_{k=0}^{n}$$n \choose k$$^2$ $=$ $2n \choose n$ $=$ $\sum_{k=0}^{n}$$n \choose k$$n \choose {n-k}$ $=$ $n+n \choose n$ (viz příklad 2). Pravá strana vyjadřuje počet podmnožin o polovičním množství prvků, levá strana pak, z které "poloviny" prvky vybírám. Pro každé $k$ vyberu z množiny $k$ lichých prvků a $n-k$ sudých prvků - čímž jsem zúžil výběr na polovinu - a $n$ v horní části kombinačního čísla na levé straně pak vyjadřuje, kolika způsoby můžu které prvky vybrat. ### Výpočty: ## komb4 ### 1. ### 2.