Kombinatorika

A kombinatorika (szó szerinti jelentése „kapcsolástan”) a matematika azon területe, amely egy véges halmaz elemeinek valamilyen szabály alapján történő csoportosításával, kiválasztásával, sorrendbe rakásával foglalkozik. Az elemi kombinatorika tárgyai a(z) (ismétléses és ismétlés nélküli) permutációk, kombinációk és variációk.

Elemi kombinatorika

Permutáció 

Ismétlés nélküli permutáció alatt néhány különböző dolognak a sorba rendezését értjük. Az "ismétlés nélküli" arra utal, hogy a sorba rendezendő elemek különbözőek, azaz nem ismétlődnek. Egy n elemű halmaz összes permutációinak a száma:

Megjegyzés: Definíció szerint .

Példa: Kiválasztottunk 3 különböző fagylaltgombócot. Ezeket szeretnénk sorba rendezni a tölcsérben. Mennyi a lehetséges sorrendek száma?

Megoldás: n = 3. Behelyettesítés után: 

Az ismétléses permutáció képlete: , ahol n a sorba rendezni kívánt összes elem száma, k1 az egyik fajta elemek száma, k2 a másik fajta elemek száma stb.

Példa:  Kiválasztottunk 3 gombóc fagylaltot. Ezeket szeretnénk sorba rendezni a tölcsérben, de vannak közöttük azonosak. Közülük 2 pisztácia, 1 csokoládé. Mennyi a lehetséges sorrendek száma?

Megoldás: n = 3, k1 = 2, k2 = 1. Behelyettesítés után:

Kombináció 

Az ismétlés nélküli kombinációt alkalmazzuk akkor, ha adott egy véges halmaz, melynek n darabszámú elemeiből k elemszámú halmazokat (kombinatorika nevén osztályokat) akarunk mindenféle módon képezni (és minden elem csak egyszer fordul elő). Ezt úgy hívjuk, hogy n elem k-ad osztályú ismétlés nélküli kombinációja.
Az ismétlés nélküli kombináció képlete:

 vagy binomiális együtthatókkal kifejezve:  (n alatt a k).

Példa: 5 különböző fagylaltgombócból 3 darabot választunk ki a fagylaltos kelyhünkbe. Mennyi a lehetséges kiválasztások száma?

Megoldás: n = 5, k = 3. Behelyettesítés után: 

Az ismétléses kombinációt alkalmazzuk, amikor adott n elemekből k elemszámú multihalmazokat képzünk, ahol adva van legalább 1 multiplikált elem.

Az ismétléses kombináció képlete: , tehát:   vagy binomiális együtthatókkal kifejezve: .

Példa: 5 fagylaltgombócból 3 darabot választunk ki a fagylaltos kelyhünkbe, amelyek között lehet több azonos gombóc is. Mennyi a lehetséges kiválasztások száma?

Megoldás: n = 5, k = 3. Behelyettesítés után:

Variáció 

Ismétlés nélküli valamint ismétléses variáció során egyaránt úgy járunk el, hogy osztályok szerint permutálunk. Vagyis eszerint azon túl, hogy n elem k-adosztályú kombinációit állítjuk fel, permutálnunk is kell azokat. Az előző kombinatorikai operációkhoz hasonlóan változik a variáció aszerint, hogy ismétléses vagy ismétlés nélküli: amennyiben legalább 1 elem multiplikált, akkor ismétléses, ellenkező esetben ismétlés nélküli variációról van szó.

Az ismétlés nélküli variáció képlete: 

Példa: 5 különböző fagylaltgombócból 3 darabot választunk ki. Ezt követően még sorba is rendezzük őket a fagylaltos tölcsérünkben. Mennyi a lehetséges variációk száma?

Megoldás: n = 5, k = 3. Behelyettesítés után: 

Az ismétléses variáció képlete: 

Példa: 5 fagylaltgombócból 3 darabot választunk ki, amelyek között lehet több egyforma is. Ezt követően még sorba is rendezzük őket a fagylaltos tölcsérünkben. Mennyi a lehetséges variációk száma?

Megoldás: n = 5, k = 3. Behelyettesítés után:

Részterületei 

Gráfelmélet, kombinatorikus optimalizáció, a hipergráfok elmélete, az extremális gráfelmélet,az extremális halmazrendszerek elmélete, a részbenrendezett halmazok elmélete, a leszámlálások elmélete, a Ramsey-elmélet, a véletlen módszerek elmélete,
a szimmetrikus struktúrák elmélete, diszkrét geometria, additív kombinatorika, algebrai kombinatorika, kombinatorikus halmazelmélet, a játékelmélet és a matroidelmélet.

A leszámláló kombinatorika a legklasszikusabb részterület, amely bizonyos tulajdonságú matematikai objektumokat számol meg. Habár egy halmaz elemeit leszámolni egy tágabb matematikai probléma része, az alkalmazásokban előforduló problémák közül sok viszonylag egyszerű kombinatorikai feladatot eredményez. Alapvető példák a Fibonacci-számok, a permutációk, variációk és kombinációk.

Az analitikus kombinatorika a kombinatorikai szerkezeteket a komplex analízis és a valószínűségszámítás eszközeivel számolja. Szemben a leszámláló kombinatorikával, ami explicit kombinatorikai képletekkel és generátorfüggvényekkel írja le az eredményt, azt analitikus kombinatorika aszimptotikus formulák alkotását célozza.

A partícióelmélet az egész számok osztályfelbontásaihoz kapcsolódó különböző leszámlálási és aszimptotikus feladatokkal foglalkozik, és közeli kapcsolatban áll a q-sorozatokkal, a speciális függvényekkel és az ortogonális polinomokkal. A számelmélet és az analízis területéről jutott el a kombinatorikába; néha külön területként hivatkoznak rá. Tartalmazza az analízis és az analitikus számelmélet több eszközét, a bijektív megközelítést. Kapcsolatban áll a statisztikai mechanikával.

A gráfok alapvetőek a kombinatorikában, legyen szó leszámlálásokról, szerkezetekről vagy algebrai reprezentációkról. Habár erős szálak fűzik a kombinatorika több területéhez, a gráfelméletet mégis sokszor külön kezelik. A módszerek hasonlóak, de a problémák többnyire különböznek.

A szimmetrikus struktúrák pontok és blokkok halmazai, melyben a blokkok méretének azonosnak kell lennie. Tágabb értelemben más szabályok is megadhatók a metszetekre. A kombinatorika egyik legrégibb területe, Kirkman iskoláslány problémája 1850-ből származik. A probléma megoldása egy Steiner-rendszer. A Steiner-rendszerek a véges egyszerű csoportok klasszifikációjában is szerepelnek. A területnek kapcsolatai vannak a kódoláselmélettel és a geometriai kombinatorikával.

A véges geometria témája a geometriai terek, melyekben csak véges sok pont van. Ezek a geometriák a folytonos geometriákhoz hasonló szerkezeteket tartalmaznak, mint pontok, egyenesek. A szimmetrikus struktúrák példáinak sorozatait szolgáltatja. Összetéveszthető a diszkrét geometriával (kombinatorikus geometria).

A rendezéselmélet részben rendezett halmazokkal foglalkozik, legyenek azok végesek vagy végtelenek. Részben rendezett halmazok a matematika több területén is felbukkannak, mint algebra, geometria, számelmélet, és gráfelmélet. Fontos speciális esetek a hálók és a Boole-algebrák.

A matroidelmélet a geometria egyes területeit vonatkoztatja el. Lineárisan  független vektorhalmazokat tanulmányoz. Nemcsak a szerkezet, hanem a számosság is a matroidelmélet része. Hassler Whitney a rendezéselmélet részeként alapította meg, de kinőtte magát. Továbbra is sok szál kapcsolja a kombinatorika többi részéhez.

Az extremális kombinatorika olyan kérdésekre keresi a választ, hogy egy adott csúcsszámú gráf vagy halmazrendszer legfeljebb mekkora lehet, ha bizonyos feltételeknek kell megfelelnie. Például a 2n csúcsú háromszögmentes gráfok között a Kn,n teljes páros gráf a legnagyobb. Gyakran olyan nehéz megtalálni az extremális választ, így csak aszimptotikus becslést tudunk adni.

A Ramsey-elmélet egy másik fajta kérdést vet fel: Mekkorának kell lennie annak a gráfnak vagy halmazrendszernek, hogy mindenképpen legyen benne egy adott konfiguráció egy adott halmazból? A skatulyaelvet általánosítja.

A valószínűségi kombinatorika véletlen gráfokat, illetve halmazrendszereket vizsgál. Olyan kérdésekre keresi a választ, hogy mekkora annak a valószínűsége, hogy a gráf vagy halmazrendszer megfelel egy adott feltételnek. Egy további lehetséges kérdés például az, hogy átlagosan hány háromszöget tartalmaz egy véletlen gráf? A valószínűségszámítás eszközeit alkalmazzák létezés bizonyítására is úgy, hogy kiszámolják a valószínűséget, és az pozitív. Különösen az extremális kombinatorikában és a gráfelméletben bizonyult hasznosnak ez a módszer. Kapcsolódó elmélet továbbá a véges Markov-láncok, különösen kombinatorikai objektumokon. Így például a keveredési idő is becsülhető a valószínűségszámítás eszközeivel.

Habár az elmélet kezdeményezőjeként Erdős Pált tartják számon, a valószínűségi kombinatorikát sokáig úgy tartották számon, mint olyan eszközök gyűjteményét, melyekkel a kombinatorika különböző területein lehet problémákat megoldani. Az alkalmazási kör bővülésével, például algoritmusok elemzése, valószínűségszámítás, additív számelmélet és valószínűségi számelmélet önálló részterületté nőtte ki magát.

Az algebrai kombinatorika az absztrakt algebra és a kombinatorika interakciója. A legtöbbet alkalmazott módszerek a csoportelmélet és a reprezentációelmélet. Az alkalmazások köre folyamatosan bővül.

A szókombinatorika ráereszti a kombinatorikát a formális nyelvekre. Témái a legkülönbözőbb matematika részterületekről származnak, benne számelmélettel, csoportelmélettel és valószínűségszámítással. Alkalmazást talál a leszámláló kombinatorikában, a fraktálanalízisben, a számítástudományban, az automaták elméletében és a nyelvészetben. Habár sok alkalmazása új, a legismertebb eredménye klasszikus: a formális nyelvtanok Chomsky–Schützenberger-hierarchiája.

A geometriai kombinatorika a konvex és a diszkrét geometria területén alkalmazza a kombinatorikát. Egy részterülete a konvex poliéderekkel foglalkozik, például, hogy hány dimenzióban hány lapja lehet egy politópnak. Tekintetbe veszi a metrikus tulajdonságokat is, köztük a  Cauchy-tételt a konvex poliéderek merevségéről. Speciális poliéderekkel is foglalkozik, mint permutoéderek, asszociaéderek és Birkhoff-politópok. Hasonló névvel előfordul a kombinatorikus geometria is, ami ma inkább diszkrét geometria néven ismert.

A topologikus kombinatorika topológiai személettel közelíti meg a kombinatorikát. Foglalkozik gráfok színezésével, egyenlő osztozkodással, partíciókkal, részben rendezett halmazokkal, döntési fákkal, nyakláncproblémákkal és diszkrét Morse-elmélettel. Nem tévesztendő össze a kombinatorikus topológiával, ami az algebrai topológia régi neve.

Az aritmetikai kombinatorika a számelmélet, kombinatorika, ergodelmélet és harmonikus analízis összjátékából született. Kombinatorikai becsléseket alkalmaz különböző aritmetikai műveletekhez (mint összeadás, kivonás, szorzás és osztás) kapcsolódóan. Része az additív számelmélet, ami csak az összeadást és kivonást veszi figyelembe. Egyik fontos módszere a dinamikus rendszerek ergodelmélete.

Az infinitezimális kombinatorika vagy kombinatorikus halmazelmélet kiterjeszti a kombinatorikát végtelen halmazokra. Itt találkozik a halmazelmélet és a logika, de az extremális kombinatorikát is hasznosítja.

Gian-Carlo Rota folytonos kombinatorikának nevezte a geometrikus valószínűséget a mérték és a számosság analógiája miatt.

A magyar kombinatorikai iskola 
Világszerte elismerik a magyar kombinatorikai iskolát, amelynek néhány képviselője:
 Babai László
 Baranyai Zsolt
 Beck József
 Bollobás Béla
 Erdős Pál
 Frank András
 Frankl Péter
 Füredi Zoltán
 Gallai Tibor
 Gyárfás András
 Hajnal András
 Hujter Mihály
 Katona Gyula
 Kőnig Dénes
 Lovász László
 Pósa Lajos
 Rényi Alfréd
 Simonovits Miklós
 Szalkai István
 Szemerédi Endre
 Szőnyi Tamás
 Tardos Gábor
 T. Sós Vera
 Turán Pál
 Tuza Zsolt

Kapcsolódó területek

A kombinatorikus optimalizáció az optimalizálás lehetőségeit keresi diszkrét, illetve kombinatorikus objektumokon. Eredetileg a kombinatorika és gráfelmélet része volt, de már önálló területté vált az alkalmazott matematikában és a számítástudományban, az operációkutatáshoz, az algoritmusok elméletéhez és a bonyolultságelmélethez kapcsolódóan.

A kódelmélet a szimmetrikus struktúrák elméletéből indult ki a hibajavító kódok korai kombinatorikus konstrukciójával. A fő cél a megbízható és hatékony adatközvetítés. Most az információelmélet részeként kezelik.

Egy másik, jelenleg sokat ígérő terület a dinamikus rendszerek kombinatorikus elemzése. Itt a dinamikus rendszereket kombinatorikai objektumokon definiálják, foglalkoznak például gráf dinamikus rendszerekkel.

A kombinatorikát is kapcsolatba hozták a fizikával, ami nem egyoldalú. A legjobban kapcsolódó terület a statisztikai fizika. Példa lehet az Ising-modell, ami a ferromágnesességet modellezi matematikai eszközökkel; általánosítása, a Potts-modell, ami kristályrácsban vizsgálja a spineket; másrészt a kromatikus polinomok és a Tutte-polinomok.

Források 
 Vilenkin: Kombinatorika. Műszaki könyvkiadó, Bp., 1970
Elekes György: Kombinatorika, egyetemi jegyzet, példatár. ELTE Eötvös kiadó, Bp., 1992
Andrásfai Béla: Gráfelmélet, Polygon Könyvtár, 1997
Hajnal Péter: Elemi kombinatorikai feladatok, Polygon, Szeged, 1997
 Lovász László: Kombinatorikai problémák és feladatok. Typotex. Bp., 1999
 Elekes György, Brunczel András:Véges matematika, egyetemi jegyzet, példatár. ELTE Eötvös kiadó, Budapest, 2002
 Lovász-Pelikán-Vesztergombi: Kombinatorika. Tankönyvkiadó, 1990, Typotex, 2003
Obádovics J. Gyula: Matematika (18. kiadás). Scolar Kiadó, Budapest, 2005
 Björner, Anders; and Stanley, Richard P.; (2010); A Combinatorial Miscellany
 Bóna Miklós; (2011); A Walk Through Combinatorics (3rd Edition). 
 Graham, Ronald L.; Groetschel, Martin; and Lovász, László; eds. (1996); Handbook of Combinatorics, Volumes 1 and 2.  Amsterdam, NL, and Cambridge, MA: Elsevier (North-Holland) and MIT Press. 
 Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); Design Theory, CRC-Press; 1st. edition (1997). .
 
 
 Stanley, Richard P. (1997, 1999); Enumerative Combinatorics, Volumes 1 and 2, Cambridge University Press. 
 van Lint, Jacobus H.; and Wilson, Richard M.; (2001); A Course in Combinatorics, 2nd Edition, Cambridge University Press.

Fordítás

További információk 
 Katona Gyula – Hogyan lett „magyar matematika” a kombinatorika?
 Linfan Mao: Combinatorial Speculation and Combinatorial Conjecture for Mathematics - a matematika főbb ágainak kombinatorikára alapozó felépítésének vázlatos programja. International Journal of Mathematical Combinatorics I. sz. (2007) (A Kínai Akadémia ingyenesen elérhető matematikai folyóirata, PDF). Hiv. beillesztése: 2010. szeptember 19.
 Kombinatorika témájú dal a Kockaéder együttestől

Jegyzetek