Permutáció: ismétléses és ismétlés nélküli, feladatokkal

A kombinatorika egyik legtöbbet emlegetett fogalma a permutáció. De mit is jelent pontosan az ismétlés nélküli és az ismétléses permutáció? Milyen feladatokat lehet megoldani a segítségükkel? Az alábbiakban mindegyik kérdésre megadjuk a választ!

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

Egy adott n elemű halmaz elemeinek egy ismétlés nélküli permutációjának nevezzük az n különböző elem egy sorba rendezését. Jelölése: P_{n}.

A fogalom megismerése után a következő lépés az, hogy megtudjuk, hogyan kell kiszámolni n elem összes ismétlés nélküli permutációját. Nézzük is meg:

Egy n elemű halmaz összes ismétlés nélküli permutációinak száma n faktoriális, azaz:

P_{n} = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot 2 \cdot 1 = n!

Most pedig nézzünk meg néhány ide kapcsolódó feladatot!

Ismétlés nélküli permutációval megoldható feladatok

Feladat: Hányféle sorrendben ülhet le egymás mellé 6 ember?

Segítség: Arra vagyunk kíváncsiak, hogy összesen hányféleképpen lehet sorba rendezni 6 embert. Azaz 6 elem ismétlés nélküli kombinációinak a számát keressük.

Megoldás: Tudjuk tehát, hogy n=6, innen a képletbe helyettesítve:

 P_{6} = 6! = 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 720.

Azaz 720 féleképpen tud leülni egymás mellé 6 ember.

Feladat: Egy fagyizóban 3 gombócot szeretnénk a tölcsérünkbe választani: csokoládét, vaníliát és puncsot. Hányféle sorrendben kérhetjük a gombócokat?

Segítség: A tölcsérben alul 3-féle, középen 2-féle, felül 1-féle gombóc lehet, mivel minden gombócot csak egyszer tehetünk a tölcsérbe. Vagyis a feladatban 3 elem ismétlés nélküli permutációinak számát keressük.

Megoldás: Vagyis a feladatban n = 3, így P_{3}-at keressük. Így a megoldás:

P_{3} = 3! = 3 \cdot 2 \cdot 1 = 6

Azaz hatféleképpen kérhetjük a fagyinkat.

Most pedig térjünk át az ismétléses permutációra és nézzük meg miben is tér el az ismétlés nélkülitől.

Ismétléses permutáció

Ha az n elem között van k_{1}, k_{2},\ldots, k_{m} egymással megegyező elem, akkor az elemek egy sorba rendezését ismétléses permutációnak nevezzük. Jelölése: P_{n}^{(k_{1}, k_{2}, \ldots, k_{m})}.

Tehát a különbség a következő: ismétlés nélküli permutáció esetén csupa különböző elemet rendezünk sorba, még ismétléses permutáció esetén vannak megegyező elemek.

Nézzük most itt is meg, hogyan kell kiszámolni az összes lehetséges ismétléses permutációt!

Ha egy n elemű halmazban az n elem között k_{1}, k_{2}, \ldots, k_{m} egymással megegyező elem van, és k_{1} + k_{2} + \ldots + k_{m} = n, akkor ezeket az elemeket

P_{n}^{(k_{1}, k_{2}, \ldots, k_{m})} = \frac{n!}{k_{1}! \cdot k_{2}! \cdot \ldots \cdot k_{m}!}

különböző módon lehet sorba rendezni. Ez a halmaz összes ismétléses permutációjának száma.

Folytassuk itt is a feladatokkal!

Ismétléses permutációval megoldható feladatok

Feladat: Hányféleképpen tudunk sorba rendezni 4 kék és 3 sárga golyót?

Segítség: Sorba rendezésről van szó, tehát tudjuk, hogy permutáció lesz a segítségünkre a megoldás során. Továbbá azt is látjuk, hogy vannak ugyanolyan elemek (sárga és kék golyók), tehát ismétléses permutációt kell használnunk.

Megoldás: A feladatban 7 golyó szerepel, vagyis n = 7. Ezek között viszont 4 és 3 ugyanolyan színű van, vagyis k_{1}=4, k_{2} = 3. Tehát a P_{7}^{(4,3)}-at keressük. Így a megoldás a képletbe behelyettesítés segítségével:

P_{7}^{(4,3)} = \frac{7!}{4! \cdot 3!} = \frac{7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(4 \cdot 3 \cdot 2 \cdot 1) \cdot (3 \cdot 2 \cdot 1)} = 7 \cdot 5 = 35

Azaz 35 féleképpen tudjuk sorba rendezni a golyókat.

A következő feladat elolvasása előtt pedig próbáld megoldani magadtól a feladatot. A megszokott segítséget a segítség fülön találod, a megoldást pedig a megoldáson.

Egy fagyizóban 5 gombócot szeretnénk a tölcsérünkbe választani: 2 csokoládét, 2 vaníliát és 1 puncsot. Hányféle sorrendben kérhetjük a gombócokat?

Sorba rendezésről van szó, tehát tudjuk, hogy permutáció lesz a segítségünkre a megoldás során. Továbbá azt is látjuk, hogy vannak ugyanolyan elemek (csokoládé és vanília gombócok), tehát ismétléses permutációt kell használnunk.

A feladatban 5 gombócot választunk, tehát n = 5. Ezekből viszont 2-2 ugyanolyan ízűt (csoki, vanília) szeretnénk választani, vagyis k_{1} = 2, k_{2} = 2, így P_{5}^{(2,2)}-at keressük. A megoldás tehát a képletbe behelyettesítés segítségével:

P_{5}^{(2,2)} = \frac{5!}{2! \cdot 2!} = \frac{5 \cdot 4 \cdot 3 \cdot 2 \cdot 1}{(2 \cdot 1) \cdot (2 \cdot 1)} = 5 \cdot  3 \cdot 2 = 30.