Permutációk, átrendezések

Jelölések:

Definíció: Egy H halmaz permutációja egy p: H-> H bijekció. Legyen S(H) a H halmaz összes permutációjának halmaza.

Megjegyzés: A sorbaállítások és permutációk között egy természetes megfeleltetés van, ha H egy alapsorrendjét lerögzítjük. Ezzel az azonosítással H minden elemének az alapsorrend szerint lesz egy pozíciója. Így a pozíciók (az alapsorrendben elfoglalt helyek) és az objektumok (H elemei) között egy megfeleltetés van. Így a p permutáció (ami alapértelmezésben objektumok halmazából objektumok halmazába történik) tekinthető úgy is, mint pozíciók halmazából objektumok halmazába történő leképezés.

Megjegyzés: A pozíciók és objektumok közötti megfeleltetés alapján egy p:H->H bijekciót értelmezhetünk úgyis mint egy átrendezést: p(i)=j jelentheti azt, hogy ``az i objektum helyére áll a j objektum''.

Definíció: Permutációk szorzása.

Példa a szorzás eredménye és az egymás utáni átrendezések végrehajtása közötti kapcsolatra.

Jelölés: Az n elemű halmaz permutációinak számát pn-nel jelöljük.


Definíció: Ciklikus átrendezés: Szükséges hozzá az alaphalmaz egy C részhalmaza (a ciklikus átrendezés alaphalmaza), amely elemei `egy kör alakú asztal mellé ülnek'. Ezek után a megfelelő ciklikus átrendezésnél a C-n kívüli elemek a helyükön maradnak, a C-hez tartozó elemük a jobb szomszédjuk helyére kerülnek.

Megjegyzés: Vegyünk két ciklikus rendezést, amelyek alaphalmazai diszjunktak. Ekkor a két ciklikus rendezést bármely sorrendben egymás után alkalmazva (két lehetőség rejlik emögött) a szorzat átrendezés ugyanaz lesz.

Tétel: Minden átrendezés előáll, mint H egy osztályozása és az osztályokon belül egy-egy ciklikus átrendezés.


Rekurzió:

Tétel: pn=n.pn-1.

Megjegyzés: A rekurzió azt mondja meg, hogy ha az n elemű H halmaz egy n-1 elemű H' halmaz elemeiből és egy s új elemből áll, akkor H' permutációinak számának n-szerese adja meg H permutációit. Igazából H permutációit generálni fogjuk úgy, hogy H' minden permutációjából H-nak n permutációja keletlezik. Továbbá természetesen minden H-beli permutációt pontosan egyszer állítunk elő.

Bizonyítás (generálás): A H' egy körökbe állításából úgy nyerünk H egy körökbe állítását, hogy az s új elem beáll az egyik H'-beli elem jobb oldalára (n-1 lehetőség) vagy egy új kört alkot (1 lehetőség).


Formula:

Tétel:

(i) pn=n!

(ii) pn=sn

Bizonyítás: (i): Indukció a rekurzió alapján.

(ii): A sorbaállítások és permutációk megfeleltetése alapján.


Aszimptotika:

Egy n elemű halmaz permutációinak n! számára vonatkozó aszimptotikát a Stirling-formula adja meg.

A formula elnevezését James Stirling (1692-1770) matematikusról kapta.