Permutáció

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

Az absztrakt algebrában és a kombinatorikában egy 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 legtöbb vizsgálatban véges, és így permutáción elemeinek egy meghatározott átrendezését vagy sorbarendezését értjük.

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

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.

A permutációk megadása[szerkesztés]

A permutációk vizsgálatakor az n elemű halmaz elemeit gyakran az első n pozitív egész számmal azonosítjuk. -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:

.

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]

(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 -nel jelöljük. . Ez azért van, mert az 1 képe n különböző érték lehet, ezek mindegyiké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]

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é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 sorrend lehetséges.

Alkalmanként annak az 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 elem között találunk egymással megegyezőt, akkor elem -ed rendű ismétléses permutációjának nevezzük. Ezeknek számára a szimbólumot szokás használni.

. 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: , , , . Í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 számjegyekből alkotható ötjegyű számok száma például

Ciklikus permutációk[szerkesztés]

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

A binomiális együtthatók[szerkesztés]

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 (kiolvasva: n alatt a k) szimbólummal jelöljük. Nevezetes tény, hogy . 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 kiszámítását kell elvégeznünk. Az 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]

  • inverziószám: Adott különböző elem. Vegyük egy permutációját ennek az elemnek és legyen ez a természetes sorrend. Ha vizsgálunk 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]

Az n elem feletti permutációk csoportját az n elemű szimmetrikus csoportnak nevezik és nagyon gyakran -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 ().

Hivatkozások[szerkesztés]

Szakirodalom[szerkesztés]

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]

  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.