Ismétlés nélküli permutáció
Hányféleképpen rendezehtünk sorba $n$ különböző elemet? Jele: $P_n$.
$$\boxed{P_n=n!}$$
Példa: úszóverseny döntőjében $n=8$ versenyző áll rajthoz. Hányféle sorrend alakulhat ki (ha nincs holtverseny, és nem zárnak ki senkit)?
$$P_n=n!=8!=40\ 320$$
Magyarázat: Az 1. helyre bármelyik úszót választhatjuk, így oda $n$ közül választhatunk. A 2. helyre ezután már csak $n-1$ úszó közül választhatunk, hisz egy úszót már "elhasználtunk" (rögzítettünk) az 1. helyre. Ugyanígy a 3. helyre már csak $n-2$ úszó közül választhatunk stb. Az eredmény: $P_n=n\cdot (n-1) \cdot (n-2) \cdot \ ... \ \cdot 1=n!$.
Isméléses permutáció
Hányféleképpen rendezhetünk sorba $n$ elemet, ha nem mind különbözőek, hanem vannak köztük egyformák is, és az egyformák darabszámai $k_1,\ k_2,\ ... \ k_m$. Jele: $P^{k_1,\ k_2,... k_m}_n$? Jele: $P^{k_1,\ k_2,... k_m}_n$
$$\boxed{P^{k_1,\ k_2,... k_m}_n=\frac{n!}{k_1! \cdot k_2! \cdot \cdot \cdot k_m!}}$$
Példa: a Forma-1 futamokon 10 istálló mindegyike 2-2 autót indít, így $n=20$ és $k_1=k_2=...=k_{10}=2$. Hányféle sorrend alakulhat ki, ha a végeredményt nem a pilóták, hanem az istállók szerint nézzük?
$$P^{k_1,\ k_2,... k_m}_n=\frac{n!}{k_! \cdot k_2! \cdot \cdot \cdot k_m!}=\frac{20!}{2!^{10}}=\frac{2\ 432\ 902\ 008\ 176\ 640\ 000}{1024}=2\ 375\ 880\ 867\ 360\ 000$$
Magyarázat: Van 2 Ferrarink, 2 Mercedes-ünk, 2 McLaren-ünk stb. Az összeset (első lépésben különfélének tekintve) $n!$ módon rendezhetjük sorba. De ilyenkor még külön esetnek vettünk két olyan esetet, amik csak abban tértek el,hogy a két Ferrari ugyanazokra a helyekre került, csak egymással "felcserélve", ezért "túlszámoltuk magunkat". Úgyhogy még el kell osztani az eredményt annyival, ahányféleképpen ezek az azonos elemek (Ferrarik) egymással sorbarendezhetők, márpedig $k_1$ elem $k_1!$ módon rendezhető sorba. Ugyanez a probléma a 2 Mercedes-szel is fennáll, így azzal is osztanunk kell, ahányféleképpen őket sorba lehet rendezni egymással (2!), hisz azok sem jelentenek külön esetet számunkra. Ugyanígy mindegyik csoporttal el kell ugyanezt végeznünk (a csoport létszámának faktoriálisával osztani kell).
Az alábbi kép egy ilyen Forma-1 futam 20 elemű sorrendjének első 10 helyezését mutatja:
Megjegyzés: Az azonos elemek $k_1,\ k_2,\ ... \ k_m$ darabszámai öszeadva nem lehet több, mint az $n$ összes elem száma: $k_1+k_2+\ ... \ k_m \le n$.
Ismélés nélküli variáció
Hányféleképpen választhatunk ki $n$ különböző elemből $k$ elemet úgy, hogy mindegyiket csak egyszer használhatjuk fel, és számít a kiválasztás sorrendje? Jele: $V_n^k$.
$$\boxed{V_n^k=\frac{n!}{(n-k)!}}$$
Példa: Az úszóverseny döntőjében $n=8$ úszó áll rajthoz. Hányféleképpen alakulhat, hogy ki melyik érmet kapja? (Nemcsak az számít, hogy ki az a három úszó, aki kap érmet, hanem az is, hogy egy kiválasztott aranyat, ezüstöt vagy bronzot, tehát a kiválasztásuk sorrendje is.)
$$V_n^k=\frac{n!}{(n-k)!}=\frac{8!}{(8-3)!}=\frac{40\ 320}{120}=336$$
Magyarázat: Képzeljük el az összes lehetséges végeredményt, de ne csak az érmet kapottak helyezéseit nézzük, hanem az összes résztvevő sorrendjét! Az összes $n$ elemet $n!$ módon rendezhetjük sorba. Így azonban egy konkrét éremkiosztás esetén még csomó külön esetként jelennek meg azok, amikor csak az "éremnélküli" helyezések térnek el, pedig számunkra ezek nem külön esetek (hisz csak az érmesek kiosztása fontos nekünk). Így ezt még el kell osztani annyival, ahányféleképpen az érmet nem kapók sorba rendezhetőek, márpedig az ő számuk $(n-k)$, így ők $(n-k)!$ módon rendezhetők sorba. Ez mindegyik éremkiosztásnál így van, így az összes $n!$ esetet el kell osztani ezzel az $(n-k)!$ tényezővel.
Megjegyzések: Ismétlés nélküli variációnál legfeljebb annyi $k$ elemet választhatunk ki, ahány $n$ elem összesen van, így ilyenkor muszáj, hogy $k\le n$ legyen. A variáció és kombináció fogalmakat úgy memorizálhatjuk, hogy variációnál számít a kiválasztás sorrendje (ahogy a versenyeken), míg kombinációnál nem számít a kiválasztás sorrendje (mintha egy kupacba szednénk ki a $k$ elemet).
Isméléses variáció
Hányféleképpen választhatunk ki $n$ elemből $k$ elemet úgy, hogy mindegyiket csak egyszer használhatjuk fel, és számít a kiválasztás sorrendje? Jele: $V_n^{k,\ i}$.
$$\boxed{V_n^{k,\ i}=n^k}$$
1. Példa: Hányféle számkód (zárkód, PIN-kód) készíthető $k=4$ darab számjegyből, ha minden számjegyet mindenhol használhatunk? A kiválasztásnál az alaphalmazunkban a $0;\ 1;\ 2;\ ...;\ 9$ számok vannak, amiknek száma $n=10$. Így $V_n^{k,\ i}=10^4=10000$ számot kell kipróbálni egy 4-jegyű számzár kinyitásához, hogy az mindenképp kinyíljon.
2. példa: A Totó nevű szerencsejátékban focimeccsekről kell megtippelni, hogy a hazai csapat győz (1), döntetlen lesz a mecs vége (x) vagy a vendég csapat győz (2). Magyarországon $13+1$ meccsre kell tippelni. Mindegyik meccsnél mindegyik eset lehetséges, így az $n=3$ elemből ismétléssel választhatunk ki $k=13+1=14$ elemet, és a sorrend számít. Így egy totószelvény $V_n^{k,\ i}=3^14=4\ 782\ 969$ módon tölthető ki.
Megjegyzések: Ismétléses variációnál a kiválasztott elemek $k$ száma bármekkora lehet (akár nagyobb is, mint az $n$). Ismétléses variációra szokás példának hozni a "hányféle háromsávos zászlót készíthetünk 5 színből" problémát, de ez nem tökéletes példa rá, mert ismétléses variációval számolva olyan színezéseket is beszámolunk, amiknél szomszédos sávok azonos színűek, ami zászlóknál nem fordul elő.
Ismétlés nélküli kombináció
Hányféleképpen választhatunk ki $n$ darab különböző elemből $k$ darabot úgy, hogy egy elemet csak egyszer használhatunk, és a kiválasztottak sorrendje nem számít (tehát csak "kupacba" rakva vesszük ki őket)? Jele: $C_n^k$.
$$\boxed{C_n^k=\binom {n}{k}=\frac{n!}{k! \cdot (n-k)!}}$$
Példa: az ötöslottó sorsolásán $n=90$ számból húznak ki $k=5$ számott, a kihúzás sorrendje nem számít, és egy számot csak egyszer lehet kihúzni (nem rakják vissza). Az eredményhez - az eddigiekből kiindulva - két lépésben juthatunk el. Először válasszunk ki 5 számot, ahogy eddig tettük, azaz hogy számít a sorrend, vagyis ismétlés nélküli variációt végzünk. Ez $V_n^k=\frac{n!}{(n-k)!}$ esetet ad. Csakhogy így külön esetnek vesszük például az $1;\ 2;\ 3; \ 4; \ 5$ és az $2;\ 1;\ 3; \ 4; \ 5$ eseteket, pedig lottóhúzásnál ez mindegy. Ezért második lépésben ezt még le kell osztani azzal, hogy hányféleképpen rendezhető sorrendbe a kihúzott $k=5$ szám, ami az ismétlés nélküli permutáció alapján $P_k=k!$. vagyis:
$$C_n^k=\frac{V_n^k}{P_k}=\frac{\frac{n!}{(n-k)!}}{k!}=\frac{n!}{k! \cdot (n-k)!}$$
Megjegyzések: Az $\displaystyle \binom {n}{k}$ csak egy elterjedt jelölés az $\displaystyle \frac{n!}{k! \cdot (n-k)!}$ kifejezésre, a neve binomiális együttható, és úgy kell kiolvasni, hogy "enn alatt a ká". Ismétlés nélküli kombinációnál is legfeljebb annyi $k$ elemet választhatuk ki, ahány $n$ elem összesen van, tehát $k\le n$.
Ismétléses kombináció
Hányféleképpen választhatunk ki $n$ darab különböző elemből $k$ darabot úgy, hogy egy elemet többször is használhatunk (mintha visszatennénk, vagy kihúzás után egyből "pótlódna" az $n$ elemű alaphalmazban), és a kiválasztottak sorrendje nem számít (tehát csak "kupacba" rakva vesszük ki őket)? Jele: $C_n^{k,\ i}$.
$$\boxed{C_n^k=\binom {n+k-1}{k}=\frac{(n+k-1)!}{k! \cdot (n-1)!}}$$
Példa: A fagyizóban 3-féle ízű fagyi kapható: $\color{deeppink}{\Huge\bullet}$ eper, $\color{saddlebrown}{\Huge\bullet}$ csoki és $\color{blueviolet}{\Huge\bullet}$ áfonya. Hányféle módon kérhetünk 4-gombócos fagyit (a kiválasztás sorrendje nem számít)? Mivel 3 különféle elem közül választhatunk, ezért $n=3$, és 4 elemet választunk, így $k=4$. A problémát a "körök és pálcák" módszerrel oldjuk meg. A körök jelölik a gombócokat, azaz van 4 körünk, azt pedig, hogy ezekből hány eper, hány csoki ízű gombóc lesz, azt elválasztó pálcikákkal fogjuk jelezni úgy, hogy az első pálcikától balra lévő gombócok az 1. ízből vannak, azaz eperízűek. Az 1. és 2. pálcika közötti gombócok a 2. ízből vannak, azaz csokisak, az utolsó pálcikától jobbra lévők pedig az utolsó ízből vannak, azaz áfonyásak. Tehát a $n$ íz "szaparálásához" $n-1$, jelen esetben $3-1=2$ határoló pálcika elég, mert az első pálcikától balra és az utolsótól jobbra is "van egy íz" (persze lehet, hogy épp nulla ilyen ízű gombóc van). Például az alábbi elrendezés a "2 eper, 1 csoki, 1 áfonya" esetét mutatja:
$$\color{darkgray}{\Huge\bullet}\color{darkgray}{\Huge\bullet} \Large| \color{darkgray}{\Huge\bullet} \Large| \color{darkgray}{\Huge\bullet}$$
A szemléletesség kedvéért ugyanez színesen így néz ki:
$$\color{deeppink}{\Huge\bullet}\color{deeppink}{\Huge\bullet} \color{gray}{\Large|} \color{saddlebrown}{\Huge\bullet} \color{gray}{\Large|} \color{blueviolet}{\Huge\bullet}$$
De térjünk vissza a szürke körökhöz, hiszen a pálcikák elhelyezkedése úgyis egyértelműsíti, hogy melyik kör valójában milyen színű-ízű.
Például ha mind a 4 gombóc eper, az így néz ki:
$$\color{darkgray}{\Huge\bullet}\color{darkgray}{\Huge\bullet}\color{darkgray}{\Huge\bullet}\color{darkgray}{\Huge\bullet}\color{gray}{\Large|} \color{gray}{\Large|}$$
mert az első pálcika előtti körök az első ízből (eperből) vannak.
Ha pedig mind a 4 gombóc áfonya, az így:
$$\Large|\Large|\color{darkgray}{\Huge\bullet}\color{darkgray}{\Huge\bullet}\color{darkgray}{\Huge\bullet} \color{darkgray}{\Huge\bullet}$$
mert az utolsó pálcika utáni körök mind az utolsó ízből (áfonyából) vannak.
A $k$ kör és $n-1$ pálcika sorrendje egyértelműen megfeleltethető a számunkra kérdéses lehetséges eseteknek, így a megoldást a körök és pálcikák összes lehetséges sorbarendezései adják. Mivel $n-1$ pálcikánk van és $k$ körünk, ezért egy $n-1+k$ elemű halmazt kell sorbarendeznünk (permutálnunk), méghozzá úgy, hogy van közte $n-1$ és $k$ azonos elem (a pálcikálk illetve a körök). Ez egy ismétléses permutáció, aminek képlete általában:
$$P^{k_1,\ k_2,... k_m}_n=\frac{n!}{k_1! \cdot k_2! \cdot \cdot \cdot k_m!}$$
a mostani elemszámokat beírva:
$$P^{n-1,\ k}_{n-1+k}=\frac{(n-1+k)!}{k! \cdot (n-1)!}$$
És mivel a binomiális együtthatók így néznek ki:
$$\binom{n}{k}=\frac{n!}{k!\cdot (n-k)!}$$
vagy mindez más betűkkel (hiszen jelenleg az $n$ és $k$ nekünk már "foglalt, mert nekünk jelentenek valamit)
$$\binom{m}{p}=\frac{m!}{p!\cdot (m-p)!}$$
vagyis a struktúráját tekintve: "aminek ($m$) a számlálóban van a faktoriálisa, azt a nevezőben ketté kell osztani valahogyan ($p$-re és $(m-p)$-re) és ezen két szám faktoriálisait ($p!$ és $(m-p)!$) össze kell szorozni". A mostani példánkban pont ilyen van, hiszen az $n-1+k$ kidejezés van kettébontva $n-1$ tagra és $k$ tagra. Így most az $m$ szerepét:
$m=n-1+k$
játssza, a $p$ szerepét pedig
$p=k$
játssza, emiatt a végeredményünk az alábbi "binomiálisos alakban" is felírható:
$$C_n^k=\binom {n-1+k}{k}$$
A mi konrét példánkban, ahol $n=3$ és $k=4$, mindez:
$$C_n^k=\frac{(n-1+k)!}{k! \cdot (n-1)!}=\frac{(3-1+4)!}{4! \cdot (3-1)!}=\frac{6!}{4! \cdot 2!}=\frac{5\cdot 6}{2}=\frac{30}{2}=15$$
Tehát 15-féle módon kérhetünk 3-féle fagyiból 4-gombócosat.
Megjegyzések: Az ismétléses kombináció $\displaystyle C_n^k=\binom {n-1+k}{k}$ binomiális alakjában a binomiális felső részében szereplő $n-1+k$ kifejezést $n+k-1$ alakban szokás írni. Ez csupán a matematikusok perverziója (mondván: vegyük előre a kifejezésben szereplő $n$ és $k$ tagokat, és a $-1$ tagot majd csak ezután szerepeltessük. Pedig a levezetésben van $n-1$ (a pálcikák száma), tehát a $\displaystyle C_n^k=\binom {n-1+k}{k}$ alak "kifejezőbb", míg az elterjedten használt $\displaystyle C_n^k=\binom {n+k-1}{k}$ alak nem mutatja a kifejezés hátterét, hiszen a levezetésben nem szerepel sem $n+k$ sem $k-1$. Ismétléses kombnációnál a kiválasztott elemek $k$ száma bármekkora lehet (akár nagyobb is, mint az $n$).
