Permutacija (matematika)
<s>U nekoliko oblasti matematike, izraz permutacija se koristi u različitim ali blisko povezanim značenjima.</s><s>Sva ova značenja se tiču pojma preslikavanja elemenata skupa u druge elemente skupa, to jest, zamene mesta (permutovanja) elemenata skupa.</s>

<s>Definicije 
Opšti pojam permutacije može da se definiše formalnije u različitim kontekstima:</s>

<s>U kombinatorici 
U kombinatorici, permutacija se obično shvata kao niz koji sadrži svaki element datog konačnog skupa jednom i samo jednom.</s><s>Pojam niza se razlikuje od pojma skupa, po tome što se elementi niza javljaju po nekom redu: niz ima prvi element (osim ako je prazan), drugi element (osim ako mu je dužina manja od 2), i tako dalje.</s><s>Sa druge strane, elementi skupa nemaju uređenje; {1, 2, 3} i {3, 2, 1} su samo različiti načini da se označi isti skup.</s>

<s>Međutim, u kombinatorici postoji i tradicionalno, opštije značenje izraza permutacija.</s><s>U ovom opštijem smislu, permutacije su oni nizovi kod kojih se svaki element pojavljuje najviše jednom, ali ne moraju svi elementi iz datog skupa da budu iskorišćeni.</s>

<s>Za više podataka o srodnom pojmu u kome uređenje izabranih elemenata iz skupa nije od značaja, videti članak kombinacija.</s>

<s>U teoriji grupa 
U teoriji grupa i srodnim oblastima, elementi permutacije nisu poređani u linearnom uređenju, ili u bilo kom drugom uređenju.</s><s>Po ovoj definiciji, permutacija je bijekcija iz konačnog skupa u samog sebe.</s><s>Ovo omogućava definisanje grupa permutacija; videti članak grupa permutacija.</s>

<s>Prebrojavanje permutacija 
U ovom odeljku se koristi tradicionalna definicija iz kombinatorike, po kojoj je permutacija uređeni niz elemenata izabranih iz datog konačnog skupa, bez ponavljanja, i ne nužno korišćenjem svih elemenata datog skupa.</s><s>Na primer, za dati skup slova {A, V, R, A, T}, neke permutacije su VRAT, VATA, VRATA, VATRA i TRAVA ali i AVRAT – niz ne mora da daje neku postojeću reč.</s><s>Sa druge strane, TATA, nije permutacija jer koristi slovo T dva puta.</s>

<s>Ako n označava veličinu skupa – broj elemenata dostupnih za izbor – a posmatraju se jedino permutacije koje koriste svih n elemenata, onda je ukupan broj mogućih permutacija jednak n!, gde ! označava faktorijel.</s><s>Ovo neformalno može da se pokaže na sledeći način.</s><s>Pri konstruisanju permutacije postoji n mogućih izbora za prvi član niza.</s><s>Kada je prvi element izabran preostalo je n − 1 elemenata, pa za drugi član niza ima n − 1 mogućih izbora.</s><s>Za izbor prva dva elementa imamo skupa
n · (n − 1) mogućih permutacija.</s>

<s>Za izbor trećeg člana niza je onda preostalo n − 2 elemenata, što za prva tri člana ukupno daje,
n · (n − 1) · (n − 2) mogućih permutacija.</s>

<s>Ako se nastavi na sličan način dok ne ostanu samo dva elementa, postoje tačno 2 izbora, što za n − 1 elemenata daje ukupan broj permutacija jednak:
n · (n − 1) · (n − 2) · ... · 2.</s>

<s>Poslednji izbor je sada iznuđen, jer je preostao tačno jedan element.</s><s>Znači ukupan broj permutacija je
n · (n − 1) · (n − 2) · ... · 2 · 1
(što je isto kao i prethodni broj jer 1 kao množilac ne pravi razliku u rezultatu).</s><s>Ovaj broj je, po definiciji, jednak n!.</s>

<s>U opštem slučaju, broj permutacija se označava sa P(n, r), nPr, ili ponekad ,
gde je:
 n broj elemenata dostupnih za izbor, a 
 r je broj elemenata koji se biraju (0 ≤ r ≤ n).</s>

<s>Za slučaj kada je r = n   je već pokazano da je P(n, n) = n!.</s><s>Opšti slučaj je dat formulom:</s>

<s>Kao i u prethodnom slučaju, ovo neformalno može da se pokaže posmatranjem konstrukcije proizvoljne permutacije, ali u ovom slučaju se postupak zaustavlja kada se dostigne dužina r .</s><s>Broj tada dostignutih permutacija iznosi:
P(n, r) = n × (n − 1) × (n − 2) × ... × (n − r + 1).</s>

<s>Pa je:
n! = n × (n − 1) × (n − 2) × ... × 2 × 1
     = n × (n − 1) × (n − 2) × ... × (n − r + 1) × (n − r) × ... × 2 × 1
     = P(n, r) × (n − r) × ... × 2 × 1
     = P(n, r) × (n − r)!.</s>

<s>Ali ako je n! = P(n, r) × (n − r)!, onda P(n, r) = n! / (n − r)!.</s>

<s>Na primer, ako postoji ukupno 10, a bira se niz od tri elementa iz ovog skupa, onda je prvi izbor jedan od 10 elemenata, sledeći je jedan od preostalih 9, i konačno jedan od preostalih 8, što daje 10 × 9 × 8 = 720 permutacija.</s><s>U ovom slučaju, n = 10 a r = 3. Korišćenjem formule da se izračuna P(10,3), dobija se</s>

<s>U specijalnom slučaju kada je n = r  formula se pojednostavljuje:</s>

<s>Razlog zašto je 0! = 1 je taj što je 0! prazan proizvod, koji je uvek jednak 1.</s>

<s>U primeru sa 6 celih brojeva {1..6}, ovo bi bilo:
P(6,6) = 6! / (6−6)! = (1×2×3×4×5×6) / 0! = 720 / 1 = 720.</s>

<s>Pošto je nepraktično da se računa  ako je vrednst n  suviše velika, efikasniji način je da se računa:
P(n, r) = n × (n − 1) × (n − 2) × ... × (n − r + 1).</s>

<s>Druge, starije notacije uključuju nPr, Pn,r, ili nPr. Uobičajena moderna notacija je (n)r što se naziva opadajućim faktorijelom.</s><s>Međutim, ista notacija se koristi i za rastući faktorijel.</s>

<s>n(n + 1)(n + 2)...(n + r − 1)r.</s>

<s>U notaciji rastućeg faktorijela, broj permutacija je (n − r + 1)r.</s>

<s>Permutacije u teoriji grupa 
Kao što je već opisano, u teoriji grupa izraz permutacija (skupa) se koristi za bijektivno preslikavanje (bijekciju) iz konačnog skupa u samog sebe.</s><s>Prethodni primer, pravljenja permutacija brojeva od 1 do 10, bi bio ovde bio preslikavanje skupa {1, …, 10} u samog sebe.</s>

<s>Apstraktnije, permutacija može da se smatra filtracijom (lancem podskupova): uređenje  odgovara filtraciji .</s><s>Iz tačke gledišta polja sa jednim elementom, uređenje na skupu odgovara maksimalnoj filtraciji na vektorskom prostoru, kada se smatra da je skup vektorski prostor nad poljem sa jednim elementom; ovo povezuje svojstva simetrične grupe sa svojstvima algebarskih grupa.</s>

<s>Notacija 
Postoje dve glavne notacije za permutacije.</s>

<s>U relacionoj notaciji dovoljno je samo ispisati prirodno uređenje elemenata koji se permutuju u prvom redu, a novo uređenje u drugom redu (prvi primer dole):
 
označava permutaciju s skupa {1, 2, 3, 4, 5} definisanu kao s(1)=2, s(2)=5, s(3)=4, s(4)=3, s(5)=1.</s>

<s>Ako je dat konačan skup E sačinjen od n elemenata, to je po definiciji bijekcija sa skupom {1, …, n}, gde ova bijekcija f odgovara prostom ređanju elemenata.</s><s>Kada su oni poređani, mogu da se identifikuju permutacije na skupu E sa permutacijama na skupu {1, …, n}. (Rečeno matematički, funkcija koja preslikava permutaciju s iz E u permutaciju f o s o f-1 of {1,…,n} je morfizam iz simetrične grupe od E u {1,…,n}, vidi ispod.)</s>

<s>Alternativno, permutacija može da se predstavi načinom na koji elementi menjaju mesta kada se permutacija primenjuje redom.</s><s>Ovo se naziva dekompozicijom permutacije u proizvod disjunktnih ciklusa. koristi se ciklična notacija (zadnja tri primera gore).</s><s>Permutacija se zapisuje na sledeći način: krene se od nekog elementa x, i zapisuje se niz (x s(x) s2(x) …) sve dok se opet ne javi početni element (koji se ne zapisuje ponovo već se zatvaraju zagrade).</s>

<s>Zatim se uzme neki element koji nije još iskorišćen i započne sledeći ciklus, i tako sve dok ima elemenata.</s><s>U gornjem primeru se dobija: s = (1 2 5) (3 4).</s>

<s>Svaki ciklus (x1 x2 … xL) predstavlja permutaciju koja preslikava xi u xi+1 (i=1…</s><s>L-1) i xL u x1, a ostale elemente ostavlja netaknutim.</s><s>L je dužina ciklusa.</s><s>Kako ovi ciklusi po konstrukciji imaju disjunktne nosače (to jest ponašaju se kao netrivijalno disjunktni podskupovi od E), oni komutiraju (na primer, (1 2 5) (3 4) = (3 4)(1 2 5)).</s><s>Redosled cikulsa u proizvodu nije bitan, dok je redosled elemenata u svakom ciklusu bitan (do na cikličnu promenu; vidi još ciklusi i nepokretne tačke).</s><s>Kanonski način za predstavljanje takvih ciklusa je da se počne od najmanjeg elementa u svakom ciklusu.</s>

<s>1-ciklus (ciklus dužine 1) jednostavno fiksira element koji se u njemu nalazi, tako da se takvi ciklusi obično ne zapisuju eksplicitno.</s><s>U nekim knjigama se ciklusi definišu tako da isključuju cikluse dužine 1.</s>

<s>Ciklusi dužine dva se nazivaju transpozicijama; takve permutacije prosto zamenjuju mesta dvama elementima.</s>

<s>Proizvod i inverz permutacija</s>

<s>Proizvod dve permutacije može da se definiše na sledeći način.</s><s>Ako su date dve permutacije, P i Q, primenjivanje prvo P a zatim Q bi dalo isti rezultat kao i primena samo jedne neke permutacije, R. Proizvod permutacija P i Q se tada definiše kao permutacija R. Ako se permutacije posmatraju kao bijekcije, proizvod dveju permutacija je isto što i njihova kompozicija kada se one posmatraju kao funkcije.</s><s>Ne postoji univerzalno prihvaćena notacija za operaciju proizvoda permutacija, i zavisnosti od literature formula kao što je PQ može da bude bilo P ∘ Q bilo Q ∘ P. Kako je kompozicija funkcija asocijativna, i proizvod permutacija je asocijativan: (P ∘ Q) ∘ R = P ∘ (Q ∘ R).</s>

<s>Slično, kako bijekcije imaju inverze, imaju ih i permutacije, i P ∘ P−1 i P−1 ∘ P su idenitične permutacije (vidi niže) koje ostavljaju sve elemente na svojim mestima.</s><s>To znači da permutacije obrazuju grupu.</s>

<s>Vidi još 
 Alternirajuća permutacija
 Binomni koeficijent
 Kombinacija
 Kombinatorika
 Konvolucija
 Ciklično uređenje
 Ciklična permutacija
 Permutaciona grupa
 Verovatnoća
 Slučajna permutacija
 Simetrična grupa</s>

<s>Literatura</s>

<s>Donald Knuth.</s><s>The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition.</s><s>Addison-Wesley, 1998. .</s><s>Section 5.1: Combinatorial Properties of Permutations, pp.11-72.</s><s>Donald Knuth.</s><s>The Art of Computer Programming, Volume 4: Generating All Tuples and Permutations, Fascicle 2, first printing.</s><s>Addison–Wesley, 2005. .</s><s>Donald Knuth.</s><s>The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition.</s><s>Addison–Wesley, 1998. .</s><s>Section 5.1: Combinatorial Properties of Permutations, pp.</s><s>11–72.</s><s>The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the Ancient Society of College Youths, to which society the "Dedicatory" is addressed.</s><s>In quotations the original long "S" has been replaced by a modern short "s".</s><s>Martin Aigner: Diskrete Mathematik.</s><s>Vieweg, 2006, .</s><s>Michael Artin: Algebra.</s><s>Birkhäuser, 1998, .</s><s>Albrecht Beutelspacher: Lineare Algebra.</s><s>6. durchgesehene und ergänzte Auflage.</s><s>Vieweg, 2003, .</s><s>Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. de Gruyter, 2003, .</s><s>Hans Kurzweil, Bernd Stellmacher: Theorie der endlichen Gruppen: eine Einführung.</s><s>Springer, 1998, .</s><s>Kristina Reiss, Gernot Stroth: Endliche Strukturen.</s><s>Springer, 2011, .</s>

<s>Spoljašnje veze 
 Mnogi uobičajeni matematički zadaci u vezi sa permutacijama i kombinacijama, sa detaljnim rešenjima
 Permutations and Puzzles on Graphs
 Onlajn kalkulator permutacija i varijacija
 Opis Actionscript generatora permutacija</s>

<s>Apstraktna algebra
Kombinatorika</s>

