Kombinatorika

Iz Wikipedije, proste enciklopedije
Skoči na: navigacija, iskanje

Kombinatórika je matematična disciplina, ki preučuje, na koliko načinov je možno razporediti, preurediti oziroma izbrati določeno množico elementov. Kombinatoriko pogosto štejemo za pomožno panogo verjetnostnega računa.

Osnovni kombinatorični problemi[uredi | uredi kodo]

Permutacije[uredi | uredi kodo]

Permutacije treh raznobarvnih kroglic urejene po leksikografskem vrstnem redu

Permutacije so različne razporeditve n elementov na n prostih mest. Pri tem je pomembno, da je število prostih mest enako kot število predmetov, ki jih razporejamo. Predmeti so lahko med seboj vsi različni (permutacije brez ponavljanja) ali pa tudi ne (permutacije s ponavljanjem).

Kombinatorika se ukvarja z vprašanjem, koliko je vseh permutacij in kako jih razporediti po smiselnem vrstnem redu.

Število permutacij n različnih elementov (brez ponavljanja) je enako produktu vseh naravnih števil od 1 do n:

P=n\cdot(n-1)\cdot\cdots\cdot3\cdot2\cdot1\,\!

To zapišemo tudi s simbolom:

P=n!\,\!

(beri: n faktoriela ali n fakulteta)

Variacije[uredi | uredi kodo]

Variacije so podobne permutacijam, le da število prostih mest ni nujno enako kot število predmetov.

Pri variacijah brez ponavljanja imamo na voljo manj prostih mest kot je predmetov, zato nekaj predmetov ostane nerazporejenih. Število variacij n elementov na r prostih mest brez ponavljanja je enako:

V=\frac{n!}{(n-r)!}

Pri variacijah s ponavljanjem pa dopustimo, da se predmet v razporeditvi lahko pojavi poljubno mnogokrat. Število variacij n elementov na r prostih mest s ponavljanjem je enako:

V=n^r\,\!

Kombinacije[uredi | uredi kodo]

Kombinacije so podobne variacijam, le da nas pri kombinacijah ne zanima vrstni red (razporeditev) izbranih predmetov, pač pa samo to, katei predmeti so bili izbrani.

Tudi pri kombinacijah ločimo kombinacije s ponavljanjem in kombinacije brez ponavljanja.

Kombinacije brez ponavljanja so izbire k različnih elementov izmed n različnih elementov, ki so na voljo. Število vseh možnih izbir je enako:

C=\frac{n!}{k!\cdot(n-k)!}

To pogosto označimo tudi z binomskim simbolom:

C={n \choose k}

Pri kombinacijah s ponavljanjem imamo na voljo n različnih elementov, izmed njih pa želimo izbrati k elementov tako, da lahko posamezni element izberemo tudi večkrat (poljubno mnogokrat). Število kombinacij s ponavljanjem je enako:

C={{n+k-1} \choose k}

Leksikografski vrstni red[uredi | uredi kodo]

Eden od osnovnih problemov kombinatorike je tudi vprašanje, kako urediti permuacije, variacije ali kombinacije po smiselnem vrstnem redu. Najpogosteje uporabljamo leksikografski vrstni red, ki je posplošitev običajnega abecednega vrstnega reda, kakršnega uporabljamo v leksikonih (od tod ime leksikografski), slovarjih, imenikih in abecednih seznamih.

Črke abecede so urejene po standardnem vrstnem redu. Pri razvrščanju besed, ki imajo več črk, pa upoštevamo naslednja pravila:

  • če imata dve besedi različni prvi črki, ju sortiramo glede na prvi črki
  • če imata dve besedi enako prvo črko, pa različni drugi črki, ju sortiramo glede na drugi črki
  • če se dve besedi ujemata v prvih n črkah, na naslednjem mestu pa imata različni črki, ju sortiramo glede na ti dve črki

Zgledi leksikografskega razvrščanja slovenskih besed:

  • beseda AVTO je pred besedo BRAT (ker je A pred B)
  • beseda ATA je pred besedo AVTO (prvi črki sta enaki, zato pogledamo drugi črki: T pa je pred V)
  • beseda AVTOMAT je pred besedo AVTOMOBIL (črke AVTOM se ujemajo, zato pogledamo naslednji črki: A je pred O)

V kombinatoriki pogosto uporabljamo isto načelo tudi za urejanje drugih objektov, ne le za črke. Primer: Če določimo, da je modra barva (M) pred rdečo (R) in ta pred zeleno (Z), lahko vse permutacije treh raznobarvnih kroglic uredimo po leksikografskem redu (glej sliko zgoraj):

M R Z
M Z R
R M Z
R Z M
Z M R
Z R M