Algebrai és geometriai módszerek a kombinatorikában (levelező), 2021/2022 tavasz

KÖVETELMÉNYEK

A félév során házi feladatok kerülnek feladásra, amelyeket a következő óráig kell benyújtani személyesen vagy CooSpace-en. A gyakorlat aláírásához (és így az előadásvizsgára bocsáthatósághoz) a házi feladatokkal megszerezhető pontszám legalább 40%-át el kell érni. A vizsgaidőszakban meghirdetett vizsgaidőpontokban írásbeli vizsgák lesznek, ahol legalább 40%-ot el kell érni a teljesítéshez. A házi feladatok és a vizsga pontszámai 50-50% súllyal számítanak bele az előadás érdemjegyébe.
  0% – 50%:   elégtelen
51% – 62%:   elégséges
63% – 75%:   közepes
76% – 87%:   jó
88% – 100%: jeles

A félév folyamán pluszpontokat is lehet gyűjteni az előadás alatt tett érdemi hozzászólással/hibajelzéssel.

TEMATIKA

1. Polinomok: Polinomok szorzása és deriválása, hasznos helyettesítések. Komplex egységgyökök helyettesítése: a polinom k-adik együtthatóinak az összege. A kockacinkeléses feladat megoldása. Páros és páratlan elemösszegű k elemű részhalmazok számának összehasonlítása.
2. Formális hatványsorok: Formális hatványsorok definíciója, generátorfüggvények. Alapműveletek (összeadás és szorzás), hatványozás, osztás. Formális hatványsor foka. Formális hatványsorok műveleti tulajdonságai (nem kell betanulni; számolni kell tudni formális hatványsorokkal), többtényezés szorzat. Az 1/(1-x) formális hatványsor. Az 1/(1-x)2 formális hatványsor.
Az ((nk)) számok generátorfüggvénye.
3. Lineáris rekurziók: Formális hatványsorok kompozíciója. Lineáris rekurziók megoldása generátorfüggvény-módszerrel. (Egy kidolgozott példa: A Fibonacci-számok zárt alakja.) Elméleti kiegészítés lineáris rekurziók megoldásához: Polinom/polinom alakú hatványsorok együtthatóinak kiszámolása.
4. Catalan-számok: Formális hatványsorok n-edik gyöke. Tört kitevőjű hatványok. Newton-formula. A Catalan-számok rekurzív definíciója (ld. ezen prezentáció 6. diáját). A Dyck-utak összeszámlálása (ld. ezen prezentáció 5. diáját); konvex sokszög háromszögeléseinek száma. A Catalan-számok generátorfüggvénye. A Catalan-számok zárt alakja (segédlet: A generátorfüggvény együtthatóinak kiszámolása).
5. Formális hatványsor négyzetgyökének további alkalmazásai: Az 1. feladatsor 15-17. feladatainak megoldásai.
6. Lineáris algebrai módszer: Fisher-egyenlőtlenség (a nemuniform változatot csak kimondani). Odd/even town. A 2. feladatsor 6. feladatának megoldása. Graham—Pollak-tétel.

MINTAVIZSGA: #1, #2.

FELADATSOROK + HÁZI FELADATOK

1. Generátorfüggvények
2. Lineáris algebrai módszer

KIVETÍTETT PREZENTÁCIÓK

Formális hatványsorok
Rekurziók (3. előadás, 5-8. dia)

TÁBLAKÉPEK

Lásd CooSpace.

AJÁNLOTT IRODALOM

Philippe Flajolet & Robert Sedgewick: Analytic Combinatorics (Cambridge University Press)
Federico Ardila: Algebraic and geometric methods in enumerative combinatorics (Handbook of Enumerative Combinatorics 1. fejezete)
Babai László, Frankl Péter: Linear algebra methods in combinatorics (The University of Chicago)
Richard P. Stanley: Enumerative Combinatorics, Vol. 1-2 (Cambridge University Press)

HASZNOS LINKEK

The On-Line Encyclopedia of Integer Sequences
The book "generatingfunctionology"

Főoldal