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.
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.
1. Generátorfüggvények
2. Lineáris algebrai módszer
Formális hatványsorok
Rekurziók (3. előadás, 5-8. dia)
Lásd CooSpace.
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"