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.

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 

Znani 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 

Kompozitum 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 

Ker 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 

Identič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 

V transpoziciji zamenjata mesti samo dva elementa iz množice. Drugi ostanejo na svojih mestih.

Krožna permutacija 

Krož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 

Š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 

Vse 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 

 kombinacija
 binomski koeficient
 ciklična permutacija
 variacija
 particija
 kompozicija

Zunanje povezave 

 Permutacija 
 Permutacija v Preseku 
 

Abstraktna algebra
Kombinatorika
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 elementovpermutacij ) . Za vsako permutacijo so napisane tri zamenjave na treh mestih , kjer so elementi množice . 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 Znani 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 , , se eno izmed permutacij lahko zapiše kot \ . S tem se je permutacijo opisalo z matriko , ki imavrstici instolpcev . Pri tem pa jekardinalnost 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 sezamenja zse zamenja sterzamenja z Drugi oklepaj pa pomeni , da sezamenja sinzamenja s To je : \ . Vsaka permutacija končne množice je produkt disjunktnih ciklov . Kompozitum permutacij Kompozitum 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 sezamenja s ki pa se zaradi permutacije zamenja s V nadaljevanju senajprej zamenja s ki se zamenja z Nato sledi zamenjavaz ki se zamenja s Nato sledi zamenjavas ki ji sledi zamenjava s Zadnja pa je zamenjavaz ki ji sledi zamenjava z S tem se je dobilo končno obliko permutacije . Obratna permutacija Ker 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 Identič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 V transpoziciji zamenjata mesti samo dva elementa iz množice . Drugi ostanejo na svojih mestih . Krožna permutacija Krož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 Š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 Vse 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 Permutacijska matrika ima v vsaki vrstici in stolpcu samo enkrat vpisano enico , na drugih mestih pa vedno Glej tudi kombinacija binomski koeficient ciklična permutacija variacija particija kompozicija Zunanje povezave Permutacija Permutacija v Preseku Abstraktna algebra Kombinatorika