Permutacija (matematika)

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

## Definicije
Opšti pojam permutacije može da se definiše formalnije u različitim kontekstima:

### U kombinatorici
U kombinatorici, permutacija se obično shvata kao niz koji sadrži svaki element datog konačnog skupa jednom i samo jednom. 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. Sa druge strane, elementi skupa nemaju uređenje; {1,&nbsp;2,&nbsp;3} i {3,&nbsp;2,&nbsp;1} su samo različiti načini da se označi isti skup.

Međutim, u kombinatorici postoji i tradicionalno, opštije značenje izraza *permutacija*. 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.

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

### 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. Po ovoj definiciji, permutacija je bijekcija iz konačnog skupa u samog sebe. Ovo omogućava definisanje grupa permutacija; videti članak grupa permutacija.

## 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. Na primer, za dati skup slova {A,&nbsp;V,&nbsp;R,&nbsp;A,&nbsp;T}, neke permutacije su VRAT, VATA, VRATA, VATRA i TRAVA ali i AVRAT – niz ne mora da daje neku postojeću reč. Sa druge strane, TATA, nije permutacija jer koristi slovo T dva puta.

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. Ovo neformalno može da se pokaže na sledeći način. Pri konstruisanju permutacije postoji *n* mogućih izbora za prvi član niza. Kada je prvi element izabran preostalo je *n*&nbsp;&minus;&nbsp;1 elemenata, pa za drugi član niza ima *n*&nbsp;&minus;&nbsp;1 mogućih izbora. Za izbor prva dva elementa imamo skupa
:*n*&nbsp;&middot;&nbsp;(*n*&nbsp;&minus;&nbsp;1) mogućih permutacija.

Za izbor trećeg člana niza je onda preostalo *n*&nbsp;&minus;&nbsp;2 elemenata, što za prva tri člana ukupno daje,
:*n*&nbsp;&middot;&nbsp;(*n*&nbsp;&minus;&nbsp;1)&nbsp;&middot;&nbsp;(*n*&nbsp;&minus;&nbsp;2) mogućih permutacija.

Ako se nastavi na sličan način dok ne ostanu samo dva elementa, postoje tačno 2 izbora, što za *n*&nbsp;&minus;&nbsp;1 elemenata daje ukupan broj permutacija jednak:
:*n*&nbsp;&middot;&nbsp;(*n*&nbsp;&minus;&nbsp;1)&nbsp;&middot;&nbsp;(*n*&nbsp;&minus;&nbsp;2)&nbsp;&middot;&nbsp;...&nbsp;&middot;&nbsp;2.

Poslednji izbor je sada iznuđen, jer je preostao tačno jedan element. Znači ukupan broj permutacija je
:*n*&nbsp;&middot;&nbsp;(*n*&nbsp;&minus;&nbsp;1)&nbsp;&middot;&nbsp;(*n*&nbsp;&minus;&nbsp;2)&nbsp;&middot;&nbsp;...&nbsp;&middot;&nbsp;2&nbsp;&middot;&nbsp;1
(što je isto kao i prethodni broj jer 1 kao množilac ne pravi razliku u rezultatu). Ovaj broj je, po definiciji, jednak *n*!.

U opštem slučaju, broj permutacija se označava sa *P*(*n*,&nbsp;*r*), *n**P**r*, ili ponekad P_n^r,
gde je:
* *n* broj elemenata dostupnih za izbor, a 
* *r* je broj elemenata koji se biraju (0 ≤ *r* ≤ *n*).

Za slučaj kada je *r* = *n* &nbsp; je već pokazano da je *P*(*n*, *n*) = *n*!. Opšti slučaj je dat formulom: 
: P(n, r) = \frac{n!}{(n-r)!}.
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*&nbsp;. &nbsp; Broj tada dostignutih permutacija iznosi:
:*P*(*n*, *r*) = *n* × (*n* − 1) × (*n* − 2) × ... × (*n* − *r* + 1).

Pa je:
:*n*! = *n* × (*n* − 1) × (*n* − 2) × ... × 2 × 1
:&nbsp;&nbsp;&nbsp;&nbsp; = *n* × (*n* − 1) × (*n* − 2) × ... × (*n* − *r* + 1) × (*n* − *r*) × ... × 2 × 1
:&nbsp;&nbsp;&nbsp;&nbsp; = *P*(*n*, *r*) × (*n* − *r*) × ... × 2 × 1
:&nbsp;&nbsp;&nbsp;&nbsp; = *P*(*n*, *r*) × (*n* − *r*)!.

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

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. U ovom slučaju, *n* = 10 a *r* = 3. Korišćenjem formule da se izračuna *P*(10,3), dobija se

: P(10,3) = \frac{10!}{(10-3)!} = \frac{10!}{7!} = \frac{7!\times 8 \times 9 \times 10}{7!} = 8 \times 9 \times 10 = 720. 

U specijalnom slučaju kada je *n* = *r*&nbsp; formula se pojednostavljuje:

: P(n,r) = \frac{n!}{0!} = \frac{n!}{1} = n!. 

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

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.

Pošto je nepraktično da se računa n! ako je vrednst *n*&nbsp; suviše velika, efikasniji način je da se računa:
:*P*(*n*, *r*) = *n* × (*n* − 1) × (*n* − 2) × ... × (*n* − *r* + 1).

Druge, starije notacije uključuju *n**P**r*, *P**n*,*r*, ili *n**P**r*. Uobičajena moderna notacija je (*n*)*r* što se naziva *[[opadajući faktorijle|opadajućim faktorijelom]]*. Međutim, ista notacija se koristi i za *[[rastući faktorijel]]*.

:*n*(*n* + 1)(*n* + 2)...(*n* + *r* &minus; 1)*r*.

U notaciji rastućeg faktorijela, broj permutacija je (*n* &minus; *r* + 1)*r*.

## 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. Prethodni primer, pravljenja permutacija brojeva od 1 do 10, bi bio ovde bio preslikavanje skupa {1, ..., 10} u samog sebe.

Apstraktnije, permutacija može da se smatra filtracijom (lancem podskupova): uređenje \{0,1,2\} odgovara filtraciji \{0\} \subset \{0,1\} \subset \{0,1,2\}. 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.

## Notacija
Postoje dve glavne notacije za permutacije.

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):
: \begin{pmatrix}
1 & 2 & 3 & 4 & 5 \\ 
2 & 5 & 4 & 3 & 1\end{pmatrix} = \begin{pmatrix}1 & 2 & 5 \end{pmatrix} \begin{pmatrix}3 & 4 \end{pmatrix} = \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}1 & 2 & 5 \end{pmatrix}= \begin{pmatrix}3 & 4 \end{pmatrix} \begin{pmatrix}5 & 1 & 2 \end{pmatrix}
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.

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. 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<sup>-1</sup>* of {1,...,*n*} je morfizam iz simetrične grupe od *E* u {1,...,*n*}, vidi ispod.)

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

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

Svaki ciklus (*x*1 *x*2 ... *x**L*) predstavlja permutaciju koja preslikava *x**i* u *x**i*+1 (*i*=1...*L*-1) i *x**L* u *x*1, a ostale elemente ostavlja netaknutim.
*L* je dužina ciklusa. 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)). 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). Kanonski način za predstavljanje takvih ciklusa je da se počne od najmanjeg elementa u svakom ciklusu.

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

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

## Proizvod i inverz permutacija

Proizvod dve permutacije može da se definiše na sledeći način. 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. 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*&nbsp;= *P* ∘ (*Q* ∘ *R*).

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

## Povezano

* 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


## Literatura

* Donald Knuth. *The Art of Computer Programming*, Volume&nbsp;3: *Sorting and Searching*, Second Edition. Addison-Wesley, 1998. . Section 5.1: Combinatorial Properties of Permutations, pp.&nbsp;11–72.
*  
* 
* 
* 
* 
* 
* Donald Knuth. *The Art of Computer Programming*, Volume&nbsp;4: *Generating All Tuples and Permutations*, Fascicle&nbsp;2, first printing.  Addison–Wesley, 2005. .
* Donald Knuth. *The Art of Computer Programming*, Volume&nbsp;3: *Sorting and Searching*, Second Edition. Addison–Wesley, 1998. . Section 5.1: Combinatorial Properties of Permutations, pp.&nbsp;11–72.
* 
* 
* 
*   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.  *In quotations the original long "S" has been replaced by a modern short "s".*
* Martin Aigner: Diskrete Mathematik. Vieweg, 2006, .
* Michael Artin: Algebra. Birkhäuser, 1998, .
* Albrecht Beutelspacher: Lineare Algebra. 6. durchgesehene und ergänzte Auflage. Vieweg, 2003, .
* Konrad Jacobs, Dieter Jungnickel: Einführung in die Kombinatorik. de Gruyter, 2003, .
* Hans Kurzweil, Bernd Stellmacher: Theorie der endlichen Gruppen: eine Einführung. Springer, 1998, .
* Kristina Reiss, Gernot Stroth: Endliche Strukturen. Springer, 2011, .

## Vanjske 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 
* 
*