Kombinatorika

Kombinatorika

Kombinatorika šteje, na koliko načinov lahko izberemo ali razporedimo objekte.

• Permutacije n različnih elementov: n! = n·(n−1)·...·2·1 (fakulteta) — število vseh možnih razporeditev VSEH n elementov. Dogovor: 0! = 1.
• Variacije k-tega razreda iz n elementov (izbor VRSTNI RED šteje, brez ponavljanja): V(n,k) = n!/(n−k)!.
• Kombinacije k-tega razreda iz n elementov (izbor, vrstni red NE šteje): C(n,k) = n!/(k!(n−k)!), pišemo tudi kot binomski simbol (n nad k).

Ključno razlikovanje: pri variacijah je pomembno, KATERI element je na kateri poziciji (npr. razporeditev na stopničkah), pri kombinacijah pa je pomembna samo IZBIRA elementov (npr. izbor skupine, kjer vrstni red ni pomemben).

Zgled: iz 5 dijakov izberemo 2 za predstavnika razreda (vrstni red ni pomemben — kombinacija): C(5,2) = 5!/(2!·3!) = 10. Če pa bi izbirali predsednika in podpredsednika (vrstni red JE pomemben — variacija): V(5,2) = 5!/3! = 20.

Pogosta napaka: dijaki uporabijo formulo za kombinacije, kadar vrstni red DEJANSKO šteje (npr. razporeditev na 1., 2., 3. mesto na tekmovanju) — tam je treba uporabiti variacije, ne kombinacije.