Kombinatorika

A Wikipédiából, a szabad enciklopédiából

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 | forrásszöveg szerkesztése]

Permutáció[szerkesztés | forrásszöveg szerkesztése]

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\cdot2\cdot1.

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

Példa: Hányféleképpen sorakozhatnak fel egy egyenes sorban egy 26 fős osztály tanulói? Az osztálynak mint 26 elemű halmaznak 26! permutációja van, azaz ennyiféle sorrend lehetséges.

Ismétléses permutáció alatt néhány, egymástól nem feltétlenül különböző dolognak a sorba rendezését értjük. Ha egy n elemű multihalmazban s különböző elem fordul elő, mégpedig az i-edik fajta elem ki-szer (és így n=k1+k2+...+ks), akkor a multihalmaz összes ismétléses permutációinak a száma: P_{n}^{\left(k_1; k_2; \ldots k_s\right)}=\frac{n!}{k_1!\cdot k_2!\cdot \ldots \cdot k_s!}.

Példa: Hányféleképpen lehet sorba rendezni az a, a, a, b, c, c, d, d betűket? Itt n=8 elemünk van, s=4 fajta, a betűből k1=3, b betűből k2=1, c és d betűkből k3=k4=2 darab, így a képlet alapján P_{8}^{\left(3; 1; 2; 2;\right)}=\frac{8!}{3!\cdot 1!\cdot 2!\cdot 2!}= 1680 sorrend lehetséges.

Ciklikus permutáció pl.: n számú vendéget hányféleképpen lehet egy kör alakú asztalnál sorba rendezni?
A megoldás: (n – 1)!

Kombináció[szerkesztés | forrásszöveg szerkesztése]

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

Variáció[szerkesztés | forrásszöveg szerkesztése]

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: Vn;k = (n!)/(n - k)!.

Az ismétléses variáció képlete: Vin;k = nk.

Részterületei[szerkesztés | forrásszöveg szerkesztése]

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 | forrásszöveg szerkesztése]

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

Szakirodalom[szerkesztés | forrásszöveg szerkesztése]

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

Külső hivatkozások[szerkesztés | forrásszöveg szerkesztése]

Ajánlott irodalom[szerkesztés | forrásszöveg szerkesztése]

  • Denkinger Géza-Scharnitzky Viktor-Takács Gábor-Takács Miklós: Matematikai zseblexikon, lektor: Bui van Thanh; Akadémiai Kiadó és TYPOTEX Kiadó, Budapest, 1992, ISBN 963-05-6328-2, ISBN 963-7546-12-X