permutáció

A permutáció a halmaz elemeinek adott sorrendben történő átrendezését írja le. Ha a halmaz n különböző elemből áll, akkor minden bijekció a halmazra egy permutációt ad, és a lehető sorrendek száma n!. Például az {1, 2, 3} halmaz 6 különböző permutációt ad.

Rendetíthetünk elemeket úgy is, hogy kiválasztunk k elemet az n-ből és azokat sorrendbe állítjuk. Ebben az esetben az összes lehetséges sorrendek száma P(n,k) = n!/(n−k)!. Ha az ismétlés megengedett, akkor n jelből k elemű sorozatok száma n^k; ismétlés nélkül ez a P(n,k) kifejezés szerinti szám.

Különleges esetek: körkörös permutációk, ahol n elemet körben rendezünk úgy, hogy a kör pozícióinak elforgatása azonos maradjon; ilyen rendezések száma (n−1)!. Derangements vagy fuq halmazokban is nevezett olyan permutációk, amelyekben senki sem marad a kiinduló helyén, száma !n.

Permutációk mint csoportok: az összes n elemű permutáció a S_n csoportot alkotja, amelynek művelete a függvénykompozíció. A permutációk paritása szerint megkülönböztetünk páros és páratlan permutációkat; egy tranzpozíció megváltoztatja a paritást, és a transzpozíciók elegendőek ahhoz, hogy S_n-t generálják.

Multisetek permutációi: ha a rendezendő elemek többszörösen ismétlődnek, akkor a számuk n!/(m1! m2! …), ahol m_i az i-edik érték előfordulásainak száma.

Alkalmazások között találhatók feladatok a kombinatorikában, valószínűségszámításban, rendezési algoritmusokban és különböző területeken, ahol a sorrend meghatározó szerepet játszik.