Permutáció

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.

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 (26 faktoriális), azaz ennyiféle sorrend lehetséges.

A permutációk megadása

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, sorba rendezve 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

(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 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

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 k_i-szer (és így n=k₁ k₂ ... k_s), 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 k₁=3, b betűből k₂=1, c és d betűkből k₃=k₄=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.

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\cdot 2\cdot 2}}=30$

Ciklikus permutációk

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

Bővebben: Binomiális tétel

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 ${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

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á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

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}$ ).

Jegyzetek

↑ Ziya Arnavut, Meral Arnavut (2004. okt.). „Investigation of block-sorting of multiset permutations”. International Journal of Computer Mathematics 81 (10), 1213-1222. o. DOI:10.1080/00207160410001712279. (Hozzáférés: 2010. január 30.)

Szakirodalom

Solt György. Valószínűségszámítás, Bolyai könyvek. Budapest: Műszaki Könyvkiadó, 268. o. (1993). ISBN 9631097811

Kapcsolódó szócikkek

[1] Ziya Arnavut, Meral Arnavut (2004. okt.). „Investigation of block-sorting of multiset permutations”. International Journal of Computer Mathematics 81 (10), 1213-1222. o. DOI:10.1080/00207160410001712279. (Hozzáférés: 2010. január 30.)

[1]