Kombinatorika

Osnovni izrek kombinatorike (pravilo produkta)

Naj bo proces odločanja takšen, da poteka v $k$ zaporednih fazah, pri čemer je v prvi fazi $n_1$ možnih odločitev, v drugi fazi $n_2$ možnih odločitev, ..., v $k$-ti fazi $n_k$ možnih odločitev. Število izborov je neodvisno od tega, katere možnosti smo zbrali v predhodnih fazah. Potem je mogoče celotni izbor opraviti na $n = n_1 \cdot n_2 \cdot ... \cdot n_k $ načinov.

Pravilo vsote

Če se pri izbiranju lahko odločimo bodisi za eno od $n_1$ možnosti iz prve množice izborov bodisi za eno od $n_2$ možnosti iz druge množice izborov, ki so nezdružjivi z izbori v prvi množici, potem imamo v celoti $n = n_1 + n_2$ izborov.

Shemo, s katero grafično prikažemo vse možne izbore odločanja imenujemo kombinatorično drevo.

Permutacije brez ponavljanja

Permutacije brez ponavljanja so razporedi $n$ različnih elementov v nize dolžine $n$.

Število permutacij brez ponavljanja:

$$P_n = n!$$ $$n! = 1 \cdot 2 \cdot 3 \cdot ... \cdot (n-1) \cdot n$$

Število bijektivnih preslikav končne množice moči $n$ nase je $n!$.

Pemutacije s ponavljanjem

Če sestavljamo razporede dolžine $n$ iz $k$ različnih elementov, kjer prvi element nastopa $l_1$-krat, drugi $l_2$-krat, itd., torej $l_1 + l_2 + ... l_k = n$. To lahko naredimo na $$ P_n^{m_1,m_2,...,m_k} = \frac{n!}{m_1! \cdot m_2! \cdot ... \cdot m_k!}$$ različnih načinov.

Variacije brez ponavljanja

Nize velikosti $r$ elementov, ki so si med seboj razilčni, izmed $n$ elementov imenujemo variacije brez ponavljanja reda $r$ iz $n$ elementov.

Število variacij brez ponavljanja: $$V_n^r = n \cdot (n-1) \cdot (n-2) \cdot ... \cdot (n-r+1)) = \frac{n!}{(n-r)!}$$.

Število injektivnih preslikav iz množice z močjo $r$ v množico z močjo $n$, kjer velja $r \leq n$, je $\frac{n!}{(n-r)!}$.

Variacije s ponavljanjem

Enaka definicija kot pri variacijah brez ponavljanja, s to razliko, da posamezni element nastopi večkrat.

Število variacij s ponavljanjem: $$^{(p)}V_n^r = n^r.$$

Število vseh preslikav iz množice z močjo $r$ v množico z močjo $n$ je enako $n^r.$

Kombinacije brez ponavljanja:

Kombinacije reda $r$ iz $n$ elementov so podmnožice z močjo $r$ končne množice, ki ima moč $n$, pri čemur velja, da je $r \leq n$.

Število kombinacij brez ponavljanja: $$C_n^r = \frac{n!}{n! (n-r)!} = \frac{V_n^r}{r!}.$$

Izraz $\binom{n}{r}$ imenujemo binomski simbol, ki nam pove število podmnožic moči $r$ množice z močjo $n$.

Lastnosti binomskega simbola:

$\binom{n}{r} = \binom{n}{(n-r)}$ $\binom{n}{0} = 1$ $\binom{n}{r} + \binom{n}{(r+1)} = \binom{(n+1)}{(r+1)}$

Primer 1

V omari imamo 3 pare hlač, 4 puloverje iz 7 srajc. Na koliko načinov se lahko oblečemo?

Pravilo produkta: Upoštevamo vse možne kombinacije, torej $3 \cdot 4 \cdot 7 = 84.$

Primer 2:

Na izbiro imamo 5 kap in 3 klobuke. Koliko različnih opcij za pokritje imamo?

Pravilo vsote: $5 + 3 = 8.$

Primer 3

Podane so črke S,A,D,E,Ž. Črke naj se ne ponavljajo.


a) Koliko različnih besed lahko sestavimo?

$$5 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 120.$$
b) S mora stati na prvem mestu.
$$1 \cdot 4 \cdot 3 \cdot 2 \cdot 1 = 24.$$
Za prvo mesto imamo samo eno možnost, ostala mesta so enaka kot zgoraj.

c) Samoglasniki morajo stati skupaj, soglasniki skupaj.
Samoglasniki predstavljajo eno množico z dvema elementoma, soglasniki pa drugo množico s tremi elementi. Imamo torej} $$2! \cdot 2! \cdot 3! = 24$$ možnosti

Primer 4:

Iz škatle v kateri je 5 rumenih, 4 zelene in 3 rdeče kroglice, hkrati izlečemo
a) 3 raznobarvne kroglice:
$$\binom{5}{1} \binom{4}{1} \binom{3}{1} = 5 \cdot 4 \cdot 3 = 60.$$

b) 3 kroglice, od katerih sta 2 enaki barvi:
$$ \binom{5}{2} \binom{7}{1} + \binom{4}{2} \binom{8}{1} + \binom{3}{2} \binom{9}{1} = 70 + 48 + 27 = 145.$$

Primer 5

Koliko je permutacij besede BARBARA?

Pogledamo koliko je dolžina besede in koliko je posameznih črk.
$$P_7^{2,3,2} = \frac{7!}{2! \cdot 3! \cdot 2!} = 210.$$

Preberite še:

Potrebujete dodatne informacije? Pomagajo vam lahko inštruktorji matematike.

Razvrsti po:

Hitri kontakt

031 606 666

Inštruktor meseca

Inštruktorica Nina

inštruktor meseca

3 prejetih referenc

zvezda mesecazvezda mesecazvezda mesecazvezda mesecazvezda meseca

Lokacije

interaktiven zemljevid inštruktorjev