Permutációk

A permutációk a rendezések fogalma. Egy n elemből álló halmaz rendezett elrendezéseit értjük alatta. Ha n különböző elem van, akkor minden permutáció egy olyan sorozat, amelyben minden elem pontosan egyszer szerepel, és a sorozat hossza n. A lehetséges permutációk száma n!. Például {A, B, C} esetén 3! = 6 permutáció létezik: ABC, ACB, BAC, BCA, CAB, CBA.

Részpermutációk és kiválasztások esetén a sorrend számít: ha n elemből k elemet választunk és rendezünk, akkor a szám P(n, k) = n!/(n−k)!.

Ismétlődő elemek esetén a rendezések száma megváltozik: ha az elemek minta szerint ismétlődnek úgy, hogy m1, m2, ..., mr ismétlődések száma van, akkor a rendezések száma n!/(m1! m2! ... mr!).

Speciális típusok közé tartozik a derangement, azaz olyan permutáció, amelyben senki sem marad a kiindulási helyén. A derangementok száma !n = n! sum_{i=0}^n (-1)^i / i!, közelítőleg közel n!/e érték körül mozog.

Alkalmazások szerint a permutációk alapvető eszközei a kombinatorikának: rendezési problémák, sorozatbeosztások, adat- és kódolási feladatok modellezése során használatosak. Különböző helyettesítési és kiválasztási problémákat, illetve multisetek rendezését is le lehet vele írni és kiszámolni.