Permutáció

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

Ha például ${\displaystyle A}$ egy csomag kártya, akkor a kártyák megkeverésével ${\displaystyle A}$ egy permutációját állítjuk elő. Hasonlóképpen, ha ${\displaystyle A}$ elemei egy futóverseny résztvevői, akkor a verseny minden lehetséges végeredménye ${\displaystyle 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ű ${\displaystyle A}$ halmaz elemeit gyakran az első n pozitív egész számmal azonosítjuk. ${\displaystyle 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:

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

Egy n elemű halmaz permutációinak számát általában ${\displaystyle P_{n}}$-nel jelöljük. ${\displaystyle P_{n}=}$${\displaystyle 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: ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle n}$ elem között találunk ${\displaystyle k_{1},k_{2},\ldots ,k_{m}}$ egymással megegyezőt, akkor ${\displaystyle n}$ elem ${\displaystyle k_{1},k_{2},\ldots ,k_{m}}$-ed rendű ismétléses permutációjának nevezzük. Ezeknek számára a ${\displaystyle P_{n}^{k_{1},k_{2},\ldots ,k_{m}}}$ szimbólumot szokás használni.

${\displaystyle 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: ${\displaystyle P_{k_{1}}=k_{1}!}$, ${\displaystyle P_{k_{2}}=k_{2}!}$, ${\displaystyle \ldots }$, ${\displaystyle 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 ${\displaystyle {1,2,2,3,3}}$ számjegyekből alkotható ötjegyű számok száma például ${\displaystyle 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 ${\displaystyle n \choose k}$ (kiolvasva: n alatt a k) szimbólummal jelöljük. Nevezetes tény, hogy ${\displaystyle {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 ${\displaystyle P_{n}^{k,n-k}}$ kiszámítását kell elvégeznünk. Az ${\displaystyle 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 ${\displaystyle n}$ különböző elem. Vegyük egy permutációját ennek az ${\displaystyle 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 ${\displaystyle 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 (${\displaystyle A_{n}}$).

Jegyzetek

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

• kombinatorika
• elemi kombinatorika
• variáció
• kombináció
• fixpontmentes permutáció
• ciklikus permutáció