Kombinatorika
A Wikipédiából, a szabad enciklopédiából.
A kombinatorika jelentése kapcsolástan, mely 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.
Tartalomjegyzék |
[szerkesztés] Elemi kombinatorika
[szerkesztés] Permutáció
Az ismétlés nélküli permutáció fogalma szerint adott egy véges n elemű halmaz, melynek elemeit minden lehetséges módon rendezni akarjuk. Tehát permutálás alatt az n elem különböző rendezéseinek számát értjük (és minden elem csak egyszer fordul elő).
Az ismétlés nélküli permutáció képlete: Pn = n!. Az ismétléses permutáció definíciója szerint adott egy véges n elemű halmaz, melyben adott minimum 1 multiplikált elem. Tehát az n elemű halmazban minimum 1 elem legalább 2-szer előfordul. Az ismétléses permutáció képlete: Pn(k1;k2;...ks) = (n!) : (k1! · k2! · ... · ks!).
[szerkesztés] 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ú csoportokat (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: Cn;k = (n!) : [k!(n - k)!]; vagy binominális együtthatókkal kifejezve: n alatt k.
Az ismétléses kombinációt alkalmazzuk, amikor adott n elemekből k elemszámú csoportokat képzünk, de adott legalább 1 multiplikált elem. Az ismétléses kombináció képlete: Cin;k = (n + k - 1 alatt k)-binominális együtthatóval kifejezve.
[szerkesztés] 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-ad osztá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.
[szerkesztés] 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, kombinatorikus halmazelmélet, a játékelmélet és a matroidelmélet.
[szerkesztés] 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,
- Kőnig Dénes,
- Katona Gyula,
- Lovász László,
- Pósa Lajos,
- Rényi Alfréd,
- Simonovits Miklós,
- Szemerédi Endre,
- Szőnyi Tamás,
- Tardos Gábor,
- T. Sós Vera,
- Turán Pál.
[szerkesztés] Szakirodalom
- 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.
[szerkesztés] Külső hivatkozások
 |
Ez a matematikai tárgyú lap egyelőre csonk (erősen hiányos). Segíts te is, hogy igazi szócikk lehessen belőle! |
