navigacija inštrukcije

inštrukcije > matematika > Kombinatorika

Objavljeno: 22.2.2019

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!}{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)}$

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:

nalagam inštruktorje

Hitri kontakt

031 606 666


Inštruktor meseca

Inštruktor Jan

inštruktor meseca

3 prejetih referenc

zvezda mesecazvezda mesecazvezda mesecazvezda mesecazvezda meseca

Lokacije

interaktiven zemljevid inštruktorjev
Poiščite mi inštruktorja

Inštruktorja poiščemo namesto vas

Da bi bil postopek iskanja vašega inštruktorja čim bolj učinkovit, vas prosimo za nekaj podatkov.