Összeszámlálási problémák

Tartalom

Előszó 1
1. Bevezetés 1
1.1. Az összeszámlálási feladatok alapproblémája 1
1.2. Sorozatok megadása 3
2. Formális hatványsorok 7
2.1. Polinomok 7
2.2. Alapfogalmak 7
2.3. Alapműveletek 10
2.4. Egyenletek 13
2.5. Racionális kitevőjű hatványok 16
2.6. Határérték. Formális hatványsorok végtelen összege, szorzata 17
2.7. Kompozíció, inverz, helyettesítés 19
2.8. Differenciál- és integrálszámítás 20
2.9. Differenciálegyenletek és alkalmazásaik 21
2.10. Hatványozás 23
2.11. Sorozatok és generátorfüggvényeik 25
3. Részhalmazok 29
3.1. Egy halmaz összes részhalmaza 29
3.2. Multihalmazok és részhalmazaik 30
3.3. Egy halmaz k elemű részhalmazai 31
3.4. k elemű multihalmazok 38
4. Sorbaállítások, permutációk 43
4.1. Egy halmaz összes permutációja 43
4.2. Multihalmazok permutációi 45
4.3. Permutációk ciklusstruktúrája 47
4.4. Permutációk típusa 48
4.5. Permutációk k-ciklussal 49
4.6. Inverziók 52
4.7. Permutációk k inverzióval 53
4.8. Multihalmazok permutációi k inverzióval 55
4.9. Egy permutáció süllyedő halmaza 58
4.10. Alternáló permutációk 59
4.11. Permutációk k süllyedéssel 61
4.12. Permutációk őrnagy indexe 62
5. Halmazok osztályozásai 65
5.1. Egy halmaz összes partíciója 65
5.2. Halmazok k osztályú partíciói 66
5.3. Az első- és a másodfajú Stirling-számok közti összefüggés 69
5.4. Másodfajú Stirling-számok és véges differenciatáblák 72
6. Egész számok partíciói 77
6.1. Egy egész szám összes partíciója 77
6.2. Partíciók feltételekkel 79
6.3. Euler-azonosság 84
6.4. Jacobi-azonosság 87
6.5. Rogers-Ramanujan-azonosság 90
7. Leképezések összeszámlálása 91
7.1. Tizenkét alapeset 91
7.2. Véges halmazokon ható csoportok 93
7.3. A Pólya-Redfield-módszer 98
8. Racionális generátorfüggvények, lineáris rekurziók 103
8.1. Alapfogalmak 103
8.2. Alaptétel 105
8.3. Racionális generátorfüggvények 113
9. Algebrai generátorfüggvények, polinomiális rekurziók 115
9.1. Algebrai formális hatványsorok 115
9.2. Catalan-számok 119
9.3. A Catalan-számok elemi tárgyalása 123
9.4. Polinomiális rekurzióval definiált sorozatok 127
9.5. A Catalan-számok újabb elemi vizsgálata 129
10. Szita módszerek 133
10.1. A tartalmazás és kizárás elve 133
10.2. A tartalmazás és kizárás elvének egy általánosítása 139
10.3. Egy további általánosítás 141
10.4. Részbenrendezett halmazok 142
10.5. Részbenrendezett halmazok Möbius-függvénye 144
10.6. Möbius-függvény és a formális hatványsorok kapcsolata 149
Jelölések 153
Név- és tárgymutató 161
Irodalomjegyzék 165

Témakörök