Permutáció

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

Az absztrakt algebrában és a kombinatorikában egy A halmaz permutációján annak önmagára vett bijektív leképezését értjük. Bár időnként beszélünk végtelen halmazok permutációiról, A a legtöbb vizsgálatban véges, és így permutáción A elemeinek egy meghatározott átrendezését vagy sorbarendezését értjük.

Ha például A egy csomag kártya, akkor a kártyák megkeverésével A egy permutációját állítjuk elő. Hasonlóképpen, ha A elemei egy futóverseny résztvevői, akkor a verseny minden lehetséges végeredménye A egy permutációját képviseli.

A permutációk megadása[szerkesztés | forrásszöveg szerkesztése]

A permutációk vizsgálatakor az n elemű A halmaz elemeit gyakran az első n pozitív egész számmal azonosítjuk. A-nak egy f permutációját úgy adhatunk meg, hogy zárójelben, egymás alá írva, sorbarendezve felsoroljuk az értelmezési tartományát és az értékkészletét. Például n=5 esetén az f(1)=5, f(2)=2, f(3)=1, f(4)=3, f(5)=4 permutációt a következő rövidebb alakban adhatjuk meg:

 \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 5 & 2 & 1 & 3 & 4 \end{pmatrix}

.

Még rövidebb, ha az elemeknek a séma felső sorában szereplő „természetes sorrendjét” is elhagyjuk, és csak a képelemeket írjuk ki: (5, 2, 1, 3, 4). Ez utóbbit néha a permutáció „Descartes-féle alakjának” nevezik [1]


A permutációk száma[szerkesztés | forrásszöveg szerkesztése]

(1,2,3,4) (2,1,3,4) (3,1,2,4) (4,1,2,3)
(1,2,4,3) (2,1,4,3) (3,1,4,2) (4,1,3,2)
(1,3,2,4) (2,3,1,4) (3,2,1,4) (4,2,1,3)
(1,3,4,2) (2,3,4,1) (3,2,4,1) (4,2,3,1)
(1,4,2,3) (2,4,1,3) (3,4,1,2) (4,3,1,2)
(1,4,3,2) (2,4,3,1) (3,4,2,1) (4,3,2,1)

Egy n elemű halmaz permutációinak számát általában P_n-nel jelöljük. P_n=n!. Ez azért van, mert az 1 képe n különböző érték lehet, ezek minegyikéhez n-1 különböző értéket választhatunk a 2 képéül a fennmaradó számokból, ezek mellé a párok mellé n-2-féleképpen választhatjuk a 3 képét, és így tovább. Az n darab szám képeként tehát n(n-1)(n-2)...1=n!-képpen választhatjuk meg a rendezett értékeket.

A jobb oldali táblázat az {1,2,3,4} számok 4!=24 darab permutációját sorolja fel.

A permutációk számára vonatkozó képlet segítségével több elemi kombinatorikai problémát is megoldhatunk.

Az ismétléses permutációk száma[szerkesztés | forrásszöveg szerkesztése]

Alkalmanként annak az A halmaznak, amelynek a permutációit vizsgáljuk, bizonyos elemeit megkülönböztethetetlennek tekintjük. Ilyen eset áll elő például, ha egy édességes zacskóban háromféle cukorkából van összesen 30 darab, vagy ha két egyforma csomag kártyát egybekeverünk. Ha n elem között találunk k_1,k_2,\ldots,k_m egymással megegyezőt, akkor n elem k_1,k_2,\ldots,k_m-ed rendű ismétléses permutációjának nevezzük. Ezeknek számára a P_n^{k_1,k_2,\ldots,k_m} szimbólumot szokás használni.

P_n^{k_1,k_2,\ldots,k_m}=\frac{n!}{k_1!k_2!\ldots k_m!}. Ennek belátásához lássuk el különböző indexszel az ismétlődő elemeket, hogy felhasználhassuk az ismétlés nélküli permutációk számának meghatározására vonatkozó képletet: P_{k_1}=k_1!, P_{k_2}=k_2!, \ldots, P_{k_m}=k_m!. Így megkaptuk az olyan permutációk számát, amelyek megegyeznek egymással (hiszen az indexszel ellátott tagok valójában megegyezők), tehát ezen értékek a szorzatával le kell osztanunk a permutációk számát.

Az {1,2,2,3,3} számjegyekből alkotható ötjegyű számok száma például P_5^{1,2,2}=\frac{5!}{1!2!2!}=\frac{120}{1\cdot2\cdot2}=30

A binomiális együtthatók[szerkesztés | forrásszöveg szerkesztése]

Gyakran merül föl az a kérdés, hogy egy n elemű halmazból hányféleképpen választható ki k elem. Ezt az n-től és k-tól függő számot az n \choose k (kiolvasva: n alatt a k) szimbólummal jelöljük. Nevezetes tény, hogy  \mbox{ }_{  {n \choose k} = \frac{n!}{k!(n-k)!} } . Ezt az alábbiak alapján úgy láthatjuk be, hogy meggondoljuk: itt a kiválasztott k elemet és a ki nem választott n-k elemet egyaránt megkülönböztethetetlennek tekintjük, tehát valójában egyszerűen a P_n^{k,n-k} kiszámítását kell elvégeznünk. Az n \choose k szimbólumok szerepet játszanak a kéttagú (idegen szóval binom) összegek hatványainak kiszámításában, ezért ezeket hagyományosan binomiális együtthatóknak nevezzük.

Fontosabb permutációelméleti fogalmak[szerkesztés | forrásszöveg szerkesztése]

  • inverziószám: Adott n különböző elem. Vegyük egy permutációját ennek az n elemnek és legyen ez a természetes sorrend. Ha vizsgáluk egy permutációban két elemet, meg tudjuk mondani, hogy melyik elem áll előrébb. Nevezzük ezt a két elem viszonyának. A két elem inverzióban áll, ha a vizsgált permutációban és a természetes sorrendben különbözik a viszonyuk. Az inverzióban álló elempárok száma az inverziószám.
  • Permutációk paritása megegyezik az inverziószám paritásával (tehát, ha egy permutációban páros sok inverzió van, a permutációt párosnak nevezzük, ellenkező esetben páratlannak).
  • Permutációs rejtjel: A permutációs kód vagy permutációs rejtjel a klasszikus titkosírás egyik rejtjelezési eljárása.

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

Az n elem feletti permutációk csoportját az n elemű szimmetrikus csoportnak nevezik és nagyon gyakran S_n-nel jelölik. Mivel egy tetszőleges csoport összes elemének egy adott elemmel végzett megszorzása a csoport elemeinek egy permutációját adja, a szimmetrikus csoport bármely más csoportot képes „szimulálni”, azaz bármely n elemű csoport izomorf egy legfeljebb n! elemű szimmetrikus csoport valamely részcsoportjával (Cayley-tétel).

Minden permutáció felbontható diszjunkt ciklikus permutációk szorzatára. Ez a felbontás a ciklushosszakat nézve egyértelmű: az azonos hosszú ciklusokból álló permutációk egymás konjugáltjai. Minden permutáció felbontható továbbá kettő hosszú ciklikus permutációk (cserék) szorzatára.

A páros permutációk is csoportot alkotnak, ez az alternáló csoport (A_n).

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

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

Solt György, Valószínűségszámítás, Műszaki könyvkiadó, Bolyai könyvek, Bp. 1993

Kapcsolódó szócikkek[szerkesztés | forrásszöveg szerkesztése]

  1. Ziya Arnavut; Meral Arnavut: Investigation of block-sorting of multiset permutations. International Journal of Computer Mathematics, évf. 10 sz. (2004 okt.), 1213. - 1222. o. Link beill. 2010. január 30.