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
Prednášky LS 2024/25 - diskrétna matematika
-
Martin Sleziak
- Posts: 5774
- Joined: Mon Jan 02, 2012 5:25 pm
-
Martin Sleziak
- Posts: 5774
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2024/25 - diskrétna matematika
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.
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
- Posts: 5774
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2024/25 - diskrétna matematika
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).
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
- Posts: 5774
- Joined: Mon Jan 02, 2012 5:25 pm
Re: Prednášky LS 2024/25 - diskrétna matematika
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.
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.