A félév során házi feladatok kerülnek feladásra, amelyet a következő órán kell benyújtani (hiányzás esetén emailben). 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.
1. Alapok: Formális hatványsorok és alapműveletek: összeadás, szorzás, osztás (ismétlés); végtelen sok hatványsor összege; kompozíció.
Osztályok generátorfüggvénye. Egy osztályból képzett véges sorozatok osztályának generátorfüggvénye (+ egy szabadon választott példa az 1. feladatsorból).
Formális hatványsorok műveleti tulajdonságai (összefoglaló, nem kell betanulni).
A Fibonacci-számok generátorfüggvénye (a bizonyítása nem vizsgaanyag, de elolvasható itt az 1. lépésben).
2. További műveletek formális hatványsorokkal: Deriválás, n-edik gyök, tört kitevőjű hatványok, Newton-formula.
3. Catalan-számok: A Catalan-számok rekurzív definíciója (lásd 6/8 dia itt) és kombinatorikus interpretációi (1. feladatsor / 8-10. feladatok). A Catalan-számok generátorfüggvénye.
A Catalan-számok zárt alakja (a generátorfüggvény együtthatóinak kiszámolásával).
4. Számok partíciói: Egy szám partíciói, p(n) definíciója. Young-diagram, Ferrers-diagram. Partíciók feltételekkel: pontosan / legfeljebb k tagból álló partíciók,
a tagok méretére vonatkozó korlátok; és ezen partíciók száma közötti összefüggések. Partíció konjugáltja. Önkonjugált partíciók és különböző páratlan tagú partíciók kapcsolata.
Végtelen sok formális hatványsor szorzata és a végtelen szorzat műveleti tulajdonságai (a tulajdonságokat nem kell betanulni, számolni kell tudni).
5. Számok partíciói II.: Euler tétele a különböző tagú partíciók és a páratlan tagú partíciók számáról.
A p(n) számok és a speciális partíciókra vonatkozó számok generátorfüggvényei, illetve ezek alkalmazásai.
Euler pentagonális tétele. Rogers—Ramanujan-azonosság (csak kimondani).
6. Lineáris algebrai módszer: Fisher-egyenlőtlenség. Erdős—de Bruijn-tétel (egy véges ponthalmaz által meghatározott egyenesek számáról).
Odd/even town. + Egy tetszőlegesen választott téma a 4. feladatsor 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.
Kiosztott segédanyag: Néhány hasznos állítás mátrixok sajátértékeiről.
8. Gessel—Viennot-lemma: A determináns explicit alakja (ismétlés). Csúcsdiszjunkt útrendszerek élsúlyozott gráfokban. A Gessel—Viennot-lemma (speciális és általános eset). Egy alkalmazás: Binomiális együtthatókból készített determinánsok vizsgálata.
9. Burnside-lemma: A Burnside-lemma kimondása (az absztrakt algebrai környezetben). Szabadon választott alkalmazások.
1. Generátorfüggvények
2. Generátorfüggvények alkalmazása
3. Számok partíciói
4. Lineáris algebrai módszerek
5. Séták összeszámlálása
6. A Gessel—Viennot-lemma
7. Burnside-lemma
Hajnal Péter: Összeszámlálási problémák (Polygon Jegyzettár)
Babai László, Frankl Péter: Linear algebra methods in combinatorics (The University of Chicago)
Federico Ardila: Algebraic and geometric methods in enumerative combinatorics (a Handbook of Enumerative Combinatorics 1. fejezete)
Richard P. Stanley: Enumerative Combinatorics, Vol. 1-2 (Cambridge University Press)
Philippe Flajolet & Robert Sedgewick: Analytic Combinatorics (Cambridge University Press)
The On-Line Encyclopedia of Integer Sequences
The book "generatingfunctionology"
| ⇦ | Főoldal |