permutaatioista

Permutaatiot käsittelevät järjestyksiä. Permutaatio on matematiikassa bijektio, joka kartoittaa joukon itseensä ja siirtää alkiot uuteen järjestykseen. Kun tarkastelemme n erilaista alkiota, kaikkien permutaatiot muodostavat ryhmän, jota kutsutaan symmetriseksi ryhmäksi ja merkitään S_n. Ryhmän koko on n!, eli kaikki mahdolliset järjestykset voidaan luetella.

Esitystavat ovat keskeisiä. Yksinkertaisinta on määrittää kullekin alkiolle sen kuvaus: pi(1), pi(2), ..., pi(n). Esimerkki: joukko {1,2,3,4} ja permutaatio pi, jossa pi(1)=2, pi(2)=3, pi(3)=1, pi(4)=4. Tämä vastaa kiertoa (1 2 3) ja kiertoa (4). Kiertoja voidaan esittää myös erillisinä kiertojen tulona, ja tavallisesti käytetään kiertomerkintää (1 2 3)(4 5) kuvaamaan disjoint cycles -rakennetta.

Kiertojen purkaminen ja transpositiot. Jokainen permutaatio voidaan kirjoittaa kiertojen tulona, ja nämä kiertot voidaan koostaa transpositioista (kaksi alkiota vaihtava rakennuspalikka). Siitä seuraa pariteetti: permutaation pariteetti määritellään sen mukaan, voiko sen esittää parillisella vai parittomalla määrällä transpositioita. Parilliset permutaatiot ovat sijoitettavissa parillisella määrällä transpositioita, parittomat parittomalla määrällä.

Sovellukset ja teoreettinen tausta. Permutaatiot ovat keskeisiä kombinaatiossa, algoritmeissa ja algebrassa. Cayleyn teoreema osoittaa, että jokainen ryhmä voidaan toteuttaa tavallisena ryhmänä jonkin S_n:n aliryhmänä. Permutaatioryhmien ominaisuudet sekä derangement-teoriat antavat työkalut sekä teoreettisiin että soveltaviin ongelmiin.