Permutációk száma

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 az 5. Ezek sorbarendezésével hány darab háromjegyű szám készíthető? A válasz könnyű, hiszen könnyen 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 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.

1. hely	2. hely	3. hely	….	(n-1). hely	n. hely
n lehetőség	(n-1) lehetőség	(n-2) lehetőség	….	2 lehetőség	1 lehetőség

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: P_n=n⋅(n-1)⋅(n-2)⋅…⋅3⋅2⋅1.  
P_n értékét tehát megkapjuk, ha 1-től n-ig összeszorozzuk az egész számokat.

Bizonyítás: teljes indukcióval.

1. 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.
2. Feltételezzük, hogy n darab különböző tárgyra igaz, tehát:
P_n=n⋅(n-1)⋅(n-2)⋅…⋅3⋅2⋅1.  
3. 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.
P_n=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énybe maradása érdekében 0!=1 megállapodást is célszerű megtenni.

Feladat:

Hány 6-tal osztható hatjegyű szám képezhető a 0, 1, 2, 3, 4, 5 számjegyekből, ha a számjegyek között nem engedjük meg az ismétlődést? 

(Összefoglaló feladatgyűjtemény 4035. feladat.)

Megoldás:

Hat darab számjegyből csak úgy készíthetünk ismétlődés nélküli hatjegyű számot, ha minden számjegyet felhasználunk és minden számjegyet csak egyszer.
Egy szám 6-tal osztható, ha 3-mal és 2-vel is osztható. Mivel 0+1+2+3+4+5=15, ezért ezekből a számjegyekből álló hatjegyű szám biztosan osztható lesz 3-mal.
2-vel osztható számot akkor kapunk a feladatban megadott számjegyekkel, ha a szám 0-ra, 2-re vagy 4-re végződik. Így tehát három, egymástól független lehetőségünk van:

I. A 0, 1, 2, 3, 4, 5 számjegyekből 0-ra végződő 6 különböző számjegyből álló szám annyi van, ahányféleképpen a 1, 2, 3, 4, 5 számjegyeket sorba lehet rakni. Ez öt elem permutációinak a számával egyenlő, azaz: P₅=5!=1⋅2⋅3⋅4⋅5=120 lehetőség. Ez azt jelenti, hogy a 0, 1, 2, 3, 4, 5 számjegyekből 0-ra végződő 6 különböző számjegyből álló szám 120 darab van.
II. A 0, 1, 2, 3, 4, 5 számjegyekből 2-re végződő 6 különböző számjegyből álló szám annyi van, ahányféleképpen a 0, 1, 3, 4, 5 számjegyeket sorba lehet rakni, úgy hogy a 0 számjegy nem lehet az első, mert nullával nem kezdődik hatjegyű szám.
Ezért az első helyre 4 lehetőségünk van, hiszen a 0-t nem választhatjuk. A második helyre ismét négy lehetőségünk van, hiszen azt ugyan nem választhatjuk, amit már az első helyre letettünk, de a nullát már választhatjuk. A harmadik helyre 3, a negyedik helyre 2, az ötödik helyre pedig már csak egy lehetőségünk van.
Így a 0, 1, 2, 3, 4, 5 számjegyekből 2-re végződő 6 különböző számjegyből álló szám darabszáma: 4⋅4!=4⋅24=96.
III. A 0, 1, 2, 3, 4, 5 számjegyekből 4-re végződő 6 különböző számjegyből álló szám ugyanannyi van, mint amennyi a fenti esetben a 2-re végződő, azaz 96.

A feladat megoldása tehát:

5!+4⋅4!+4⋅4!=120+96+96=312.

312 darab hatjegyű szám készíthető a 0, 1, 2, 3, 4, 5 számjegyekből, ha a számjegyek között nem engedjük meg az ismétlődést.