Permutációk száma (A szám permutációja)

A permutáció alapjai

Gyakori probléma lehet, hogy hányféleképpen tudunk embereket, tárgyakat, objektumokat sorbarendezni.

Például: adott három számjegy (számkártya): 2, 3, és 5. Ezek sorbarendezésével hány darab háromjegyű szám készíthető? A válasz könnyen meghatározható, hiszen előállítható a 6 darab szám: 235, 253, 325, 352, 523, 532.

Hasonlóan: Az „A", a „B", és a „C" betűket hányféleképpen lehet sorba rakni? Válasz: ABC; ACB; BAC; BCA; CAB; CBA

Definíció: Adott számú elem valamely sorrendjét (elrendezését) az adott elemek egy permutációjának nevezzük. (Permutáció: elrendezés.) Permutálás: maga a tevékenység, a sorbarendezés. Permutációk száma: a lehetséges elrendezések száma.

A permutációk matematikája

A feladatot általánosan megfogalmazva: Adott „n" db különböző tárgy. Hányféleképpen rakható sorba, azaz mennyi a permutációinak a száma?

Próbáljunk meg egy kis modellel szemléltetni! Képzeljünk el egy „n" rekeszes dobozt.

Az első helyre az n elem bármelyike választható, tehát erre a helyre n lehetőségünk van. A második helyre már csak (n-1) elem közül választhatunk, mert az első rekeszbe már egy tárgyat elhelyeztünk. Így tehát a 2. helyre (n-1) lehetőségünk van. És így tovább. Az utolsó előtti rekesznél már csak két tárgyunk van, így ebbe a rekeszbe 2 lehetőség közül választhatunk. Az utolsó rekeszbe már csak 1 lehetőségünk marad.

Tétel: „n" különböző elem összes permutációjának a száma: Pn=n⋅(n-1)⋅(n-2)⋅...⋅3⋅2⋅1. Pn értékét tehát megkapjuk, ha 1-től n-ig összeszorozzuk az egész számokat.

Bizonyítás: teljes indukcióval.

n=1, n=2; n=3 esetén az összefüggés igaz. Egy tárgyat csak egy féleképpen lehet sorba rakni, 2 tárgyat 1⋅2=2, míg 3 tárgyat 1⋅2⋅3=6 féleképpen.

Feltételezzük, hogy n darab különböző tárgyra igaz, tehát: Pn=n⋅(n-1)⋅(n-2)⋅...⋅3⋅2⋅1.

Belátjuk (n+1)-re. (n+1) különböző tárgy esetén az első helyre (n+1) lehetőségünk van. Bármelyiket is választjuk, marad n darab különböző tárgy. Ezeket az indukciós feltevés miatt n(n-1)(n-2)...3⋅2⋅1 féleképpen lehet sorba rakni, azaz az (n+1) tárgyat (n+1)⋅n⋅(n-1)⋅(n-2)⋅...⋅3⋅2⋅1 féleképpen lehet elrendezni.

Faktoriális jelölés és tulajdonságok

Pn=n⋅(n-1)⋅(n-2)⋅...⋅3⋅2⋅1 olyan gyakori matematikai művelet, hogy külön nevet és jelölést is kapott.

Definíció: Az első n pozitív egész szám szorzatát n faktoriálisnak nevezzük. Jelölése: n!. n!=n⋅(n-1)⋅(n-2)⋅...⋅3⋅2⋅1.

2!=1⋅2=2.

3!=1⋅2⋅3=6. Mint láttuk is, 3 különböző tárgyat 6 féleképpen lehet sorba rakni.

10!=1⋅2⋅3⋅4⋅5⋅6⋅7⋅8⋅9⋅10=3.628.800. Tehát 10 különböző tárgynak ilyen sok elrendezése lehetséges.

A definícióból következik, hogy n!=(n-1)!⋅n. Megállapodás szerint 1!=1. Az n!=(n-1)!⋅n elv érvényben maradása érdekében célszerű a 0!=1 megállapodást is megtenni.

Gyakorlati alkalmazások

Valós életbeli példák:

• Ütemezés és logisztika: Repülőtéri kifutópályák használati sorrendjének meghatározása, vagy gyártási sorrend optimalizálása a termelésben

• Kriptográfia: Permutációk alapvető szerepet játszanak a modern titkosítási eljárásokban, ahol az adatok átrendezése növeli a biztonságot

• DNS-szekvenciálás: A molekuláris biológiában a DNS-szekvenciák lehetséges elrendezéseinek vizsgálatánál

• Kémiai kötések: Molekulák lehetséges szerkezeteinek meghatározásához

Történeti háttér: A permutációk elméletének korai gyökerei az ókori Indiába nyúlnak vissza. A permutációk rendszerezett vizsgálata azonban a 17-18. században kezdődött Leibniz és később Euler munkásságával. A faktoriális jelölést (n!) Christian Kramp vezette be 1808-ban.

Miért fontos ezt megtanulni?

A permutációk megértése kritikus gondolkodási készségeket fejleszt és segíti a rendszerezőképességet. Amikor a számítógéped jelszavat kér, a mobilod záróképernyőjét állítod be, vagy egy társasjátékban stratégiát tervezel, valójában permutációkkal dolgozol. A kombinatorika alapfogalmaként a permutációk megértése kaput nyit számos további területhez: valószínűségszámítás, statisztika, operációkutatás, és algoritmusok tervezése.

Kapcsolódás más tudományterületekhez:

• Számítástechnika: Algoritmusok hatékonyságának elemzése, keresési és rendezési problémák

• Genetika: Kromoszómák lehetséges elrendeződéseinek tanulmányozása

• Kvantummechanika: Részecskék lehetséges állapotainak leírása

• Közgazdaságtan: Erőforrások optimális elosztásának modellezése

• Mesterséges intelligencia: Gépi tanulási modellek és neurális hálózatok struktúrájának meghatározása