Definicija . Svako jedno-na-jedan preslikavanje skupa A od prvih n prirodnih brojeva na sebe naziva se zamjenanti stupanj, i, očito, svaka supstitucija A može se napisati pomoću dvije permutacije, označene jedna ispod druge

Kroz α ja ovdje označava broj u koji, kada se zamijeni A, broj postaje ja , ja = 1, 2, …, n.

Napišimo dvije permutacije od n znakova jednu ispod druge, uzimajući rezultirajuća dva retka u zagrade; na primjer n=5:

Reći ćemo da je broj 3 prelazi preko na broj 5, broj 5 ide na 2, broj 1 ide na 3, broj 4 ide na 4 (ili ostaje na mjestu), i na kraju broj 2 ide na 1. Dakle, dvije permutacije napisane jedna ispod druge u obliku (2) odredite neke preslikavanje jedan na jedan skup prvih pet prirodnih brojeva na sebe, tj. preslikavanje koje svakom od prirodnih brojeva 1, 2, 3, 4, 5 pridružuje jedan isti prirodni broj, a različitim brojevima se pridružuju različiti brojevi.

Jasno je da se preslikavanje jedan na jedan skupa njihovih prvih pet prirodnih brojeva, koje smo dobili pomoću (2), može dobiti ispisivanjem jednog ispod drugog i nekih drugih parova permutacija pet simbola. Ti se zapisi dobivaju iz (2) nekoliko transpozicija (permutacija) stupaca; to su npr.

U svim ovim unosima, 3 ide u 5, 5 u 2, itd.

Supstitucija A ima mnogo različitih unosa oblika (1). Dakle, (2) i (3) su različiti unosi za istu zamjenu 5. stupnja.

Kanonski tip supstitucije

Konkretno, svaka permutacija n-tog stupnja A može se napisati u kanonskom obliku

tj. s prirodnim rasporedom brojeva u gornjem redu. S ovim zapisom, različite zamjene razlikuju se jedna od druge po permutacijama koje se pojavljuju u donjem retku.

Primjer zamjene n-tog stupnja je zamjena identiteta

u kojem svi simboli ostaju na mjestu.

Komentar . Treba primijetiti da gornji i donji redak u unosu (1) supstitucije A imaju različite uloge i njihovim preuređivanjem, općenito govoreći, dobivamo drugačiju supstituciju.

Ciklička supstitucijska struktura

Zamjena tipa

(U ovom slučaju, svi brojevi ja 1 , ja 2 , …, ja m - različito)

naziva se ciklus duljine m.

Uvodi se posebna oznaka za cikluse:

Primjer 1.

Ciklus (2 3 4 1) radi ovako

Teorema. Svaka se supstitucija može rastaviti na produkt neovisnih ciklusa. Ova dekompozicija je jedinstvena do reda ciklusa.

Algoritam za sastavljanje ciklusa:

1. Uzmite zamjenu i pogledajte u što ulazi prvi element.

2. Rezultirajući element upisujemo iza prvog elementa i pronalazimo njegovu sliku pod djelovanjem supstitucije.

3. Čim se slika poklopi s elementom iz kojeg je započela izgradnja ciklusa, zatvorite ciklus.

Primjer 2.

Proširi zamjenu

u proizvod nezavisnih ciklusa.

Riješenje.

Od , dobivamo ciklus (135). Lanac 2→4→2 daje transpoziciju (24). Također 6→8→6 daje transpoziciju (68). 7 ostaje na mjestu.

Preslikavanje jedan na jedan na sebe (ili transformacija) konačnog skupa N = (1, 2, 3, n) prvih n prirodnih brojeva naziva se supstitucija n brojeva (ili supstitucija n-d stupnja). Zamjena se obično piše kao dva retka brojeva u zagradama. Na primjer, korespondencija jedan-na-jedan prirodnih brojeva 1, 2 i 3, dana skupom ((2, 3), (1, 2), (3, 1)) uređenih parova, zapisuje se kao supstitucija p trećeg stupnja (2 1 3 \ P =13 2 1 J" u kojoj 2 ide u 3, 1 u 2 i 3 u 1. Budući da se preslikavanje neće promijeniti kada se promijeni redoslijed uređenih parova, ista zamjena može se prikazati u nekoliko oblika: Poželjno je napisati u kojem se brojevi u gornjem redu nalaze u prirodni poredak. Tada zamjena 71. stupnja poprima oblik (4.19) gdje su t"i, t"2, in prvih n prirodnih brojeva smještenih u nekom specifičnom redoslijedu. Svaka promjena u njihovoj lokaciji odredit će novu zamjenu i ukupan broj zamjena n-ti stupanj odgovara broju n! permutacije prvih n elemenata skupa N u donjem redu (4.19). Supstitucija identiteta n-tog stupnja uzima svaki broj za sebe i može se napisati kao (4.20) Sastav p2°Pi supstitucija n-ti stupanj pi i Rz nazivaju supstituciju n-tog stupnja p = pipi) koja je rezultat sekvencijalnog izvođenja preslikavanja, prvo danog s pi, a zatim danog s />2. Sastav zamjena zapisan je kao njihov produkt, ali uzet obrnutim redoslijedom, s pip? frur\. Na primjer, za supstitucije Jasno je da ako je p supstitucija n-tog stupnja, onda i.e. en igra ulogu neutralnog elementa u odnosu na zakon kompozicije preslikavanja. Ako se linije supstitucije p u (4.19) zamijene, tada se dobiva inverzna supstitucija supstitucije p i ima svojstvo i.e. p"1 igra ulogu elementa simetričnog za p s obzirom na zakon kompozicije preslikavanja. Dakle, skup P od n! supstitucija n-tog stupnja tvori multiplikativnu grupu (vidi tablicu 4.1) s obzirom na ovaj zakon, koji u ovom slučaju igra ulogu multiplikativnog zakona (asocijativnog, ali ne i komutativnog). Skup P nazivamo skupinom permutacija n-tog stupnja. Budući da je prvi redak zapisan u obliku (4.19) nepromijenjen, zamjena n-tog stupnja može se specificirati samo drugim retkom: Grupa permutacija supstitucija n brojeva sastav simetrija grupa figure m Odnosno preuređivanjem prvih n elemenata skupa N. Ako u takvom preuređenju zamijenimo bilo koja dva broja ( ne nužno susjedni), a ostale ostavimo na svojim mjestima, dobivamo novu permutaciju. Ova se transformacija naziva transpozicija permutacije. Dva broja tvore inverziju u permutaciji, kada se manji nalazi desno od većeg ( ili, kako kažu, veći broj u permutaciji dolazi prije manjeg). Permutacija se naziva parnom ako je ukupan broj inverzija u njenom redu paran, a neparnim u suprotnom. Da bi se izračunao ukupan broj inverzija u određenoj permutaciji od n elemenata, svaki element se sekvencijalno uspoređuje, počevši od prvog lijevo, sa svim onima koji ga slijede, a g određuje broj manjih brojeva desno od njega. To daje broj inverzija danog elementa. Tako dobiveni n-1 brojevi se zbrajaju. Primjer 4.12. A. Permutacija (1, 2, ..., n) je parna za bilo koji n, jer je broj inverzija u njoj jednak nuli. b. Permutacija () sadrži 14 inverzija i stoga je parna. V. Permutacija () sadrži 17 inverzija i stoga je neparna. Teorem 4.7. Svaka transpozicija mijenja paritet permutacije. Razmotrimo najprije slučaj kada su preuređeni brojevi r i j susjedni, tj. izvorna permutacija i permutacija dobivena transpozicijom imaju oblik gdje elipse zamjenjuju one brojeve na koje ova transpozicija ne utječe. U obje permutacije, svaki od brojeva t, j čini iste inverzije s brojevima koji ostaju na svojim mjestima. Ako brojevi r i nisu formirali inverziju u izvornoj permutaciji, tada će nakon transpozicije nastati jedna nova inverzija. Ako su ti brojevi u izvornoj permutaciji tvorili inverziju, tada će nakon transpozicije nestati, tj. ukupan broj inverzija bit će za jedan manji. U oba slučaja mijenja se parnost permutacije. Neka se sada između preuređenih brojeva r i j nalazi m brojeva (m 6 N), tj. početna permutacija ima oblik Preuređivanje položaja i i j može se izvršiti kao rezultat sekvencijalnog mijenjanja mjesta susjednih brojeva, izvođenjem 2m + 1 koraka (preuređujemo t s klf zatim t, već umjesto A?i, c, itd., sve dok r u m koraka kt neće zauzeti mjesto kt i neće stajati pored j; tada ćemo zamijeniti i i y, i na kraju će biti potrebno još m koraka za sekvencijalno preuređivanje j s kt- 1 itd., nakon čega će j zauzeti mjesto i, a brojevi kt će zadržati svoja mjesta). U ovom slučaju, parnost permutacije mijenja se neparan broj (2m + 1) puta. Stoga permutacije (4.21) imaju suprotne paritete. Razmotrimo oznaku za supstituciju (4.19). Permutacije koje čine gornji i donji red mogu imati iste ili suprotne paritete. Prijelaz na bilo koji drugi zapis može se postići uzastopnim izvođenjem nekoliko transpozicija u gornjem retku i njihovih odgovarajućih transpozicija u donjem retku. Međutim, izvođenjem jedne transpozicije u gornjem redu (4.19) i jedne transpozicije odgovarajućih elemenata u donjem redu, istovremeno mijenjamo paritete obiju permutacija i stoga čuvamo podudarnost ili suprotnost njihovih pariteta. Iz toga slijedi da su za bilo koji zapis supstitucije pariteti gornjeg i donjeg retka ili isti ili suprotni. Grupa supstitucija supstitucija n brojevi kompozicija simetrija grupa likovi Definicija 4.10. Zamjena se naziva čak i ako permutacije u oba njena reda imaju isti paritet, a neparna ako imaju suprotni paritet. Jasno je da je permutacija identiteta (4.20) parna, a parnost permutacije dane u obliku (4.19) podudara se s parnošću permutacije u njenom donjem redu. Gornje se može generalizirati u odnosu na preslikavanje jedan na jedan na sebe (transformacija) bilo kojeg konačnog skupa E-(ni, 02, an) (ne nužno numeričkog), ako njegove elemente numeriramo s prvih n prirodnih brojeva . Primjer 4.13. Neka su vrhovi jednakostraničnog trokuta (sl. 4.5). ^Kada je skup P sastavljen od n! = 3! = 6 zamjena gdje su “b”2, “z” tri prirodna broja 1, 2, 3 poredana nekim redoslijedom, opisuje skupinu na Sl. 4.5 simetrije ovog trokuta, tj. takva gibanja trokuta u ravnini takva da se poklapa sam sa sobom. Identična zamjena e, kada, ostavlja trokut na mjestu. Kada (jednake zamjene a i 0), trokut rotira u smjeru suprotnom od kazaljke na satu u odnosu na točku O, redom, za kutove a = =3 (vidi sliku 4.5). Kada (neparna zamjena q) trokut rotira oko osi simetrije OA. Rotacije oko osi simetrije OB i OS specificiraju neparne supstitucije z i z, redom, s 4 = 3, "2 = 2, "z = 1 i "1 = 2, "2 = 1, "Z = 3. Proizvod pip ? bilo koja od ovih zamjena također specificira jednu od operacija podudaranja trokuta (na primjer, qr = /?). U lijevom stupcu i gornjem redu tablice. 4.2 sadrži oznake za supstitucije p\ odnosno p2, a na ostalim mjestima - produkte pip? ove zamjene. U svakom retku i u svakom stupcu tablice. 4.2 postoji identična zamjena e, tj. svaka operacija ima simetričnu (ili inverznu), a za operaciju rotacije oko bilo koje osi simetrije (i, naravno, za identičnu operaciju) sama je ova operacija inverzna. Tablica nije simetrična oko svoje glavne dijagonale (prolazi kroz gornji lijevi i donji desni element), što još jednom pokazuje da je produkt supstitucija nekomutativan. Razmatrani skup P supstitucija naziva se i grupom simetrije lika (u ovom slučaju jednakostraničnog trokuta). Slično, može se konstruirati skupina simetrija bilo kojeg drugog geometrijskog objekta kao skup svih transformacija metričkog prostora koje ga spajaju sa samim sobom (na primjer, skupina simetrija kvadrata, kocke, tetraedra itd.). Upravo s takvih pozicija E.S. Fedorov je 1890. izgradio klasifikaciju točnih prostorni sustavi točke u odnosu na kristalografiju. Ovo je bila povijesno prva primjena teorije grupa izravno na prirodne znanosti. Pitanja i zadaci 4.1. Provjeriti ima li zakon kompozicije (operacije) m svojstva asocijativnosti i komutativnosti na skupu E: gdje je GCD najveći zajednički djelitelj dvaju prirodnih brojeva. 4.2. Odredite koje algebarske strukture tvore sljedeći numerički skupovi s obzirom na navedene zakone sastavljanja: a) jedan od skupova s ​​obzirom na zbrajanje i s obzirom na množenje; b) skup svih parnih brojeva u odnosu na zbrajanje i množenje; c) skup potencija zadanog realnog broja af Os u cjelobrojnim eksponentima s obzirom na množenje; d) skup svih kompleksnih korijena zadanog stupnja n € N jedinice s obzirom na množenje; e) skup kompleksnih korijena svih potencija n € 14 jedinice s obzirom na množenje; f) skupovi kompleksnih brojeva sa zadanim modulom r € R s obzirom na množenje; g) skup kompleksnih brojeva s modulom koji ne prelazi zadani broj R f 0, s obzirom na zbrajanje i s obzirom na množenje; h) skup kompleksnih brojeva s modulom različitim od nule koji se nalazi na zrakama koje izlaze iz ishodišta koordinata i tvore kutove y>2i » ¥>m s osi Ox u odnosu na množenje. i) skup P(E) svih podskupova nekog skupa E s obzirom na operacije simetrične razlike i presjeka i s obzirom na svaku od njih posebno. 4.3. Na skupu E = (o, 6, c) jednoj od tablica zadan je zakon kompozicije m. Za svaki od tih zakona odredite njegova svojstva, naznačite neutralni element i parove simetričnih elemenata (ako postoje) i utvrdite vrsta algebarske strukture. 4.4. Na skupu E = (o, 6, c), tablicama su navedeni aditivni (+) i multiplikativni (*) zakoni slaganja. Za svaki od ovih zakona odredite njegova svojstva, navedite neutralni element i parove simetričnih elemenata (ako postoje). Koju algebarsku strukturu tvori skup E s obzirom na svaki od navedenih zakona, a koju s obzirom na oba zakona? Koje značenje dobivaju ovi zakoni u numeričkom skupu ako stavimo a = 1, 6 = 2, c = 3? 4.5. Na skupu E = (0, 1, ru d), aditivni (+) i multiplikativni (*) zakoni sastava navedeni su pomoću tablica. Za svaki od ovih zakona odredite njegova svojstva, navedite neutralni element i parove simetričnih elemenata (ako postoje). Koju algebarsku strukturu tvori skup E s obzirom na svaki od navedenih zakona, a koju s obzirom na oba zakona? 4.6. Dokazati svojstva operacija zbrajanja i množenja kompleksnih brojeva. 4.7. Odredite realne i imaginarne dijelove kompleksnih brojeva: 4.8. Dokažite jednakosti: Grupa permutacija supstitucija n brojeva kompozicija simetrija grupa figure 4.9. Dokažite da | £ C. Pod kojim uvjetima te nejednakosti prelaze u jednakosti? 4.10. Pronađite sve kompleksne brojeve konjugirane na njegov a) kvadrat i b) kub. 4.11. Neka su na kompleksnoj ravnini zadane tri točke zlf z3. 1. Odredite točku r, koja određuje položaj središta mase sustava materijalnih točaka masa mi, m2) tz, smještenih u zadane tri točke. Pod kojim će uvjetom središte mase biti u ishodištu? 2. Zadane točke su vrhovi trokuta. Pronađite točku presjeka njegovih središnjica. Pod kojim će uvjetom biti u ishodištu? 3. Zadane točke su tri vrha A\% A2y paralelograma. Pronađite njegov četvrti vrh L4, nasuprot A2. Pod kojim će uvjetom biti u ishodištu? 4. Pod kojim uvjetom zadane točke leže na istoj ravni? 5. Odredite središte kružnice koja prolazi kroz zadane točke. Pod kojim će uvjetom biti u ishodištu? 6. Kako se nalaze zadane točke ako je |zi| = \z2\ = = 1*z| f 0 i zi + z2 + z3 = 0? 4.12. Odredite skup točaka kompleksne ravnine zadan uvjetom: 4.13. Dokažite jednakosti: a 4.14. Je li jednakost istinita (* 4.15. Pronađite umnožak svih korijena stupnja n € N jedinice. 4.16. Je li broj (2 + i)/(2-«) korijen neke jedinice? 4.17. Pronađite složenu brojeva koji odgovaraju suprotnim vrhovima kvadrata, ako druga dva vrha odgovaraju brojevima z\ i 23. 4.18.Nađite kompleksne brojeve koji odgovaraju vrhovima pravilnog n-kuta, ako brojevi z\ i 22 odgovaraju njegovim dva susjedna vrha 4.19 Dokažite da su cijele nule polinoma s cijelim koeficijentima djelitelji njegovog slobodnog člana (koeficijenta an) i pronađite cijele nule polinoma: 4.20 Dokažite da svaki polinom neparnog stupnja s realnim koeficijentima ima pri najmanje jedna realna nula 4.21.Nađite polinom najmanjeg stupnja s realnim koeficijentima čije su nulte točke: a ) 3 i 2-i; b) t (korijen višestrukosti 2) i -1-i; c) 0, 1, i. 4.22. Nađite: a) polinom s nulama x\, uz uvjet da su brojevi a?i, X2 i a?3 nulte točke polinoma x3 - x2 -1; b) vrijednost a kod koje nule polinoma x3-1-x2 + 2a:+a tvore geometrijsku progresiju; c) zbroj kvadrata i zbroj kubova nula polinoma 8a:4 -- 5®2 + 2« + 1; d) zbroj svih koeficijenata polinoma: 1) ; e) polinom P(x) najmanjeg stupnja prema uvjetu: Nađi paritet supstitucija: 4. 24. Zapišite skupinu simetrija kvadrata, pronađite paritet svake supstitucije iz te skupine, sastavite tablicu sličnu tablici. 4.2 i analizirajte ga.

Definicija . Svako jedno-na-jedan preslikavanje skupa A od prvih n prirodnih brojeva na sebe naziva se zamjenanti stupanj, i, očito, svaka supstitucija A može se napisati pomoću dvije permutacije, označene jedna ispod druge

Kroz α ja ovdje označava broj u koji, kada se zamijeni A, broj postaje ja , ja = 1, 2, …, n.

Napišimo dvije permutacije od n znakova jednu ispod druge, uzimajući rezultirajuća dva retka u zagrade; na primjer n=5:

Reći ćemo da je broj 3 prelazi preko na broj 5, broj 5 ide na 2, broj 1 ide na 3, broj 4 ide na 4 (ili ostaje na mjestu), i na kraju broj 2 ide na 1. Dakle, dvije permutacije napisane jedna ispod druge u obliku (2) odredite neke preslikavanje jedan na jedan skup prvih pet prirodnih brojeva na sebe, tj. preslikavanje koje svakom od prirodnih brojeva 1, 2, 3, 4, 5 pridružuje jedan isti prirodni broj, a različitim brojevima se pridružuju različiti brojevi.

Jasno je da se preslikavanje jedan na jedan skupa njihovih prvih pet prirodnih brojeva, koje smo dobili pomoću (2), može dobiti ispisivanjem jednog ispod drugog i nekih drugih parova permutacija pet simbola. Ti se zapisi dobivaju iz (2) nekoliko transpozicija (permutacija) stupaca; to su npr.

U svim ovim unosima, 3 ide u 5, 5 u 2, itd.

Supstitucija A ima mnogo različitih unosa oblika (1). Dakle, (2) i (3) su različiti unosi za istu zamjenu 5. stupnja.

Kanonski tip supstitucije

Konkretno, svaka permutacija n-tog stupnja A može se napisati u kanonskom obliku

tj. s prirodnim rasporedom brojeva u gornjem redu. S ovim zapisom, različite zamjene razlikuju se jedna od druge po permutacijama koje se pojavljuju u donjem retku.

Primjer zamjene n-tog stupnja je zamjena identiteta

u kojem svi simboli ostaju na mjestu.

Komentar . Treba primijetiti da gornji i donji redak u unosu (1) supstitucije A imaju različite uloge i njihovim preuređivanjem, općenito govoreći, dobivamo drugačiju supstituciju.

Ciklička supstitucijska struktura

Zamjena tipa

(U ovom slučaju, svi brojevi ja 1 , ja 2 , …, ja m - različito)

naziva se ciklus duljine m.

Uvodi se posebna oznaka za cikluse:

Primjer 1.

Ciklus (2 3 4 1) radi ovako

Teorema. Svaka se supstitucija može rastaviti na produkt neovisnih ciklusa. Ova dekompozicija je jedinstvena do reda ciklusa.

Algoritam za sastavljanje ciklusa:

1. Uzmite zamjenu i pogledajte u što ulazi prvi element.

2. Rezultirajući element upisujemo iza prvog elementa i pronalazimo njegovu sliku pod djelovanjem supstitucije.

3. Čim se slika poklopi s elementom iz kojeg je započela izgradnja ciklusa, zatvorite ciklus.

Primjer 2.

Proširi zamjenu

u proizvod nezavisnih ciklusa.

Riješenje.

Od , dobivamo ciklus (135). Lanac 2→4→2 daje transpoziciju (24). Također 6→8→6 daje transpoziciju (68). 7 ostaje na mjestu.

Definicija 5. Zamjena N-ti stupanj naziva se jedan-na-jedan preslikavanje Skupa na sebe. Obično se zamjena piše pomoću dva N-permutacije napisane jedna ispod druge:

, (1)

Gdje kroz označava broj u koji ide element tijekom zamjene ja, tj. ; i=1,2,..., N.

U zapisu zamjene možete nasumično zamijeniti stupce. Na primjer, sve tri zamjene u nastavku su jednake.

. (2)

Konkretno, svaka zamjena N-ti stupanj može se napisati kao:

.

S ovim oblikom zapisa, različite zamjene razlikuju se samo u permutacijama u donjem retku. Tada smo, temeljem teorema 1, dobili sljedeću tvrdnju.

Teorem 4.Broj različitih zamjena n-tog stupnja jednak je N.

Definicija 6.Broj inverzija u zamjeni je zbroj broja inverzija u prvom i drugom retku zamjene.

Broj inverzija u supstituciji označavamo simbolom . Zamjena se zove Čak, ako je broj paran, poziva se Neparan ako je broj neparan. Zamjenski znak je broj:

.

Stoga je zamjenski znak jednak 1 ili -1 ovisno o tome je li zamjenski znak paran ili neparan.

Na temelju teorema 2, kada se preuređuju stupci u supstituciji, pariteti permutacija u donjim i gornjim redovima supstitucije su istovremeno obrnuti. Stoga je očuvan paritet permutacije. Odavde i iz teorema 3 dobivamo sljedeća svojstva supstitucija.

1. Paritet i zamjenski znak ne ovise o obliku zamjenskog znaka.

2. Kada N>1 broj parnih zamjena N stupanj jednak je broju neparnih zamjena i jednak je .

Primjer 4. Supstitucija (2) je neparna i ima predznak -1, iako kod različitih oblika zapisa ima 3, 7, 5 inverzija.

Pokažimo da skup svih supstitucija N-ti stupanj tvori grupu s obzirom na operaciju množenja supstitucija definiranih u nastavku. Ova skupina je od velike važnosti u algebri, tzv Simetrično Skupina i označena je simbolom .

Definicija 7. Produkt supstitucija i N stupanj je sastav ovih produkcija kao preslikavanja, tj. za bilo koji imamo . Određujemo

Kako je kompozicija dvaju bijektivnih preslikavanja biektivna preslikava, tada je umnožak dviju supstitucija N-stupanj postoje postolja N ti stupanj. U praktičnom množenju zamjena prvo se izvodi desna, a zatim lijeva zamjena. Na primjer,

Teorem 5.Skup svih permutacija n-tog stupnja čini grupu s obzirom na operaciju množenja permutacija.

Dokaz. Zbog navedenog je operacija množenja supstitucija binarna algebarska operacija. Provjerimo aksiome grupe.

Množenje supstitucija je asocijativno. Zaista, neka bude. Zatim za bilo koga