IV.1.  Bijektio ja permutaatio

Kertaamme ensin perusasioita kuvauksista. Kahden kuvauksen ja yhdistetty kuvaus määritellään asettamalla kaikilla . Joukon identtinen kuvaus taas määritellään yksinkertaisesti säännöllä kaikilla .

Kahden joukon välinen kuvaus on erikoisesti injektio, surjektio tai bijektio seuraavassa taulukossa esitettyjen määrittelyjen mukaisesti.

Bijektiolla on aina käänteiskuvaus , jolle

Nämä ehdot voidaan kirjoittaa myös muotoon

ja .

Esimerkiksi alla olevan kuvan mukainen nelialkioisten joukkojen välinen kuvaus on bijektio.

Tarkastelemme jatkossa erityisesti saman joukon bijektioita itselleen. Näitä sanotaan, varsinkin äärellisille joukoille , myös permutaatioiksi. Kiinteälle joukolle käytämme kaikkien sen bijektioiden joukosta merkintää , siis

.

Koska bijektioiden yhdistetyt kuvaukset ja niiden käänteiskuvaukset ovat edelleen bijektioita, ovat joukon kahden permutaation ja myötä aina permutaatioita myös kuvaukset , , , , , , jne. Lisäksi tiedetään, että bijektioille pätee sääntö .

Erityisesti joukoille käytetään permutaatioiden muodostamasta joukosta myös merkintää . Tapauksessa löytyy vain yksi permutaatio, identtinen kuvaus. Siitä syystä oletammekin jatkossa aina, että . Näitä joukkoja tarkastelemme lähemmin.

Esimerkki 4.1.1.

Määrätään joukon alkiot. Kaksialkioiselle joukolle voi löytää vain kaksi bijektiota. Kuvan merkinnöin siis .

Esimerkki 4.1.2.

Määrätään joukon alkiot. Kolmialkioisen joukon alkiot voi panna eri järjestykseen (permutoida) seuraavasti: 1−2−3, 2−1−3, 3−2−1, 1−3−2, 2−3−1, 3−1−2, yhteensä siis kuudella eri tavalla. Näistä jokainen voidaan ilmoittaa kuvauksena, esimerkiksi tapausta 2−1−3 esittää alla kuvattu kuvaus .

Tämä sama riippuvuus ilmoitetaan usein myös vähemmän pystysuunnassa tilaa vievästi kaksirivisenä taulukkona tai 'matriisina' seuraavaan tapaan:

.

Siinä alarivissä ovat lueteltuina ylärivin alkioiden kuvat: , ja . Tällä tavalla esitettynä joukon alkiot ovat siten:

Yleisemminkin permutaatiota merkitsemme 2−rivisenä taulukkona seuraavasti

.

Tällaisessa esityksessä alkio ja sen kuva-alkio ovat aina allekkain. Näiden parien järjestyksellä ei ole merkitystä, vaikkakin ne usein esitetään ylärivin lukujen pienuusjärjestyksessä. Esimerkiksi kaikki seuraavat matriisit esittävät samaa edellä olevan esimerkin permutaatiota :

.

Koska permutaatiot ovat kuvauksia, ovat kaksi permutaatiota samat, jos ne kuvaavat kaikki alkiot täsmälleen samalla tavalla. Tämän perusteella voimmekin päätellä, montako eri permutaatiota joukossa on. Ensinnäkin kuva-alkio voidaan valita eri tavalla. Koska permutaatioille (eli bijektioille) eri alkioiden pitää kuvautua eri alkioiksi, alkio voidaan valita sen jälkeen enää eri tavalla. Näin jatkamalla (ja induktiolla todistamalla) saadaan seuraava tulos.

Lause 4.1.3.

Joukossa on eri alkiota (permutaatiota), ts. .

Lauseessa esiintyvä kertoma määritellään tulona . Tuloksen mukaan ja , kuten edellä esimerkeissä 4.1.1 ja 4.1.2 todettiinkin. Sen jälkeen mahtavuudet kasvavat nopeasti:

,   ,   ,   ,   jne.

Opiskelutehtävä 34. (Permutaatioiden lukumäärä)

(a)  Kuinka monta sellaista permutaatiota, jotka kuvaavat alkion 1 itselleen, on ryhmässä ? Entä sellaista, jotka kuvaavat joko alkiot 1 ja 2 molemmat itselleen tai molemmat toisikseen?

(b)  Yleistyksenä ilmoita edelleen, kuinka monta sellaista permutaatiota, jotka kuvaavat ensimmäistä alkiota kaikki itselleen, on ryhmässä ? Entä sellaista, jotka kuvaavat ne keskenään joko itselleen tai toisikseen?

Vinkki tehtävään 34

Permutaatioita voidaan tietenkin yhdistää kuten kuvauksiakin. Usein vain kuvausten yhdistämistä osoittava pallomerkintä jätetään pois ja sen sijasta käytetään pelkkää tulomerkintää (ilman mitään välimerkkiä).

Esimerkki 4.1.4.

Muodostetaan joukon alkioiden

tulot (esimerkin 4.1.2 merkintöjä käyttäen). Näiden yhdistetylle kuvaukselle on

joten

Sama nähdään myös graafisesti:

Vastaavasti samat permutaatiot toisinpäin kerrottuna antavat tuloksen

Huomaa erityisesti, että permutaatiot kerrotaan, kuten kuvaukset yhdistetään, oikealta vasemmalle: ensin siis katsotaan, mitä oikeanpuoleinen kuvaus tekee kullekin alkiolle, ja sitten, mitä vasemmanpuoleinen tekee niille sen jälkeen. Esimerkiksi yllä viimeisimmässä yhtälössä kuvaa alkion 3 ensin alkioksi 2 ja sitten alkion 2 alkioksi 1; yhdistettynä siis alkio 3 kuvautuu alkioksi 1.

Huomaa myös, että kertolasku voi antaa eri tuloksen kertomisjärjestyksestä riippuen. Näin tapahtuikin yllä esimerkissä 4.1.4, jossa siis

.

Permutaation käänteispermutaatio (käänteiskuvaus) näkyy helposti matriisiesityksestä: riittää vain vaihtaa ylä- ja alarivit keskenään (jonka jälkeen kuvausparit voi järjestää ylärivin mukaan pienuusjärjestykseen). Tämä perustuu yksinkertaisesti siihen, että permutaatiolle on ja .

Esimerkki 4.1.5.

Muodostetaan joukon alkion (ks. esimerkki 4.1.2) käänteispermutaatio:

Opiskelutehtävä 35. (Permutaatioiden tulo ja käänteispermutaatiot)

Laske permutaatioille

tulot ja sekä käänteispermutaatiot ja .

Opiskelutehtävä 36. (Kolmen alkion permutaatioiden tulot)

Käyttäen esimerkin 4.1.2 merkintöjä määrää joukon alkioille permutaatiot , , , , , , ja . Selvitä kussakin tapauksessa, mikä joukon alkio tulee vastaukseksi. Vertaa myös eri tuloksia keskenään. Tunnistatko mitään sääntöjä?

Vinkki tehtävään 36

Lause 4.1.6.

Joukon kaikille alkioille , ja pätevät seuraavat:

(a)   ,

(b)   ,

(c)   , kun on identtinen kuvaus,

(d)   .

Todistus.

Kaikki kyseiset ominaisuudet seuraavat suoraan kuvausten ja bijektioiden ominaisuuksista.

Yllä olevassa lauseessa kohdan (b) ominaisuutta voi sanoa sulkujen poistoluvaksi, sillä sen mukaan tulo on riippumaton ryhmittelyjärjestyksestä eikä siinä siten tarvita sulkuja osoittamaan sitä. Kertomisjärjestyksellä on sen sijaan merkitystä.

Joukko varustettuna yllämainituilla alkioiden yhdistelyominaisuuksilla on taasen esimerkki eräästä yleisemmästä algebrallisesta struktuurista, nimittäin ryhmästä. Joukkoa sanotaankin astetta olevaksi symmetriseksi ryhmäksi. Symmetria-sanan esiintyminen nimessä selittyy myöhemmin luvussa Symmetria, kun tarkastelemme lähemmin tasokuvioiden ja avaruuskappaleiden symmetrisyyttä. Osoittautuu nimittäin, että näiden symmetrian kuvaamiseen voidaan käyttää ryhmiä .

Ryhmän alkioiden tulot ovat siis aina edelleen sen alkioita. Kun aste on pieni, voidaan kertomisen tulokset esittää kertolasku- eli operaatiotaulukon avulla. Seuraavissa esimerkeissä tämä tehdään, kun ja .

Esimerkki 4.1.7.

Merkitään ryhmän alkioita

jolloin on identtinen kuvaus ja . Näillä tiedoilla saadaan seuraava kertotaulukko:

Esimerkki 4.1.8.

Merkitään ryhmän alkioita esimerkin 4.1.2 mukaisesti

Esimerkissä 4.1.4 on laskettu, että ja . Kun lasketaan vastaavasti kaikki muut tulot, saadaan seuraava operaatiotaulukko:

Opiskelutehtävä 37. ((Kolmen alkion permutaatioiden kertotaulukko)

Tarkista ryhmän kertotaulukon jotkin kaksi riviä tai saraketta (mutta ei kahta ensimmäistä) oikeiksi.

Vinkki tehtävään 37

Renkaassa yhtälöä ei voitu aina ratkaista. Ryhmässä voidaan kuitenkin aina tämäntyyppiset yhtälöt ratkaista.

Lause 4.1.9.

Ryhmässä yhtälöllä on yksikäsitteinen ratkaisu . Vastaavasti yhtälöllä on yksikäsitteinen ratkaisu .

Todistus. Jos ja , on

ja

,

joten ne ovat väitettyjen yhtälöiden ratkaisuja. Se, että nämä ovat ainoat ratkaisut, nähdään taas heti, kun kerrotaan ratkaistavat yhtälöt alkiolla , edellinen vasemmalta ja jälkimmäinen oikealta.

Yhtälöiden ja ratkaiseminen tapahtuu siis kertomalla yhtälöt kertoimen käänteispermutaatiolla siltä samalta puolelta, jolla kerroin on ratkaistavan muuttujan suhteen.

Lause 4.1.10.

Ryhmässä pätee ns. supistamissääntö: jos , niin välttämättä , ja vastaavasti, jos , niin .

Todistus. Yhtälöstä seuraa edellisen lauseen perusteella, että

.

Vastaavasti ehdosta seuraa, että

.

Supistamissääntö on hyödyllistä muistaa silloin, kun laaditaan ryhmille kertolaskutaulukoita. Tämän säännön mukaan nimittäin tällaisessa taulukossa kukin ryhmän alkio esiintyy kullakin rivillä ja sarakkeella korkeintaan yhden kerran. Toisaalta paikkoja on yhtä monta kuin käytettäviä alkioita, joten itse asiassa kukin ryhmän alkio esiintyy kullakin rivillä ja sarakkeella täsmälleen kerran.

[Ylempi pääsivu] [Edellinen sivu] [Seuraava sivu]