Fő kategória: matek.

$\DeclareMathOperator{\tg}{tg}\DeclareMathOperator{\ctg}{ctg}\DeclareMathOperator{\arctg}{arctg}\DeclareMathOperator{\arcctg}{arcctg}\DeclareMathOperator{\arccot}{arccot}\DeclareMathOperator{\arcsec}{arcsec}\DeclareMathOperator{\arccsc}{arccsc}$

Áttekintés

Számos matekfeladat megoldása során hasznát vesszük a kombinatorikának. Akár közvetlenül is: ez esetben a kérdés tipikusan úgy hangzik, hogy hányféleképpen fordulhat elő ez vagy az. De sokkal gyakoribb az, amikor valaminek a valószínűségét kell kiszámolni, és az összes valamint a számunkra kedvező esetek számát tudjuk ennek segítségével meghatározni.

Permutáció

A permutáció alatt adott halmaz elemeinek sorba rendezését értjük.

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

Ez esetben minden elem különböző. Jelölése és kiszámítása:

$P_n = n!$

Példa: nyolcan futnak egy futóversenyen. Hányféleképpen érhetnek célba?

Megoldás: $P_8 = 8! = 40.320$

Magyarázat: az első helyre nyolcféleképpen tudunk választani, a másodikra hétféleképpen stb.

Illusztrálása $n=3$ esetben ($3! = 6$):

Python kód

for c in itertools.permutations('🔴🟡🔵'):
    print(c)

('🔴', '🟡', '🔵')
('🔴', '🔵', '🟡')
('🟡', '🔴', '🔵')
('🟡', '🔵', '🔴')
('🔵', '🔴', '🟡')
('🔵', '🟡', '🔴')

Ismétléses permutáció

Ez esetben előfordulhatnak olyan elemek, amelyek nem megkülönböztethetőek. Ha egy $n$ elemű halmazban $s$ különböző elem fordul elő úgy, hogy az $i$-edik elem darabszáma $k_i$ (ez esetben $k_1 + k_2 + … + k_s = n$), akkor a jelölése és a képlet:

$P^{(k_1;k_2;… k_s)}_n = \frac{n!}{k_1!\cdot k_2!\cdot … \cdot k_s!}$

Példa: Nyolcan futnak egy futóversenyen, öt fiú és három lány. A nemek sorrendje hányféleképpen alakulhat?

Megoldás: $P^{(5,3)}_8 = \frac{8!}{5!\cdot 3!} = \frac{40.320}{120\cdot 6} = 56$

Magyarázat: mivel a feladatban a fiúkat ill. a lányokat nem különböztetjük meg (tehát mondjuk Pista harmadik és Jóska ötödik helyezése egyenértékű Jóska harmadik és Pista ötödik helyezésével), a végeredményt el kell osztani az egyes nemek belső sorrendjével, amit pont a nevező ad meg.

Illusztrálása $n=4$, $k_1=2$ és $k_2=2$ esetben ($\frac{4!}{2!\cdot 2!}=6$):

Python kód

for c in collections.Counter(itertools.permutations('🔴🔴🟡🟡')):
    print(c)

('🔴', '🔴', '🟡', '🟡')
('🔴', '🟡', '🔴', '🟡')
('🔴', '🟡', '🟡', '🔴')
('🟡', '🔴', '🔴', '🟡')
('🟡', '🔴', '🟡', '🔴')
('🟡', '🟡', '🔴', '🔴')

Variáció

Azt adja meg, hogy hányféleképpen választhatunk ki $n$ elemből $k$ elemet úgy, hogy számít a kiválasztás sorrendje.

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

Egy elem egyszer fordulhat elő a kiválasztásban. Jelölése és kiszámítása:

$V^k_n = \frac{n!}{(n-k)!}$

Ez esetben $n$ elem $k$-ad osztályú variációjáról beszélünk.

Példa: nyolcan futnak egy futóversenyen. Hányféleképpen alakulhat a három dobogós helyezés?

Megoldás: $V^3_8 = \frac{8!}{(8-3)!} = \frac{8!}{5!} = 8\cdot 7\cdot 6 = 336$

Magyarázat: első helyezést nyolcan érhetnek el, másodikat heten (az első helyezett nem lehet második is, mert már célba ért), harmadikat hatan. Ezek függetlenek, azaz a győztes nem befolyásolja a második helyezettet, így össze kell őket szorozni.

Illusztrálása $n=4$ és $k=2$ esetben ($\frac{4!}{(4-2)!} = 12$):

Python kód

for c in itertools.permutations('🔴🟡🔵🟢', 2):
    print(c)

('🔴', '🟡')
('🔴', '🔵')
('🔴', '🟢')
('🟡', '🔴')
('🟡', '🔵')
('🟡', '🟢')
('🔵', '🔴')
('🔵', '🟡')
('🔵', '🟢')
('🟢', '🔴')
('🟢', '🟡')
('🟢', '🔵')

Ismétléses variáció

Ugyanaz az elem többször is előfordulhat. Jelölése és kiszámítása:

$V^{k,i}_n = n^k$

Példa: nyolcan futnak egy futóversenyen. Ezt háromszor megismétlik, így tehát lesz összesen három első helyezett. Ez hányféleképpen jöhet létre, ha a sorrend is számít? (Tehát tegyünk különbséget a Jóska, Pista, Jóska és a Jóska, Jóska, Pista győzelmek között.)

Megoldás: $V^{3,i}_8 = 8^3 = 512$

Magyarázat: az első, a második és a harmadik versenyben is nyolcan érhetnek célba. A három verseny egymástól független.

Illusztrálása $n=4$ és $k=2$ esetben ($4^2=16$):

Python kód

for c in itertools.product('🔴🟡🔵🟢', repeat=2):
    print(c)

('🔴', '🔴')
('🔴', '🟡')
('🔴', '🔵')
('🔴', '🟢')
('🟡', '🔴')
('🟡', '🟡')
('🟡', '🔵')
('🟡', '🟢')
('🔵', '🔴')
('🔵', '🟡')
('🔵', '🔵')
('🔵', '🟢')
('🟢', '🔴')
('🟢', '🟡')
('🟢', '🔵')
('🟢', '🟢')

Kombináció

Azt adja meg, hogy hányféleképpen képezhetjük egy halmaz részhalmazait. Ez tehát annyiban különbözik csak a variációtól, hogy itt nem vesszük figyelembe a kiválasztás sorrendjét.

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

Ez esetben ugyanazt az elemet csak egyszer választhatjuk ki. Jelölése és kiszámítása:

$C^k_n = \binom{n}{k} = \frac{n!}{k!\cdot(n-k)!}$

Példa: nyolcan futnak egy futóversenyen. A három leggyorsabb tovább jut a versenysorozat következő fordulójába. Ez hányféleképpen lehetséges?

Megoldás: $C^3_8 = \binom{8}{3} = \frac{8!}{3!\cdot(8-3)!} = 56$

Magyarázat: az ismétlés nélküli variáció példájában láttuk, hogy a dobogó sorrendje 336-féleképpen alakulhat. Azonban a továbbjutás szempontjából mindegy, hogy valaki az első vagy a harmadik helyről jut-e tovább, így ezt el kell osztani a három dobogós belső sorrendjével, azaz $3! = 6$-tal, így az eredmény 56.

Illusztrálása $n=4$ és $k=2$ esetben ($\binom{4}{2}=\frac{4!}{2!\cdot(4-2)!}=6$):

Python kód

for c in itertools.combinations('🔴🟡🔵🟢', 2):
    print(c)

('🔴', '🟡')
('🔴', '🔵')
('🔴', '🟢')
('🟡', '🔵')
('🟡', '🟢')
('🔵', '🟢')

Ismétléses kombináció

Ez esetben ugyanazt az elemet többször is kiválaszthatjuk. Jelölése és kiszámítása:

$C^{k,i}_n = \binom{n+k-1}{k} = \frac{(n+k-1)!}{k!\cdot(n-1)!}$

Példa: nyolcan futnak egy futóversenyen. Ezt háromszor megismétlik, így tehát lesz összesen három első helyezett. Ez hányféleképpen jöhet létre, ha a sorrend nem számít? (Tehát ne tegyünk különbséget a Jóska, Pista, Jóska és a Jóska, Jóska, Pista győzelmek között.)

Megoldás: $C^{3,i}_8 = \binom{8+3-1}{3} = \binom{10}{3} = \frac{10!}{3!\cdot 7!} = 120$

Magyarázat: képzeljük el, hogy mindegyik futó előtt van egy-egy doboz, ahova belehelyezzük a győzteseknek járó megkülönböztethetetlen aranyérmeket. Jelen esetben 8 dobozba teszünk összesen 3 aranyérmet. Képzeljük el a sorba kihelyezett dobozokat, és képzeletben rajzoljunk közéjük valamilyen elválasztó jelet, pl. ezt: |. Eggyel kevesebb ilyen jelre van szükség, mint ahány induló van, jelen esetben tehát 7, ami elválasztja a 8 dobozt. Az aranyérmet jelölje valamilyen karakter, mondjuk a $. Itt tehát az a kérdés, hogy hányféleképpen tudunk n-1 darab elválasztót és k darab $ jelet sorba rendezni, a példában 7 elválasztót és 3 $ jelet, mégpedig úgy, hogy sem az elválasztók sem az aranyérmet szimbolizáló karakterek nem megkülönböztethetőek. Egy ilyen példa: $||||$$|||. Ezzel a gondolatmenettel kijön a fenti képlet. (A magyarázatért hatalmas köszönet Simon Daninak!)

Illusztrálása $n=4$ és $k=2$ esetben ($\binom{4+2-1}{2}=\frac{5!}{2!\cdot(5-2)!}=10$):

Python kód

for c in itertools.combinations_with_replacement('🔴🟡🔵🟢', 2):
    print(c)

('🔴', '🔴')
('🔴', '🟡')
('🔴', '🔵')
('🔴', '🟢')
('🟡', '🟡')
('🟡', '🔵')
('🟡', '🟢')
('🔵', '🔵')
('🔵', '🟢')
('🟢', '🟢')