Cvičenia LS 2023/24 - diskrétna matematika

[Martin Sleziak]

V tomto topicu by som chcel vždy napísať nejaké stručné zhrnutie, čo sme stihli na cviku.
Ak budete mať otázky k niečomu, čo bolo na cviku, otvorte na to nový topic. (Tento topic by som chcel zachovať pre tento jediný účel.)

[Martin Sleziak]

1. týždeň (22.2):
Dokázali sme hokejkovú identitu - matematickou indukciou aj kombinatoricky.
Pozreli sme sa na niekoľko príkladov z 01principy.pdf takého typu, kde bolo treba spočítať počty nejakých objektov: úlohy 6, 7, 9 a 13.
Potom sme ešte ukázali kombinatoricky nejaký vzťah pre $\sum\limits_{k=1}^n k^2$ (úloha 2). A aspoň som spomenul, že by sme to vedeli dostať aj z hokejkovej identity (úlohy 3 a 4).

[Martin Sleziak]

3. týždeň (4.3):
Počítali sme úlohy z 02binom1.pdf.

• Ešte sme sa vrátili k dôkazu binomickej vety a rozmysleli sme si, ako to je pre matice.
• Rozmysleli sme si, ako sa dá pomocou binomických koeficientov vyjadriť počet najkratších ciest po mriežke.
• Počet $k$-prvkových podmnožín v $\{1,2,\dots,n\}$ takých, že sa tam nevyskytnú susedné čísla. viewtopic.php?t=2053
• S pomocou komplexných čísel sme vyjadrili $\sum\limits_{k\ge0}\binom n{4k}$.

[Martin Sleziak]

5. týždeň (18.3):
S výnimkou posledného príkladu všetko bolo z 03binom2.pdf.
Ešte raz sme sa vrátili k identite $\sum\limits_{k=0}^n k\binom nk = n2^{n-1}$: viewtopic.php?t=1003
viewtopic.php?t=987
Pozreli sme sa na sumy
\begin{align*}
\sum_{k=0}^n k^2\binom nk&=n(n+1)2^{n-2}\\
\sum_{k=0}^n k(k-1)\binom nk&=n(n-1)2^{n-2}
\end{align*}
Dokázali sme, že $\sum_{k=0}^n (-1)^k k\binom nk =0$, resp. to, že takáto suma cez párne aj cez nepárne indexy nám dá tú istú hodnotu $n2^{n-2}$.
Pozreli sme sa na $\sum_{k=0}^n \binom nk^2=\binom{2n}n$ a pripomenuli Vandermondovu identitu.
Rozmysleli sme si, že platí $\sum\limits_{k=0}^n k\binom nk^2=n\binom{2n-1}{n-1}.$

[Martin Sleziak]

6. týždeň (25.3):
Na začiatku sme sa vrátili k dvojitej sume z domácej úlohy.
Ostatné veci, ktoré sme počítali, sú z 04pie.pdf.
Konkrétne sme sa pozreli na úlohy 11 a 10, týkajúce sa počtu celočíselných riešení lineárnej rovnice s viac premennými, kde nám teraz pribudli aj horné ohraničenia. )
Úloha 13 - počet čísel bez štvorcov.
Úloha 12 - počet čísel, ktoré sú deliteľné $2$ alebo $7$. Túto úlohu sme potom vypočítali aj pomocou Eulerovej funkcie - dalo sa tam nejako použiť to, že $\varphi(14)=6$).
Úloha 6: Ak $n>2$, tak $\varphi(n)$ je párne. Toto sme zatiaľ ukázali pomocou prvočíselného rozkladu - nabudúce by sme sa k tejto úlohe chceli vrátiť a rozmyslieť si, či nevieme to isté dokázať tak, že vhodne popárujeme prvky množiny, ktorej počet vyjadruje $\varphi(n)$.
Pridám aj nejakú linku: Why is Euler's Totient function always even?

[Martin Sleziak]

8. týždeň (8.4):
Do súboru 04pie.pdf som pridal aj úlohy, ktoré sme počítali dnes - a ktoré tam minulý týždeň ešte neboli.
Eulerova funkcia
Vrátili sme sa k Eulerovej funkcii - ešte raz sme sa pozreli na to, že $\varphi(n)$ je párne a zdôvodnili sme $\sum\limits_{d\mid n}\varphi(d)=n$. (Úlohy 5 a 6.)
Princíp zapojenia a vypojenia.
Počet permutácií daného slova, kde nesmú nasledovať tesne po sebe rovnaké písmená (úlohy 18 a 19).
Počet usadení, ak nesmú byť pokope všetci z rovnakej národnosti (úloha 20).
Počet riešení $x_1+x_2+x_3=48$ takých, že $0\le x_1<x_2<x_3$ resp. takých, že hodnoty $x_{1,2,3}$ sú rôzne(úloha 17).
Koľkými spôsobmi sa dá uložiť $n$ veží na šachovnicu $n\times n$ tak, aby každé políčko bolo obsadené alebo ohrozené niektorou z nich? (Úloha 19)
Permutácie bez pevného bodu.
Zdôvodnili sme rovnosť $D_n=nD_{n-1}+(-1)^n$. Našli sme počet permutácií, ktoré majú práve $k$ pevných bodov. Na základe toho sme vedeli odvodiť rovnosť $n!=\sum\limits_{k=0}^n \binom nk D_k$.

[Martin Sleziak]

10. týždeň
Príklady z 05planar.pdf.

Pondelok (22.4):
Dve úlohy takého typu, kde sme pre dané grafy mali rozhodnúť, či sú alebo nie sú planárne; úlohy 2.7 a 2.9.
Povedali sme si niečo o komponentoch súvislosti.
Úloha 2.4 - Eulerova formula v tvare $v-h+s=1+c$, kde $c$ je počet komponentov súvislosti.

Štvrtok (25.4):
Pozreli sme sa na popis Petersenovho graf grafu pomocou dvojprvkových množín - úloha 1.2.
Ukázali sme, že graf je súvislý p.v.k. pre každý rozklad množiny vrcholov $V=V_1\cup V_2$ na dve neprázdne disjunktné množiny existuje hrana spájajúca nejaký vrchol z $V_1$ s nejakým vrcholom z $V_2$; úloha 1.10.
V každom grafe existujú dva vrcholy rovnakého stupňa (úloha 1.3).
Ukázali sme, že ak z $K_5$ resp. z $K_{3,3}$ vynecháme jednu hranu, tak dostaneme rovinný graf.
Úloha 2.6.: Nech $G$ je graf na $n$ vrcholoch a $n\ge11$. Dokážte, že potom graf $G$ alebo jeho komplement nie je planárny. Pridám k tejto úlohe aj takúto linku: https://math.stackexchange.com/q/128657

[Martin Sleziak]

12. týždeň
Príklady z 06farb.pdf.

Štvrtok (9.5.):
Rozmysleli sme si dôkaz charakterizácie grafov, ktoré majú uzavretý eulerovský ťah.
Pozreli sme sa na úlohu 10 - ak graf má aspoň $\binom{n-1}2+1$ hrán, tak má hamiltonovskú kružnicu.
Pridám k tejto úlohe aj nejaké linky: https://math.stackexchange.com/q/30833 a https://math.stackexchange.com/q/91975