Kombinatorika

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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[szerkesztés]

Permutáció[szerkesztés]

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 .

Kombináció[szerkesztés]

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 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: - binomiális együtthatóval kifejezve.

Variáció[szerkesztés]

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:

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

Részterületei[szerkesztés]

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[szerkesztés]

Világszerte elismerik a magyar kombinatorikai iskolát, amelynek néhány képviselője:

Források[szerkesztés]

  • 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[szerkesztés]