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, 2, 3} i {3, 2, 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, 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č. 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 − 1 elemenata, pa za drugi član niza ima n − 1 mogućih izbora. Za izbor prva dva elementa imamo skupa

n · (n − 1) mogućih permutacija.

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.

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.

Poslednji izbor je sada iznuđen, jer je preostao tačno jedan element. 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). Ovaj broj je, po definiciji, jednak n!.

U opštem slučaju, broj permutacija se označava sa P(n, r), _nP_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 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 . 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

= n × (n − 1) × (n − 2) × ... × (n − r + 1) × (n − r) × ... × 2 × 1

= P(n, r) × (n − r) × ... × 2 × 1

= 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 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 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 ⁿP_r, P_n,r, ili _nP_r. Uobičajena moderna notacija je (n)_r što se naziva opadajućim faktorijelom. Međutim, ista notacija se koristi i za rastući faktorijel.

n(n + 1)(n + 2)...(n + r − 1)r.

U notaciji rastućeg faktorijela, broj permutacija je (n − 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.^[1]

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^-1 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 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²(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₁ x₂ … x_L) predstavlja permutaciju koja preslikava x_i u x_i+1 (i=1…L-1) i x_L u x₁, 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 = P ∘ (Q ∘ R).

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

Vidi još

Reference

^ Wussing, Hans (2007), The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory, Courier Dover Publications, str. 94, ISBN 9780486458687, „Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815.”

Literatura

Bogart, Kenneth P. (1990), Introductory Combinatorics (2nd izd.), Harcourt Brace Jovanovich, ISBN 978-0-15-541576-8
Bóna, Miklós (2004), Combinatorics of Permutations, Chapman Hall-CRC, ISBN 978-1-58488-434-7
Bona, Miklos (2012), Combinatorics of Permutations (2nd izd.), CRC Press, ISBN 978-1-4398-5051-0
Brualdi, Richard A. (2010), Introductory Combinatorics (5th izd.), Prentice-Hall, ISBN 978-0-13-602040-0
Cameron, Peter J. (1994), Combinatorics: Topics, Techniques, Algorithms, Cambridge University Press, ISBN 978-0-521-45761-3
Carmichael, Robert D. (1956) [1937], Introduction to the theory of Groups of Finite Order, Dover, ISBN 978-0-486-60300-1
Gerstein, Larry J. (1987), Discrete Mathematics and Algebraic Structures, W.H. Freeman and Co., ISBN 978-0-7167-1804-8
Hall, Marshall, Jr. (1959), The Theory of Groups, MacMillan
Humphreys, J. F. (1996), A course in group theory, Oxford University Press, ISBN 978-0-19-853459-4
Knuth, Donald (1973), Sorting and Searching, The Art of Computer Programming, 3 This book mentions the Lehmer code (without using that name) as a variant C₁,...,C_n of inversion tables in exercise 5.1.1−7 (p. 19), together with two other variants.
Knuth, Donald (2005), Generating All Tuples and Permutations, The Art of Computer Programming, 4, Addison–Wesley, ISBN 978-0-201-85393-3 Fascicle 2, first printing.
McCoy, Neal H. (1968), Introduction To Modern Algebra, Revised Edition, Boston: Allyn and Bacon, LCCN 68015225
Nering, Evar D. (1970), Linear Algebra and Matrix Theory (2nd izd.), New York: Wiley, LCCN 76091646
Rotman, Joseph J. (2002), Advanced Modern Algebra, Prentice-Hall, ISBN 978-0-13-087868-7
Stedman, Fabian (1677), Campanalogia, London The publisher is given as "W.S." who may have been William Smith, possibly acting as agent for the 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".
Biggs, Norman L. (2002), Discrete Mathematics (2nd izd.), Oxford University Press, ISBN 978-0-19-850717-8
Foata, Dominique; Schutzenberger, Marcel-Paul (1970), Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, 138, Berlin, Heidelberg: Springer-Verlag, ISBN 978-3-540-04927-2 . The link is to a freely available retyped (LaTeX'ed) and revised version of the text originally published by Springer-Verlag.
Knuth, Donald (1998), Sorting and Searching, The Art of Computer Programming, 3 (Second izd.), Addison–Wesley, ISBN 978-0-201-89685-5 . Section 5.1: Combinatorial Properties of Permutations, pp. 11–72.

Spoljašnje veze

[1] Wussing, Hans (2007), The Genesis of the Abstract Group Concept: A Contribution to the History of the Origin of Abstract Group Theory, Courier Dover Publications, str. 94, ISBN 9780486458687, „Cauchy used his permutation notation—in which the arrangements are written one below the other and both are enclosed in parentheses—for the first time in 1815.”

[1]

Normativna kontrola
Državne	Izrael Češka
Ostale	Enciklopedija Britanika