Zoran Skoda
permutacija

Permutacija je bijekcija sa skupa AA u samog sebe. Svaka bijekcija je preslikavanje koje ima inverznu funkciju, ili ekvivalentno funkcija koja je istovremeno injekcija i surjekcija.

Kompozicija dviju surjekcija je surjekcija. Kompozicija dviju injekcija je injekcija. Dakle kompozicija dviju bijekcija je bijekcija.

Zaključujemo da je kompozicija permutacija permutacija.

Kod konačnih skupova imamo slijedeću notaciju.

Neka je SS konačan skup. Tada permutaciju σ:SS\sigma: S\to S zapisujemo u obliku 2×kard(S)2\times kard(S)-matrice (s 22 retka i kard(S)kard(S) elemenata u svakom retku). U prvi red zapisujemo elemente od SS (tipični primjer 1,2,,n1,2,\ldots,n), a u drugi potpisujemo redom njihove vrijednosti (“slike”) po σ\sigma.

Neka je S={a,b,c,d}S = \{a,b,c,d\}. Tada za permutaciju σ\sigma moramo reći u koji element ide aa u koji bb u koji cc u koji dd. dakle, pišemo elemente a,b,c,da,b,c,d u prvi red, a ispod svakog elementa pišemo vrijednost σ(togelementa)\sigma(tog\,\,\,elementa). Dakle

σ=(a b c d σ(a) σ(b) σ(c) σ(b)) \sigma = \left(\array{ a & b & c & d\\ \sigma(a) & \sigma(b) & \sigma(c) & \sigma(b)}\right)

Npr. permutacija

σ=(a b c d d a c b)\sigma = \left(\array{ a & b & c & d\\ d & a & c & b}\right)

šalje aa u σ(a)=d\sigma(a) = d, bb u σ(b)=a\sigma(b) =a, cc u σ(c)=c\sigma(c) = c i dd u σ(d)=b\sigma(d) = b.

Primijetite da se u drugom retku svaki element od SS pojavljuje (jer je permutacija surjekcija) i to točno jednom (jer je permutacija injekcija).

Gledajmo npr. permutacije skupa {1,2,3,4}\{1 ,2,3,4\}. Računajmo kompoziciju

στ=(1 2 3 4 2 1 3 4)(1 2 3 4 3 1 4 2) \sigma\circ\tau = \left(\array{ 1 & 2 & 3 & 4\\ 2 & 1 & 3 & 4}\right) \circ \left(\array{ 1 & 2 & 3 & 4\\ 3 & 1 & 4 & 2}\right)

U kompoziciji funkcija uvijek prvo evaluiramo funkciju na desnoj strani onda funkciju na lijevoj strani. Dakle 11 najprije ide preko τ\tau u 33, a onda 33 ide preko σ\sigma ponovno u 33. Dalje, 22 ide u τ(2)=1\tau(2) = 1, a 11 zatim ide u σ(1)=2\sigma(1) = 2. Slično (στ)(3)=σ(τ(3))=σ(4)=4(\sigma\circ\tau)(3) = \sigma(\tau(3)) = \sigma(4) = 4 i (στ)(4)=σ(τ(4))=σ(2)=1(\sigma\circ\tau)(4) = \sigma(\tau(4)) = \sigma(2) = 1.

Dakle, rezultat je

στ=(1 2 3 4 3 2 4 1) \sigma\circ\tau = \left(\array{ 1 & 2 & 3 & 4\\ 3 & 2 & 4 & 1}\right)

Koliko permutacija ima konačan skup SS od KK elemenata ? Prebrojimo permutacije SSS\to S. Ako je SS konačan skup onda ga možemo gledati kao da je uređen (jednom za svagda). Prvi element možemo smjestiti permutacijom na bilo koje od KK mjesta (uključujući ono na kojem smo bili i prije) tj. pridružiti mu permutacijom onaj element koji je bio prije permutacije na tom mjestu. Sad je jedno mjesto zauzeto (jedan element u kodomeni; to je zato što je permutacija injekcija pa ni jedan drugi element ne smijemo poslati u taj isti element); drugim riječima, kako je permutacija bijekcija slijedeći element možemo staviti na jedno od K1K-1 preostalih mjesta. Dakle prva dva elementa možemo smjestiti na ukupno K×(K1)K\times (K-1) načina. Za svako od tih K×(K1)K\times (K-1) smještenja prva dva elementa, treći element možemo smjestiti na jedno od preostalih K2K-2 mjesta, dakle prva tri elementa možemo smjestiti na K×(K1)×(K2)K\times (K-1)\times(K-2) načina itd. Dakle, sveukupno KK elemenata možemo razmjestiti na

K!=K(K1)(K2)21 K! = K \cdot (K-1) \cdot (K-2) \cdots 2\cdot 1

načina. Npr. riječ ABCABC ima 3!=321=63! = 3\cdot 2\cdot 1 = 6 anagrama, tj. permutacija: ABC,ACB,BAC,BCA,CAB,CBAABC, ACB, BAC, BCA, CAB, CBA. Ovdje smo ih poredali “abecedno” gdje slova koja su naprijed imaju redom veću težinu nego ona iza njih ili, kako to matematičari kažu, leksikografskim uređajem (kao u enciklopediji).

Cayleyev teorem: svaka grupa izomorfna je podgrupi grupe permutacija nekog skupa.

Skica dokaza. Neka je (G,)(G,\cdot) grupa s neutralnim elementom ee. Gledamo grupu svih permutacija Perm(G)Perm(G) same grupe. Među permutacijama su preslikavanja L gL_g, gGg\in G gdje je L g(h)=ghL_g(h) = g\cdot h za svaki hGh\in G. Ako je L g(h)=L g(h)L_g(h) = L_g(h') tada je gh=ghg h = g h', pa ako pomnožimo s lijeva s g 1g^{-1} dobijemo h=hh = h'. Time smo dokazali da je svaka L gL_g injekcija. Surjekcija je zato što L g(g 1k)=kL_g(g^{-1} k) = k dakle svaki kk je u slici.

Sada definiramo homomorphizam grupa L:GPerm(G)L : G\to Perm(G), gL gg\mapsto L_g. Najprije se provjeri da je to homomorfizam, tj. da L aa=L aL aL_{a\cdot a'} = L_a\circ L_{a'}. Zaista, za svaki bBb\in B, L aa(b)=(aa)b=a(ab)=L a(L a(b))=(L aL a)(b)L_{a\cdot a'}(b) = (a\cdot a')\cdot b = a\cdot (a'\cdot b) = L_a(L_{a'}(b)) = (L_a\circ L_{a'})(b). Nakon toga provjerimo da je homomorfizam zapravo injektivan. Injektivnost znači da L g(h)=L g(h)L_g(h) = L_{g'}(h) za sve hh implicira da g=gg = g'. No, prvi identitet raspišemo gh=ghg h = g' h pa množenjem s h 1h^{-1} zdesna, uz korištenje asocijativnosti, daje g=gg = g'. Za kraj dokaza sjetimo da je slika bilo kojeg injektivnog homomorfizma grupa podgrupa kodomene (dakle izomorfna (bijektivna homomorfna) slika početne grupe). Ako smo zaboravili tu činjenicu lako je pokažemo: neka je J:(G,)(H,)J: (G,\cdot)\to (H,\circ) ma koji injektivni homomorfizam grupa i J(G)={hH|g,h=J(G)}J(G) = \{h\in H\,|\,\exists g, h = J(G)\} slika od JJ. Ako su dva elementa, h 1,h 2J(G)h_1, h_2\in J(G) dakle oblika h 1=J(g 1)h_1 = J(g_1), h 2=J(g 2)h_2 = J(g_2), tada je h 1h 2=J(g 1)J(g 2)=J(g 1g 2)h_1\cdot h_2 = J(g_1)\circ J(g_2) = J(g_1\cdot g_2), dakle element iz J(G)J(G). Dakle, J(G)J(G) je zatvoren s obzirom na operaciju \circ u HH. Jedinični element e=J(e)e' = J(e) je u J(G)J(G). Za svaki element hh, inverz od J(g)J(g) je J(g 1)J(g^{-1}) dakle ponovno u J(G)J(G).

category: zadarmat1, zadarmat4

Last revised on March 8, 2018 at 06:47:11. See the history of this page for a list of all contributions to it.