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: ${\displaystyle P_{n}=n!=n\cdot (n-1)\cdot (n-2)\cdot \ldots \cdot 2\cdot 1.}$

Megjegyzés: Definíció szerint ${\displaystyle 0!=1}$.

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: ${\displaystyle 3!=6}$

Az ismétléses permutáció képlete: ${\displaystyle P_{n}^{\left(k_{1};k_{2};\ldots k_{s}\right)}={\frac {n!}{k_{1}!\cdot k_{2}!\cdot \ldots \cdot k_{s}!}}}$, ahol n a sorba rendezni kívánt összes elem száma, k₁ az egyik fajta elemek száma, k₂ 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, k₁ = 2, k₂ = 1. Behelyettesítés után: ${\displaystyle {\frac {3!}{2!\cdot 1!}}=3}$

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:

${\displaystyle C_{n}^{k}={\frac {n!}{k!(n-k)!}}}$ vagy binomiális együtthatókkal kifejezve: ${\displaystyle n \choose k}$ (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: ${\displaystyle {\frac {5!}{3!(5-3)!}}=10}$

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: ${\displaystyle C_{n}^{k}={\frac {(n+k-1)!}{k!([n+k-1]-k)!}}}$, tehát: ${\displaystyle C_{n}^{k}={\frac {(n+k-1)!}{k!(n-1)!}}}$ vagy binomiális együtthatókkal kifejezve: ${\displaystyle C_{n}^{k,i}={{n+k-1} \choose k}}$.

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: ${\displaystyle {\frac {(5+3-1)!}{3!\cdot (5-1)!}}=35}$

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: ${\displaystyle V_{n}^{k}={\frac {n!}{(n-k)!}}=n(n-1)\ldots (n-k+1)}$

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: ${\displaystyle {\frac {5!}{(5-3)!}}=60}$

Az ismétléses variáció képlete: ${\displaystyle V_{n}^{k,i}=n^{k}}$

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: ${\displaystyle 5^{3}=125}$

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.

Példa a Catalan-számokra: Öt bináris fa hét csúccsal, melyből négynek levélnek kell lennie

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.

Egy síkpartíció

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.

Petersen-gráf

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.^[1]

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).

Az {x,y,z} halmaz hatványhalmazának Hasse-diagramja a tartalmazásra rendezve

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 K_n,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.

Önmagát elkerülő séta négyzetrács gráfon

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.

A (5,4,1) partíció Young-diagramja

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.

Thue–Morse végtelen szó

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.

Ikozaéder

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.

Nyaklánc felosztása két vágással

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 kölcsönösen egymást érintő gömbök kapcsolódnak mind a kódelmélethez, mind a diszkrét geometriához

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. ISBN 0-262-07169-X
• Lindner, Charles C.; and Rodger, Christopher A.; eds. (1997); Design Theory, CRC-Press; 1st. edition (1997). ISBN 0-8493-3986-3.
• Riordan, John. An Introduction to Combinatorial Analysis. Dover (2002). ISBN 978-0-486-42536-8 
• Ryser, Herbert John. Combinatorial Mathematics, The Carus Mathematical Monographs (#14). The Mathematical Association of America (1963) 
• 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. ISBN 0-521-80340-3

Fordítás

Ez a szócikk részben vagy egészben a Combinatorics című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

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
• Denkinger Géza – Scharnitzky Viktor – Takács Gábor – Takács Miklós: Matematikai zseblexikon. Lektorálta Bui van Thanh. Budapest: Akadémiai, TYPOT_EX. 1992. ISBN 963-05-6328-2, ISBN 963-7546-12-X  

Jegyzetek

1. Sanders, Daniel P.; 2-Digit MSC Comparison Archiválva 2008. december 31-i dátummal a Wayback Machine-ben.