Permutaatio

Wikipediasta

Matematiikassapermutaatioilla tarkoitetaanalkioiden järjestystä. Esimerkiksi järjestetynjoukon {1,2,3,4} yksi permutaatio on (1,3,2,4) ja toinen esimerkiksi (2,1,4,3). Permutaatioiden lukumäärä n-alkioisessa järjestetyssä joukossa on n:nkertoma $n! {\displaystyle n!}$ .^[1] Tämä nähdään seuraavasti:

Oletetaan että joukossa on $n {\displaystyle n}$ kappaletta alkioita. Otetaan ensimmäinen paikka jonosta: tähän voidaan asettaa mikä tahansa alkio alkuperäisestä joukosta. Jonon seuraavaan paikkaan voi asettaa minkä tahansa jäljelle jääneistä $n-1$ :stä alkiosta. Tätä alkioiden asettelua jatketaan kunnes kaikki alkiot on käyty läpi. Tuloksena kaikkien mahdollisten jonojen lukumäärälle saadaan $n\times (n-1)\times \ldots \times 2\times 1=n!$

Jos järjestettävissä alkioissa on samoja alkioita, esimerkiksi (1,1,2,4) permutaatioiden lukumäärässä samat alkiot luetaan eriäviksi. Näin ollen kertoma $4!$ sisältää esimerkiksi järjestyksen (1,2,1,4) kaksi kertaa, sillä 1-alkioiden paikat voidaan vaihtaa keskenään. Siten voidaan myös sanoa, että permutaatio äärellisestä joukosta $X {\displaystyle X}$ onbijektio itseensä.

Voidaan myös järjestää tietyn kokoisia osajoukkoja. Esimerkiksi jos järjestettävänä ovat kirjaimet a, b ja c, niin meillä on 3! eli kuusi järjestystä: abc, acb, bac, bca, cab, cba. Jos kuitenkin haluamme järjestää niistä vain kaksi kirjainta kerrallaan, niin meillä on seuraavat kuusi järjestystä: ab, ba, ac, ca, bc, cb. Yleisemmin jos meillä on $n {\displaystyle n}$ eri alkiota ja $k {\displaystyle k}$ on kokonaisluku $1\leq k\leq n$ , niin $k {\displaystyle k}$ :n mittaisten osajonojen elivariaatioiden lukumäärä on:^[2]

P(n,k)={\frac {n!}{(n-k)!}}

Tätä kutsutaan myös toisinaan k-permutaatioksi.

Kun halutaan tietää, kuinka monta erilaista pienempijäsenistä osajoukkoa joukosta alkioita voidaan muodostaa puhutaankombinaatioista.

Esimerkki

[muokkaa |muokkaa wikitekstiä]

Kun n erilaisesta helmestä muodostetaan helminauha, niin helmet voidaan asettaa n! erilaiseen järjestykseen. Helminauhassa on kuitenkin sama, mistä helmestä tarkastelu aloitetaan, joten em. kertoma tulee jakaa helminauhan "jaksolla" n. Helminauha on myös sama, jos se käännetään ympäri. Tämä seikka johtaa vielä kahdella jakamiseen, joten erilaisten helminauhojen lukumäärä on

{n! \over n\cdot 2}={(n-1)! \over 2},n>2

Esimerkiksi neljästä helmestä saadaan kolme erilaista nauhaa:

1 – 2 1 – 2 1 – 3

| | | | | |

4 – 3 3 – 4 4 – 2

Historia

[muokkaa |muokkaa wikitekstiä]

Ensimmäinen maininta permutaatiosta on tuntemattoman mystikon joskus vuosien 200 ja 600 jaa. välillä kirjoittamassa hebreankielisessäSefer Yetzirah -teoksessa. Tosin jo aikaisemmin kreikkalaisen filosofinKsenokrateen on sanottu yrittäneen laskea permutaatioita. Ensimmäinen länsimainen oppikirjamainen esitys onJakob BernoullinArs Conjectandi vuodelta 1713.^[2]

Katso myös

[muokkaa |muokkaa wikitekstiä]

Levi-Civita-symboli

Lähteet

[muokkaa |muokkaa wikitekstiä]

↑Häsä, Jokke & Rämö, Johanna: Johdatus abstraktiin algebraan, s. 64. Helsinki: Gaudeamus, 2015. ISBN 978-952-495-361-0
↑^a ^bGrimaldi, Ralph P.: Discrete and Combinatorial Mathematics: an Applied Introduction, s. 7,42. (4. painos) Addison Wesley, 1999. ISBN 0-201-19912-2 (englanniksi)

Tämämatematiikkaan liittyvä artikkeli ontynkä. Voit auttaa Wikipediaalaajentamalla artikkelia.

Noudettu kohteesta ”https://fi.wikipedia.org/w/index.php?title=Permutaatio&oldid=22802729”

Luokat:

Piilotetut luokat:

ページ先頭