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

Megjegyzés: Definíció szerint $0!=1$.

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

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: $C_{n}^{k,i}={{n+k-1} \choose k}$ - binomiális együtthatóval kifejezve.

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-, ellenben ismétlés nélküli variációról van szó. Az ismétlés nélküli variáció képlete: $V_{n}^{k}={\frac {n!}{(n-k)!}}=n(n-1)\ldots (n-k+1)$

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

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

Források

• Andrásfai Béla: Gráfelmélet, Polygon Könyvtár, 1997.
• Elekes György: Kombinatorika, egyetemi jegyzet, példatár. ELTE Eötvös kiadó, Bp.
• Elekes György, Brunczel András:Véges matematika, egyetemi jegyzet, példatár. ELTE Eötvös kiadó, Budapest, 2002.
• Hajnal Péter: Elemi kombinatorikai feladatok, Polygon, Szeged, 1997.
• Obádovics J. Gyula: Matematika (18. kiadás). Scolar Kiadó, Budapest, 2005.
• Vilenkin: Kombinatorika. Műszaki könyvkiadó, Bp. 1970.
• Lovász László: Kombinatorikai problémák és feladatok. Typotex. Bp., 1999.
• Lovász-Pelikán-Vesztergombi: Kombinatorika. Tankönyvkiadó, 1990, Typotex, 2003.

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