Leszámlálási feladatok

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

n elem lehetséges sorrendjei n elem ismétlés nélküli permutációi, röviden permutációi.

Pontosabban fogalmazva: Legyen A véges halmaz, |A|=n. Ekkor A halmaz elemeinek egy permutációja egy delim{lbrace}{1,2, cdot, n}{rbrace} right A bijekció.

Ezek száma: n! = 1 cdot 2 cdot ... cdot n (kiolvasva: n faktoriális)

Megjegyzés: 0! = 1! = 1

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

n elem közül válasszunk ki k darabot adott sorrenben. Egy ilyen kiválasztást az n elem k-ad osztályú ismétlés nélküli variáciojának nevezünk.

Pontosabban fogalmazva: Legyen A véges halmaz, |A|=n>k. Ekkor A halmaz elemeinek egy k-ad osztályú variációja egy delim{lbrace}{1,2, cdot, n}{rbrace} right A bijekció.

Ezek száma: n cdot (n-1) cdot ... cdot (n-k+1)= {n!} / {(n-k)!}

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

n elemű halmaz egy k elemű részhalmazát az n elem k-ad osztályú ismétlés nélküli kombinációjának nevezzük

A variáció és a kombináció között az alapvető különbség, hogy a kombináció esetén az elemek (kiválasztásának) sorrenje nem számít. Az egyik egy k elemű halmaz, amásik egy k tagú számsor.

Ezek száma: {n!} / {(n-k)! cdot k!} ={n cdot (n-1) cdot ... cdot (n-k+1)}{1 cdot 2 cdot ... cdot k} = (matrix{2}{1}{{n}{k}})

Az (matrix{2}{1}{{n}{k}}) (kiolvasva n alatt a k) értékeket binomiális együtthatóknak nevezzük.

Ismétléses permutáció

n db elem, k₁ db egyféle, k₂ db másféle, k₃ db megint másféle, …, k_e szintén más (a csoportokon belül nem tudom megkülönböztetni az elemeket)

Ezek száma: ${n!} / {k_1! cdot k_2! cdot ... cdot k_e!}$

Ismétléses variáció

n db adott elemből k db-ot választok adott sorrendben, visszatevéssel.

Ezek száma: n^k

Ismétléses kombináció

Ezek száma [matrix{2}{1}{{n}{k}}]=(matrix{2}{1}{{n+k-1}{n-1}})=(matrix{2}{1}{{n+k-1}{k}})