Algebrai és geometriai módszerek a kombinatorikában, 2022/2023 tavasz
Csütörtök 14:00-17:00 Vályi terem
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 (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.
TEMATIKA
1. Polinomok, permutációk: Polinomegyenlőségek bizonyítása kiértékeléssel. A ±1 helyettesítés és a deriválás alkalmazásai.
Permutációk kanonikus cikluselőállítása, egyszerű alkalmazások. Az [n alatt k] számok generátorfüggvénye. Egy polinom r-edik együtthatói összegének meghatározása
az r-edik komplex egységgyökök helyettesítésével.
2. Formális hatványsorok: Formális hatványsorok és alapműveletek: összeadás, szorzás, osztás (ismétlés); kompozíció; deriválás.
Formális hatványsorok műveleti tulajdonságai (összefoglaló, nem kell betanulni).
A Fibonacci-számok generátorfüggvénye (ismétlés: itt az 1. lépésben).
Véges sorozatok generátorfüggvénye és az 1/(1-F(x)) hatványsor.
3. További műveletek formális hatványsorokkal, Catalan-számok: n-edik gyök, tört kitevőjű hatványok, Newton-formula.
A Catalan-számok rekurzív definíciója és néhány kombinatorikus interpretációja (pl. Dyck-utakkal a rekurziós prezentációban). A Catalan-számok generátorfüggvénye.
A Catalan-számok zárt alakja (generátorfüggvényekkel). Kiegészítés: A zárt alak elemi bizonyítása.
4. Számok partíciói: Egy szám partíciói, p(n) definíciója. Young-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.
A bolgár pasziánsz játék (ld. első óra).
5. Számok partíciói II.: 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).
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: Prezentáció I., Prezentáció II.
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. Nagy Zsigmond explicit Ramsey-konstrukciója.
Graham—Pollak-tétel (ld. első óra). Egy távolságú ponthalmazok mérete. Polinomok vektortere, Larman—Rogers—Seidel-tétel (két távolságú ponthalmazok méretéről). Téglalapok parkettázása négyzetekkel (Dehn tétele).
7. Séták összeszámlása gráfokban. Mátrixok: 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.
Alkalmazások. Lineáris rekurziók megoldása mátrixhatványozással.
Kiosztott segédanyag: Néhány hasznos állítás mátrixok sajátértékeiről.
8. Pólya—Redfield-módszer: A Burnside-lemma kimondása. A Pólya—Redfield-módszer és alkalmazásai színezett objektumok összeszámlálására.
MINTAVIZSGA: #1, #2. FRISSÍTETT!
FELADATSOROK
1. A polinomok ereje
2. Formális hatványsorok, Catalan-számok
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
AJÁNLOTT IRODALOM
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)
HASZNOS LINKEK
The On-Line Encyclopedia of Integer Sequences
The book "generatingfunctionology"