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.
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.
1. Generátorfüggvények
2. Lineáris algebrai módszer
Formális hatványsorok
Rekurziók (3. előadás, 5-8. dia)
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)
The On-Line Encyclopedia of Integer Sequences
The book "generatingfunctionology"