inštrukcije > matematika > Kombinatorika
Objavljeno: 22.2.2019
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.
Č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 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!$.
Č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.
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)!}$.
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 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!}{r! (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)}$
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.$
Na izbiro imamo 5 kap in 3 klobuke. Koliko različnih opcij za pokritje imamo?
Pravilo vsote: $5 + 3 = 8.$
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
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.$$
Pogledamo koliko je dolžina besede in koliko je posameznih črk.
$$P_7^{2,3,2} = \frac{7!}{2! \cdot 3! \cdot 2!} = 210.$$