Permutacija
Permutácija (oznaka ) (iz latinske besede permutare, kar pomeni zamenjati) je v matematiki z medsebojnimi zamenjavami preurejeno zaporedje znanega končnega števila elementov (pri tem pa število elementov ostane enako). V matematiki je to bijekcija množice elementov samega v sebe, ki se jo zapiše kot:
Permutacije naravnih števil tvorijo simetrično grupo, ki se jo označuje s . Grupa ima svojo identično funkcijo, vsaka permutacija ima tudi obratno permutacijo, ki povrne dano permutacijo v stanje pred zadnjo zamenjavo.
V naslednji razpredelnici so prikazane vse permutacije treh elementov (6 permutacij). Za vsako permutacijo so napisane tri zamenjave na treh mestih, kjer so elementi množice.
permutacija | zamenjava 1 | zamenjava 2 | zamenjava 3 |
---|---|---|---|
1 | |||
2 | |||
3 | |||
4 | |||
5 | |||
6 |
Prva permutacija se imenuje identična permutacija Pri tej permutaciji v resnici ostanejo elementi na svojih mestih. Pri vseh ostalih pa zamenjajo mesta.
Sam postopek preurejanja zaporedja elementov se imenuje permutiranje.
Načini označevanja permutacij
urediZnani so trije različni načini za opis permutacij v končni množici :
- V dvovrstičnem načinu se v prvi vrstici napišejo elementi množice , v drugi vrstici pa se vpiše permutacija elementov.
- Za množico , ki ima elemente {1, 2, 3, 4, 5}, se eno izmed permutacij lahko zapiše kot
- .
- S tem se je permutacijo opisalo z matriko, ki ima 2 vrstici in 5 stolpcev. Pri tem pa je 5 kardinalnost množice, ki se jo permutira. Druga vrstica tako pove na katerem mestu je po permutaciji element, ki je napisan v prvi vrstici. To je enako kot:
- .
- Podobno se zapiše dvovrstični zapis za poljubno število elementov .
- Enovrstični način opisa vsebuje samo drugo vrstico.
- Zgornji primer se zapiše kot:
- Ciklični zapis temelji na dejstvu, da se permutacije izvajajo v določenem zaporedju. V tem načinu zapisa se pokaže kateri elementi so menjali lege, če se permutacije izvajajo po vrsti. To se imenuje tudi razbijanje permutacije v zmnožek disjunktnih ciklov permutacij.
- Zgornjo permutacijo se na ta način zapiše kot:
- . Permutacija elementov se lahko piše v obliki ciklov kot . To pomeni, da se lahko vsako permutacijo napiše kot produkt transpozicij. Vsak element množice nastopa natanko samo v enem ciklu. Vsak cikel pa je tudi permutacija. Permutacija je soda, če je produkt sodega števila transpozicij, in liha, če je produkt lihega števila transpozicij. Sodost in lihost permutacije določa parnost permutacije. Če se potrebuje liho število permutacij, da se pride do identične permutacije, se reče, da je parnost permutacije liha. Podobno velja tudi za sode permutacije.
- To je enako kot:
- ,
- ,
- ,
- ,
- Ciklični zapis permutacije:
- Pomeni, da se 1 zamenja z 2, 2 se zamenja s 5 ter 5 zamenja z 1. Drugi oklepaj pa pomeni, da se 3 zamenja s 4 in 4 zamenja s 3. To je:
- .
Vsaka permutacija končne množice je produkt disjunktnih ciklov.
Kompozitum permutacij
urediKompozitum dveh permutacij in se imenuje produkt permutacij (grupna operacija). Označuje se ga z . V splošnem velja tudi, da produkt permutacij ni komutativen. To pomeni, da . Je pa asociativen .
Zgled: obravnavata se dve permutaciji:
Rezultat se lahko prikaže v obliki matrike s tremi vrsticami:
kjer se je
- v drugo vrstico vpisalo permutacijo
- v tretji vrstici pa je vpisan rezultat kompozituma
Torej je kompozitum dveh permutacij enak:
kjer se je drugo vrstico izpustilo.
Rezultat se dobi tako, da se najprej opravi permutacijo , na dobljeno permutacijo se izvede še permutacijo .
Zgled: po permutaciji se 1 zamenja s 3, ki pa se zaradi permutacije zamenja s 4. V nadaljevanju se 2 najprej zamenja s 5, ki se zamenja z 1. Nato sledi zamenjava 3 z 2, ki se zamenja s 5. Nato sledi zamenjava 4 s 4, ki ji sledi zamenjava s 3. Zadnja pa je zamenjava 5 z 1, ki ji sledi zamenjava z 2. S tem se je dobilo končno obliko permutacije.
Obratna permutacija
urediKer ima bijektivna preslikava tudi obratni element, se lahko definira obratni element tudi za permutacijo. Označi se ga z . Obratna permutacija je tudi ena izmed permutacij. Z dvovrstičnim zapisom (glej spodaj) je to:
- .
Identična permutacija
urediIdentična permutacija preslika vse elemente sama v sebe. To se lahko zapiše kot:
V takšni permutaciji ostane prvi element na prvem mestu, drugi element na drugem in tako dalje do zadnjega elementa množice.
Transpozicija
urediV transpoziciji zamenjata mesti samo dva elementa iz množice. Drugi ostanejo na svojih mestih.
Krožna permutacija
urediKrožna permutacija je permutacija v kateri se premakne elemente urejene množice za določen pomik v levo ali desno, višek elementov na drugi strani pa se vrine na začetku v istem vrstnem redu. To je podobno vrtenju.
Zgled: če je množica in se izvede krožno permutacijo s pomikom za eno mesto proti levi, se bo dobilo zaporedje v množici (prvi element je prišel na zadnje mesto). Če pa bi se naredila krožna permutacija s pomikom na desno, bi bila nova permutacija (zadnji element je prišel na prvo mesto)
Število permutacij
urediŠtevilo vseh permutacij reda je enako:
kjer je:
- fakulteta števila ( ).
Kadar se iz množice elementov vzame elementov, je število permutacij enako . V tem primeru je seveda nekaj elementov nerazporejenih ( ).
Poseben primer je število permutacij, če so v množici med seboj enaki elementi. Če je med elementi enakih , potem je število možnih permutacij enako:
Permutacijska matrika
urediVse permutacije elementov se lahko prikaže kot matriko z razsežnostjo . Običajno se vzame za elemente pri tistih permutacijah pri katerih je , drugi pa so enaki 0. Permutacijska matrika ima v vsaki vrstici in stolpcu samo enkrat vpisano enico, na drugih mestih pa vedno 0.
Glej tudi
urediZunanje povezave
uredi- Permutacija (slovensko)
- Permutacija v Preseku (slovensko)
- Weisstein, Eric Wolfgang. »Permutation«. MathWorld.