Kombinatorika a Grafy 1 (NDMI011) -- přednáška
Přednáška se koná každé pondělí v 15:40 v N1.
Přednášku vede Pepa Tkadlec. E-mail: pepa (AT) iuuk.mff.cuni.cz
Cvičení vedou: Eliška Červenková, Barbora Dohnalová, Tomáš Hons, David Mikšaník, Irena Penev a Pepa Tkadlec
Zápočet:
Zápočet bude udělen za zisk 100 bodů udělovaných průběžně za písemné testy, řešení domácích úloh, aktivitu na hodinách, apod. Maximální možný počet bodů, které lze získat, je zhruba 150. Konkrétní pravidla pro zisk zápočtu stanoví cvičící příslušného kroužku.
Stránky cvičení:
Zkouška:
Následující informace o zkoušce jsou předběžné a můžou se měnit do 31.11.2025:
Zkouška má písemnou část (90 minut, dopoledne) a ústní část (odpoledne). Ústní část je obvykle poměrně krátká (<15 minut). Písemná část obsahuje několik úloh následujících typů: zformulujte definici; uveďte výsledek z přednášky; dokažte výsledek z přednášky; vyřešte úlohu související s probranou látkou. Loňské písemky jsou na loňské stránce. Celkem je z písemky možné získat až 30 bodů. Předběžné známky jsou pak
[26-30]: 1
[21-25]: 2
[16-20]: 3
[11-15]: 4 (ústní část je možná)
[ 0 -10]: 4 (ústní část není možná)
Vy i zkoušející můžete iniciovat ústní část. Během té se známka může změnit oběma směry.
Během zkoušky smíte používat jen psací potřeby a lahev s vodou (zejména: žádná elektronika, žádné poznámky).
Vezměte si s sebou doklad totožnosti.
Pro složení zkoušky je potřeba mít v SISu zápočet (neplatí pro předtermín).
Předběžné termíny zkoušek (přihlašování v SISu od 1.12.):
(předtermín) 7.1. písemka od 8.30 v N2, ústní od 12.30 v N2 (v tomto termínu výjimečně není potřeba mít v SISu zápočet)
12.1. písemka od 9.00 v S9, ústní od 12.30 v S8
13.1. písemka od 9.00 v S9, ústní od 12.30 v S8
14.1. písemka od 9.00 v S9, ústní od 12.30 v S8
20.1. písemka od 9.00 v S5, ústní od 12.30 v S8
21.1. písemka od 9.00 v S9, ústní od 12.30 v S8
budou minimálně 2 termíny v létě, data určím nejpozději 30.4.
Pozor, odhlásit se ze zkoušky je možné nejpozději 3 dny před termínem.
Zdroje:
[MN] J. Matoušek, J. Nešetřil: Invitation to discrete mathematics, 2nd edition, 2008.
[P] I. Penev: Combinatorics and Graph Theory 1 & 2 (pdf), kapitoly 1 -- 8.
záznamy přednášek Vítka Jelínka z roku 24/25 (pozor, probraná látka se trochu liší)
stránka Martina Balka z roku 22/23 (pozor, probraná látka se trochu liší)
Probraná látka:
29.9. Úvod, odhady faktoriálů a kombinačních čísel: [MN: chapter 3, P: chapter 1] [záznam]
- introduction, basic info, overview
- easy factorial bounds nn/2 ≤ n! ≤ nn and stronger bounds e(n/e)n ≤ n! ≤ en(n/e)n (by integral) [MN: 3.5.5]
- Stirling formula n! ~ (2\pi n)1/2(n/e)^n (just stated) [MN: 3.5]
- binomial bounds (n/k)k ≤ C(n,k) ≤ (en/k)k [MN: 3.6.1]
- bounds on the central binomial coefficient 22n/(2n1/2) ≤ C(2n,n) ≤ 22n/(2n)1/2 [MN: 3.6.2]
- Example: random walk on a line [P: 1.4]
- bonus [fun stuff]: 52! is a very large number
6.10. Vytvořující funkce [P: chapter 2, MN: chapter 12] [záznam]
- baby example (7 balls from 5 red, 4 green, 3 blue) [MN 12.1]
- definition, example (1,1,1,..) -> 1/(1-x), comment on assumptions (x from a tiny neighborhood of 0)
- dictionary for translating between sequences and their generating functions [MN 12.2 / P 2.4]
- solving linear recurrences with constant coefficients, on the example of Fibonacci numbers [MN 12.3 / P 2.3]
- bonus: recall the Taylor series (explained by Taylor Swift and Elon Musk) and a book generatingfunctionology by H. S. Wilf
13.10. [plán] Víc vytvořujících funkcí [P: chapter 2, MN: chapter 12]
- generalized binomial coefficients, generalized binomial theorem (proof sketched) [MN 12.2 / P 2.2]
- corollary (1-x)^{-n} = \sum_{i=0}^\infty \binom{n+i-1}{n-1} x^i [MN 12.2]
- rooted binary trees, #rooted binary trees is the n-th Catalan number C_n=\frac1{n+1}\binom{2n}{n} [MN 12.4 / P 2.5]
- #partitions of n into odd parts = #partitions of n into distinct parts [MN 12.7 / here]
- bonus: the riddle (un, dos, tres, quatre, cinc, sis, ..) and the Veritasium video about the generalized binomial theorem