Permutáció

A Wikipédiából, a szabad lexikonból.

Tartalomjegyzék 1 Definíció 1.1 Elemi definíció 1.2 Halmazelméleti definíció 2 Permutációk típusai 2.1 Ismétlés nélküli permutáció 2.1.1 Példa 2.2 Ismétléses permutáció 2.2.1 Példa 3 Fontosabb permutációelméleti fogalmak 4 Permutációcsoportok 5 Hivatkozások 5.1 Szakirodalom 5.2 Kapcsolódó cikkek

[szerkesztés] Definíció

[szerkesztés] Elemi definíció

Definíció

A kombinatorikában n elem egy permutációján az n darab elem egy meghatározott sorrendjét értjük.

Legyen az n darab elem a következő A halmaz eleme: A:={a₁, a₂, ..., a_n}. Matematikailag legtermészetesebben úgy definiálható ekkor az A egy permutációja egy f:{1,2,...,n}→A kölcsönösen egyértelmű függvény (minden számhoz 1-től n-ig az A egy és csak egy elemét rendeljük, azaz „sorba rendezzük”).

Egy permutációt úgy adhatunk meg, hogy zárójelben (általában vesszővel) felsoroljuk az elemeit, vagy pl. n=5 esetén az f(1)=a₅, f(2)=a₂, f(3)=a₁, f(4)=a₃, f(5)=a₄ permutációt a következő rövidebb alakokban adhatjuk meg:

még rövidebb, ha a második sorban csak az elemek indexeit írjuk ki (mintha azonosítanánk A-t az {1,2,...,n} halmazzal):

[szerkesztés] Halmazelméleti definíció

A felsőbb matematikában - pontosabban és az elemi definíciónál kicsit általánosabban is - a következő definíciót adhatjuk: adott egy A (nem feltétlenül véges) halmaz, ennek egy permutációja valamely, önmagára való bijektív leképezése. Tehát egy f: A→A alakú bijektív függvény az A egy permutációja. Ezeknek (ti. az A összes permutációja halmazának) különféle osztályfelbontásainak tagjait is különféle „permutációknak” nevezzük (ismétléses permutációk, ciklikus permutációk), bár ezek „igazából” nem permutációk, hanem permutációosztályok.

[szerkesztés] Permutációk típusai

[szerkesztés] Ismétlés nélküli permutáció

Definíció

n különböző elem esetén, n egy permutációját, n elem ismétlés nélküli permutációjának nevezzük. Jele: P_n

Tétel

n elem ismétlés nélküli permutációinak száma megegyezik az első n természetes szám szorzatával: P_n = n!

A bizonyításhoz teljes indukciót fogunk alkalmazni, és felhasználjuk a faktoriális definícióját.

Először vizsgáljuk meg n = 1 esetet

Egy elemet egyféleképpen rendezhetünk sorba. Ez alapján P₁ = 1 = 1!, így erre az esetre a tétel teljesül.

Az indukciós feltétel n = k elem esetén

k elem ismétlés nélküli permutációinak száma megegyezik az első k természetes szám szorzatával: P_k = k!

Most pedig lássuk be a tétel helyességét az n = k + 1 esetre, az indukciós feltétel felhasználásával.

Vizsgáljuk meg, hány új permutáció keletkezik egy új elem felvételekor. Minden eddigi permutációhoz (k elem) hozzáadhatjuk az új elemet az első, második, , k-adik, és k + 1-edik tagként, tehát a permutációk száma k + 1 szeresére változik: P_{k + 1} = P_k(k + 1)

Az indukciós feltétel alapján P_{k + 1} = k!(k + 1) = (k + 1)!. Ezt kellett belátnunk. ■

[szerkesztés] Példa

(1,2,3,4) (2,1,3,4) (3,1,2,4) (4,1,2,3) (1,2,4,3) (2,1,4,3) (3,1,4,2) (4,1,3,2) (1,3,2,4) (2,3,1,4) (3,2,1,4) (4,2,1,3) (1,3,4,2) (2,3,4,1) (3,2,4,1) (4,2,3,1) (1,4,2,3) (2,4,1,3) (3,4,1,2) (4,3,1,2) (1,4,3,2) (2,4,3,1) (3,4,2,1) (4,3,2,1)

Az 1,2,3,4 elemek összes permutációja

(negyedrendű permutációk)

Az 1,2,3,4 számokból hány négyjegyű szám alkotható, ha minden számjegyet csak egyszer használhatunk fel?

Mivel a számok között nincsen megegyező elem, ezért a válasz az 1,2,3,4 elemek ismétlés nélküli permutációinak száma, vagyis P₄ = 4! = 24

[szerkesztés] Ismétléses permutáció

Definíció

Ha n elem között találunk egymással megegyezőt, akkor n elem egy permutációját, n elem ismétléses permutációjának nevezzük. Jele: .

Tétel

n elem ismétléses permutációinak száma , ha egymással megegyező elemekből darab van. A bizonyításhoz az ismétlés nélküli permutáció képletét fogjuk felhasználni.

Lássuk el különböző indexszel az ismétlődő elemeket, hogy felhasználhassuk az ismétlés nélküli permutációk számának meghatározására vonatkozó képletet: , , , . Így megkaptuk az olyan permutációk számát, amelyek megegyeznek egymással (hiszen az indexszel ellátott tagok valójában megegyezők), tehát ezen értékek a szorzatával le kell osztanunk a permutációk számát. Ezt kellett belátnunk. ■

[szerkesztés] Példa

Az 1,2,2,3,3 számokból hány ötjegyű szám alkotható, ha minden számjegyet csak egyszer használhatunk fel?

Mivel a számok között van megegyező elem, ezért a választ a következő képlet adja meg:

Tehát a feladat megoldása: 30

[szerkesztés] Fontosabb permutációelméleti fogalmak

• inverziószám: Adott n különböző elem. Vegyük egy permutációját ennek az n elemnek és legyen ez a természetes sorrend. Ha vizsgáluk egy permutációban két elemet, meg tudjuk mondani, hogy melyik elem áll előrébb. Nevezzük ezt a két elem viszonyának. A két elem inverzióban áll, ha a vizsgált permutációban és a természetes sorrendben különbözik a viszonyuk. Az inverzióban álló elempárok száma az inverziószám.
• Permutációk paritása megegyezik az inverziószám paritásával (tehát, ha egy permutációban páros sok inverzió van, a permutációt párosnak nevezzük, ellenkező esetben páratlannak).
• Permutációs rejtjel: A permutációs kód vagy permutációs rejtjel a klasszikus titkosírás egyik rejtjelezési eljárása.

[szerkesztés] Permutációcsoportok

[szerkesztés] Hivatkozások

[szerkesztés] Szakirodalom

Solt György, Valószínűségszámítás, Műszaki könyvkiadó, Bolyai könyvek, Bp. 1993

[szerkesztés] Kapcsolódó cikkek

• kombinatorika
• elemi kombinatorika
• variáció
• kombináció
• fixpontmentes permutáció
• ismétléses permutáció
• ciklikus permutáció