Permutaatio kombinatoriikassa on järjestetty joukko ilman lukujen toistoja , yleensä sitä käsitellään joukossa bijektiona , joka yhdistää luvun joukon -: nnen elementin kanssa. Lukua kutsutaan permutaation pituudeksi [1] .
Ryhmäteoriassa mielivaltaisen joukon permutaatio tarkoittaa tämän joukon bijektiota itseensä . Synonyyminä sanalle "permutaatio" tässä mielessä jotkut kirjoittajat käyttävät sanaa substituutio . (Toiset kirjoittajat kutsuvat substituutiota visuaalisena tapana kirjoittaa permutaatio. Merkittävämpi ero on, että substituutio on itse funktio, kun taas permutaatio on tulosta soveltamalla tätä funktiota sekvenssin elementteihin.)
Termi "permutaatio" syntyi, koska aluksi esineitä otettiin, järjestettiin jotenkin ja muut järjestystavat vaativat näiden objektien uudelleenjärjestelyä. [2] .
Permutaatio on joukko, joka koostuu samasta määrästä elementtejä, jotka eroavat vain elementtien järjestyksestä. [3]
Kaikkien elementtien permutaatioiden määrä on yhtä suuri kuin by:n sijoittelujen lukumäärä , eli tekijä [ 4 ] [5] [6] [7] :
.Koostumus määrittää tuotteen toiminnan samanpituisilla permutaatioilla: Tämän operaation suhteen elementtien permutaatioiden joukko muodostaa ryhmän , jota kutsutaan symmetriseksi ja jota yleensä merkitään .
Mikä tahansa äärellinen elementtiryhmä on isomorfinen jollekin symmetrisen ryhmän alaryhmälle ( Cayleyn lause ). Tässä tapauksessa jokainen elementti liittyy permutaatioon , jonka elementeille määrittää identiteetti missä on ryhmäoperaatio .
Permutaation kantoaalto on joukon osajoukko, jokamääritellään nimellä
Permutaation kiinteä piste on mikä tahansakuvauksen kiinteä piste, eli joukon elementti.Permutaation kaikkien kiinteiden pisteiden joukkoonsen kantajan komplementti .
Inversio permutaatiossaon mikä tahansa indeksien parisiten, ettäja. Permutaation inversioiden lukumäärän pariteetti määrittää permutaation pariteetin .
Joukon permutaatio voidaan kirjoittaa substituutioksi , esimerkiksi:
missä ja .
Mikä tahansa permutaatio voidaan hajottaa pituisten epäyhtenäisten syklien tuotteeksi ( koostumukseksi ) ja ainutlaatuisella tavalla tuotteen syklien järjestykseen asti. Esimerkiksi:
Usein oletetaan myös, että permutaation kiinteät pisteet ovat itsenäisiä syklejä, joiden pituus on 1, ja ne täydentävät niillä permutaation syklilaajennusta. Yllä olevassa esimerkissä tällainen lisätty hajotus olisi . Eripituisten jaksojen lukumäärä, nimittäin lukujoukko , jossa on pituisten jaksojen lukumäärä , määrittää permutaation syklisen rakenteen . Tässä tapauksessa arvo on yhtä suuri kuin permutaation pituus ja arvo on yhtä suuri kuin jaksojen kokonaismäärä. Elementtien permutaatioiden lukumäärä jaksoilla saadaan ensimmäisen tyypin etumerkittömällä Stirling-luvulla .
Mikä tahansa sykli voidaan hajottaa (ei välttämättä hajautettujen) transpositioiden tuloksi . Tässä tapauksessa sykli, jonka pituus on 1 (joka on olennaisesti identtinen permutaatio ) voidaan esittää transpositioiden tyhjänä tulona tai esimerkiksi minkä tahansa transponoinnin neliönä: Pituusjakso voidaan hajottaa transponoinnin tulos seuraavasti:
On huomattava, että syklien hajoaminen transpositioiden tuloksi ei ole ainutlaatuinen:
Siten mikä tahansa permutaatio voidaan hajottaa transpositioiden tuloksi. Vaikka tämä voidaan tehdä monella tavalla, transponointien lukumäärän pariteetti on sama kaikissa tällaisissa hajotteluissa. Tämä mahdollistaa permutaation etumerkin ( permutaatiopariteetti tai permutaatioallekirjoitus ) määrittämisen seuraavasti:
missä on transponointien määrä jossain laajennuksessa . Tässä tapauksessa he kutsuvat parillista permutaatiota if , ja paritonta permutaatiota jos .
Vastaavasti permutaation etumerkki määräytyy sen syklin rakenteesta: jaksoista koostuvan elementtien permutaation etumerkki on yhtä suuri kuin
.Permutaation etumerkki voidaan määrittää myös inversioiden lukumäärällä :
.Harkitse erityyppisiä elementtejä , ja jokaisessa tyypissä kaikki elementit ovat samoja. Sitten kaikkien näiden elementtien permutaatioita samantyyppisten elementtien järjestykseen asti kutsutaan permutaatioiksi toistolla . Jos on th-tyypin elementtien lukumäärä, niin mahdollisten permutaatioiden määrä toistoilla on yhtä suuri kuin moninomikerroin
Permutaatiota, jossa on toistoja, voidaan pitää myös kardinaalisuuden monijoukkopermutaationa .
Satunnaispermutaatio on satunnaisvektori, jonka kaikki elementit saavat luonnolliset arvot 1:stä ja minkä tahansa kahden elementin yhteensopivuuden todennäköisyys on 0.
Itsenäinen satunnaispermutaatio on sellainen satunnainen permutaatio , jolle:
joillekin sellaisille:
Jos samaan aikaan eivät riipu , niin permutaatiota kutsutaan tasajakaiseksi . Jos ei ole riippuvuutta , eli sitä kutsutaan homogeeniseksi .