Te tudtad, hogy 10 ember egymás mellé több, mint 3,6 millió féle különböző sorrendben ülhet le? Nem? Akkor maradj velem és ismerkedj meg a kombinálás tudományának alapjaival, ebben a cikkben a permutációval.
A kombinatorika esetszámlálással foglalkozik, például: hányféleképpen ülhet le egymás mellé 5 ember vagy hányféle módon választhatunk ki 3 ízt a 20 féle különböző ízesítésű fagylalt közül. Bár az egyes feladatokban a legtöbb esetben nem tisztán, önmagukban jelennek meg a most következő alapesetek, de ismeretük elengedhetetlen a gondolkodási módszer elsajátításában.
3 különböző esetet fogunk átnézni 3 leckén keresztül:
- Permutáció: az összes elemünket sorbarendezzük.
- Variáció: az összes elemünk közül néhányat kiválasztunk és őket sorba rendezzük. (lecke ITT)
- Kombináció: az összes elemünk közül néhányat kiválasztunk, de nem rendezzük sorba őket. (lecke ITT)
Permutáció
Ebben a leckében a permutációval fogunk foglalkozni, amikor az összes elemünket sorba rendezzük.
Ismétlés nélküli permutáció:
- Ez történik: minden “n” darab elemünk különböző és úgy rendezzük őket sorba.
- Képlet:
- Magyarázat: Az n! azt jelenti, hogy n-től kezdődően összeszorozzuk a tagokat egészen 1-ig. Tehát például: 4! = 4*3*2*1 = 24.
- Feladat: Egy 5 tagú baráti társaság 5 egymás mellé szóló jegyet vásárol a moziba. Hányféle különböző módon ülhetnek le egymás mellé?
- A feladat megoldása: érdemes végig menni az egyes helyen és megvizsgálni oda hányféle elem kerülhet. Az első helyre (mondjuk a bal szélére) még bárki leülhet ötük közül, viszont tőle jobbra már csak 4 valaki közül választhatunk, hiszen valaki már helyet foglalt a bal szélső széken. Még egyet jobbra haladva, már csak 3 fő jöhet szóba, mert ketten már leültek. Utána már csak 2 és végül a jobb szélére már csak 1 fő marad. Az eredmény: 5*4*3*2*1 = 5! = 120, azaz 120 féle különböző sorrendben ülhetnek le egymás mellé.
Ismétléses permutáció:
- Ez történik: az “n” darab összes elem között van k1, k2, …, kn darab alkalommal ismétlődő elem és úgy rendezzük őket sorba.
- Képlet:
- Magyarázat: Az összes (n darab) elem faktoriálisát vesszük és leosztjuk az ismétlődő elemek számának faktoriálisaiból képzett szorzattal.
- Feladat: Az A, A, A, B, B, C, C, C, C, D betűk vannak előttünk 1-1 kártyán és (nem feltétlen értelmes) 10 betűből álló szavakat alkotunk. Hányféle ilyen szó alkotható?
- A feladat megoldása: Hasonlóan az ültetéses feladathoz, itt is elkezdjük letenni a betűket. A feladat elején még nem foglalkozunk azzal, hogy vannak ismétlődő betűk, de észben tartjuk! A szó első betűjének helyére 10 féle kártyát tehetünk le, második helyére már csak 9 félét (hiszen a kezdőbetű kártyáját már letettük), a harmadik helyre már csak 8 félét (és így tovább), egészen egyig. Tehát: 10*9*8*7*(…)*1 = 10! Igen ám, de voltak ismétlődő betűk, amiket felcserélésével nem keletkeznek új szavak. Van 3 db „A” betű, 2 db „B” betű, 4 db „C” betű és 1 db „D” betű. Ezekből faktoriálisokat képzünk, összeszorozzuk őket és elosztjuk ezzel a taggal a 10!-t.:
