Prednášky LS 2024/25 - diskrétna matematika

[Martin Sleziak]

V tomto vlákne budem pravidelne dopĺňať, čo sa stihlo prebrať na jednotlivých prednáškach. (Napríklad to môže byť užitočné pre ľudí, ktorí z nejakého dôvodu nemohli prísť na prednášku - aby si mohli pozrieť, čo si treba doštudovať.)

Ak budete mať otázky k niečomu, čo odznelo na prednáškach, otvorte na to nový topic. (Tento topic by som chcel zachovať pre tento jediný účel.)

Tu sa dá pozrieť, čo som stihol prebrať minule: viewtopic.php?t=2043

[Martin Sleziak]

1. prednáška (19.2):
Sčítací a násobiaci princíp.
Spomenuli sme niektoré základné kombinatorické princípy; konkrétne sčítací a násobiaci princíp.
Ako príklad použitia násobiaceho princípu sme odvodili počet permutácií, počet variácií a počet $k$-prvkových podmnožín $n$-prvkovej množiny.
Pri vyjadrení pre $\binom nk$ sme zaviedli označenie pre rastúcu a klesajúcu mocninu.
Ako príklad použitia sčítacieho princípu som ukázal Pascalovu identitu.
Pozreli sme sa aj na počet zobrazení medzi dvoma konečnými množinami. Pri počte zobrazení z $A$ do $B$ sa môže človek zamyslieť aj nad tým, čomu sa rovná $0^0$, $0^n$ a $n^0$: viewtopic.php?t=343
Ako príklad princípu bijekcie sme ukázali, že $n$-prvková množina má práve $2^n$ podmnožín. Použili sme pri tom charekteristickú funkciu.
Ako príklad počítania dvoma spôsobmi sme ukázali, ako vyzerá súčet v riadku Pascalovho trojuholníka.
Počítanie dvoma spôsobmi chceme použiť aj na zdôvodnenie hokejkovej identity; tu sme sa však zatiaľ k jej dôkazu nedostali; iba sme sa chvíľu hrali s Pascalovým trojuholníkom a po chvíli experimentovania sa nám podarilo uhádnuť, ako vyzerá súčet binomických koeficientov na diagonále.

[Martin Sleziak]

2. prednáška (24.2):
Hokejkovú identitu, ktorú sme spomenuli na konci minulej prednášky, sme dokázali na cvičeniach.
Permutácie s opakovaním. Počet permutácie pre $n_1,n_2,\dots,n_k$ rôznych typov prvkov a $n=n_1+n_2+\dots+n_k$ je
$$\binom n{n_1,n_2,\dots,n_k}=\frac{n!}{n_1!n_2!\cdots n_k!}.$$
Tomuto výrazu sa zvykne hovoriť aj multinomický koeficient..
Kombinácie s opakovaním a celočíselné riešenia. Počet kombinácii s opakovaním $k$-tej triedy z $n$ prvkov je rovný $$\binom{n+k-1}{k-1}=\binom{n+k-1}n.$$
Zdôvodnili sme ho pomocou stars and bars. (Povedali sme si, že pomerne priamočiaro by sa dal dokázať aj indukciou - ale každopádne túto metódu je užitočné poznať.)
Ten istý vzťah nám dá počet celočíselných riešení rovnice $x_1+\dots+x_k=n$ takých, že $x_i\ge0$.
Binomické koeficienty. Pripomenuli sme definíciu binomického koeficientu a niektoré základné vlastnosti (symetria, Pascalova identita.)
Binomická veta. Sfomulovali sme binomickú vetu v dvoch podobách:
\begin{gather*}
(1+t)^n=\sum_{k=0}^n \binom nk t^k\\
(x+y)^n=\sum_{k=0}^n \binom nk x^ky^{n-k}
\end{gather*}
Povedali sme si, ako sa dá dokázať - aj keď pri dôkaze indukciou som nerobil všetky detaily. (Spomenul som otázku, či platí binomická veta pre polia, okruhy, či sa dá aplikovať na matice - môžeme sa k tejto otázke niekedy vrátiť.)
Keď sme vhodne dosadili do binomickej vety, tak sme dostali, že pre $n\ge1$ platí
$$\sum_{k=0}^n (-1)^k \binom nk=0,$$
t.j. vlastne súčet binomických koeficientov v riadku Pascalovho trojuholníka so striedavými znamienkami. Ako dôsledok dostávame, že máme rovnako veľa podmnožín s párnym a s nepárnym počtom prvkov.
Potom sme ešte binomickú vetu zderivovali a zintegrovali, dostali sme takto identity: $\sum\limits_{k=0}^n k\binom nk = n2^{n-1}$ a $\sum\limits_{k=0}^n \frac1{k+1}\binom nk = \frac{2^{n+1}-1}{n+1}$.
Sľúbil som, že aspoň k niektorým identitám, ktoré sme dostali ako dôsledky binomickej vety, sa ešte vrátime aj na cvičeniach - pozrieme sa na možnosť iného dôkazu (indukciou, kombinatoricky, pomocou iných identít).

[Martin Sleziak]

3. prednáška (3.3.):
Binomické koeficienty.
Ukázali sme, že platí $k\binom nk = n \binom{n-1}{k-1}$: viewtopic.php?t=988
Použili sme ju na iné zdôvodnenie rovnosti $\sum\limits_{k=0}^n k\binom nk = n2^{n-1}$: viewtopic.php?t=1003
Dokázali sme Vandemondovu identitu - kombinatoricky cez počítanie komisií aj použitím binomickej vety na základe $(1+t)^{m+n}=(1+t)^m(1+t)^n$.
Princíp zapojenia a vypojenia.
Sformulovali sme princíp zapojenia a vypojenia a ukázali sme si nejaký dôkaz. Spomenul som, že by sa takýto dôkaz dal zapísať aj pomocou charakteristických funkcií - dá sa takýto dôkaz pozrieť v texte na stránke. (A dôkaz by sa dal spraviť aj indukciou vzhľadom na počet množín.)
Permutácie bez pevného bodu.
Zadefinovali sme permutácie bez pevného bodu a vypisovaním všetkých možností sme spočítali $D_n$ pre $n=1,2,3,4$.
Odvodili sme vyjadrenie pre $D_n$, t.j. počet permutácií bez pevného bodu pomocou PIE.

[Martin Sleziak]

4. prednáška (10.3.):
Permutácie bez pevného bodu.
Ešte som sa vrátil k vyjadreniu pre $D_n$ z minula. Pozreli sme sa na to, ako súvisí s Taylorovým radom pre $e^x$ a na to, že $\frac{D_n}{n!}$ je približne $\frac1e$.
Počet surjektívnych zobrazení.
Vyjadrili sme pomocou PIE $\operatorname{Sur}(n,k)$, počet surjekcií z $n$-prvkovej množiny do $k$-prvkovej množiny.
Trochu sme potom odbočili k tomu, že počet $\operatorname{Sur}(n,k)$ pomerne prirodzeným spôsobom súvisí aj s počtom rozkladov $n$-prvkovej množiny na $k$ neprázdnych podmnožín, čo je vlastne definícia Stirlingovho čísla druhého druhu.
(Vo verzii textu, ktorá je na momentálne na stránke, je o Stirlingových číslach druhého druhu niečo napísané - ale veľmi málo, v podstate iba rekurencia, ktorú sme spomenuli na prednáške a súvis s počtom surjekcií. Každopádne keď sme dnes hovorili o niečom, čo s touto témou úzko súvisí, zdalo sa mi rozumné ich aspoň spomenúť.)
V súvislosti so vzťahom medzi surjekciami a rozkladmi resp. reláciami ekvivalencie pridám aj túto linku: viewtopic.php?t=1730
Eulerova funkcia
Ukázali sme si pomocou PIE vyjadrenie Eulerovej funkcie na základe kanonického rozkladu.
Z neho vieme odvodiť aj $\varphi(mn)=\varphi(m)\varphi(n)\frac{d}{\varphi(d)}$ pre $d=\gcd(m,n)$. (Okrem iného dostaneme to, že $\varphi(n)$ je multiplikatívna funkcia.)
Bez dôkazu sme spomenuli Eulerovu vetu a Malú Fermatovu vetu.
Pripomeniem nejaký príklad z minulého semestra o mocninách prvku v komutatívnej grupe, ktorý súvisí s Malou Fermatovou vetou (a vlastne aj s Eulerovou vetou): viewtopic.php?t=2005

[Martin Sleziak]

5. prednáška (17.3.):
Multinomická veta. Sformulovali a zdôvodnili sme multinomickú vetu.
Binomická veta s reálnym exponentom.
Povedali sme si, ako by fungovala binomická veta pre reálny exponent. (Tam sme dostali vyjadrenie pre $(1+x)^t$ v tvare nekonečného radu. Je to vlastne skôr téma týkajúca sa matematickej analýzy než diskrétnej matematiky - keďže však súvisí s tým čo sme preberali teraz, zdalo sa mi vhodné ju aspoň spomenúť.)
Spomenul som, že takáto veta platí a že ju dostanete ako špeciálny prípad Taylorovho radu. (Túto tému by ste mali na analýze prebrať niekedy v tomto semestri.)
Pozreli sme sa na to, čo dostaneme, keď exponent je $-1$; vyjadrili sme $\binom{-1}k$ a dopracovali sme sa ku geometrickému radu.
A tiež sme sa ešte pozreli na špeciálny prípad $t=-n$ pre prirodzené číslo $n$; videli sme, že to nejako súvisí s počtom nezáporných celočíselných riešení.
Wikipédia: Binomial series.
Riešenia rovnice $x_1+\dots+x_k=n$ s obmedzeniami. Už sme sa zaoberali počtom celočíselných riešení rovnice $x_1+\dots+x_k=n$, pričom sme mali dolné ohraničenia na jednotlivé premenné.
Rozmysleli sme si, že PIE sa dá použiť na vyjadrenie počtu riešení, ak navyše máme horné ohraničenia. A ukázali sme si trik so substitúciou, ktorý nám môže niekedy riešenie zjednodušiť.
Nejaké takéto príklady sú vyriešené aj v texte na stránke. A jeden taký príklad je aj tu na fóre: viewtopic.php?t=1015
Grafy.
Definícia grafu, niektoré základné pojmy (vrcholy, hrany, stupeň).
Súčet stupňov všetkých vrcholov sa rovná $2|E|$. Wikipédia: Handshaking lemma

[Martin Sleziak]

5. prednáška (24.3.):
Stromy.
Definícia cesty a kružnice. Definovali sme strom ako súvislý a acyklický graf.
Ukázali sme, že každý strom s aspoň dvoma vrcholmi má aj vrcholy stupňa 1. Ukázali sme, že pre vrchol stupňa 1 platí: $G$ je strom $\Leftrightarrow$ $G-v$ je strom.
Strom na $n$ vrcholoch má $n-1$ hrán. Ak súvislý graf na $n$ vrcholoch má $n-1$ hrán, tak je to strom.
Spomenuli sme si ďalšie ekvivalentné charakterizácie stromov: minimálny súvislý graf, maximálny acyklický graf, existencia práve jednej cesty pre ľubovoľné dva vrcholy.
Pre existenciu práve jednej cesty sme ekvivalenciu aj dokázali; zostáva nám ešte dokázať, že aj minimálny súvislý graf a maximálny acyklický graf sú ekvivalentné charakterizácie.

[Martin Sleziak]

6. prednáška (31.3):
Stromy.
Dokončili sme ekvivalentné charakterizácie stromov: minimálny súvislý graf, maximálny acyklický graf.
Planárne grafy.
Zadefinovali sme pojem planárneho (rovinného) grafu. Povedali sme si niečo o tom, čo myslíme pod rovinným nakreslením a ako počítame steny. Spomenuli sme stereografickú projekciu a to, že planárne grafy sú vlastne tie isté grafy, ktoré vieme nakresliť na guľu. (A pomocou stereografickej projekcie sme si vedeli rozmyslieť, že ak máme nejaké rovinné nakreslenie grafu, tak ľubovoľnú jeho stenu vieme zmeniť na vonkajšiu stenu v inom nakreslení.)
Viacero vecí sme spomínali skôr na intuitívnej úrovni než ako niečo, čo by bol úplne rigorózny dôkaz - špecificky spomeniem, že sme vlastne využívali Jordanovu vetu o krivkách; potrebovali sme vedieť, že uzavretá krivka rozdelí rovinu na dve oblasti.
Dokázali sme Eulerovu formulu: Pre súvislý planárny graf platí $v-h+s=2$.
Dokazoval som to trochu inak ako je v texte - dokazoval som verziu pre nesúvislé grafy v tvare $v-h+s=1+c$.
Ako dôsledok Eulerovej formuly sme dostali nerovnosť $h\le 3v-6$.
Graf $K_5$ nie je planárny.
Každý rovinný graf má vrchol stupňa nanajvýš $5$.
Ak graf nemá kružnicu dĺžky $3$, tak platí $h\le 2v-4$. Graf $K_{3,3}$ nie je planárny.