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

KÖVETELMÉNYEK

A félév során házi feladatok kerülnek feladásra, amelyet a következő órán kell benyújtani (vagy aznap éjfélig emailben elküldeni a megoldást). A vizsgaidőszakban meghirdetett vizsgaidőpontokban írásbeli vizsgák lesznek. A házi feladatok és a vizsga pontszámai 50-50% súllyal számítanak bele a végső érdemjegybe.
  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.
Lásd CooSpace.

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.
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.
3. Multihalmazok: Multihalmazok és az ((nk)) számok definíciója (ismétlés a Kombinatorika kurzusról). Az ((nk)) számok pontos értéke (ismétlés a Kombinatorika kurzusról). Az ((nk)) számok generátorfüggvénye.
4. 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.
5. 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). 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).
6. Lineáris algebrai módszer: Fisher-egyenlőtlenség. Odd/even town. Nagy Zsigmond explicit Ramsey-konstrukciója. Egy tetszőlegesen választott téma a 2. feladatsor 6-7. feladatai közül.
7. Séták összeszámlálása gráfokban: Szomszédsági mátrix. A szomszédsági mátrix kapcsolata a k hosszú séták számával. Zárt séták száma a sajátértékek segítségével. Az eddigiek egy szabadon választott kombinatorikai alkalmazása. Lineáris algebrai segédanyag: Néhány hasznos állítás mátrixok sajátértékeiről.

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)

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