Kombinacija (matematika)

Za druge pomene glej kombinacija (razločitev).

Kombinacija (oznaka $C_{n}^{k}\!\,$ za kombinacije $k\!\,$ elementov iz množice $n\!\,$ elementov) je v matematiki način izbora $k\!\$ elementov iz večje množice $n\,$ različnih elementov. Pri tem pa zaporedje izbora ni pomembno. Kombinacije so podobne variacijam. Od njih se razlikujejo le v tem, da pri kombinacijah ni pomemben vrstni red izbranih elementov, pri variacijah pa je zaporedje izbranih elementov pomembno. Pri kombinacijah je pomembno samo to, kateri elementi so izbrani. Kombinacije se lahko pojavljajo s ponavljanjem ali pa brez ponavljanja.

Število kombinacij brez ponavljanja

Število kombinacij izbora $k\!\,$ elementov iz množice $n\!\,$ elementov brez možnosti ponavljanja elementov se dobi s pomočjo obrazca:

$C_{n}^{k}={n \choose k}={\frac {n!}{k!(n-k)!}}={\frac {n\cdot (n-1)\cdots (n-k+1)}{k\cdot (k-1)\cdots 1}},\quad n\geq k\geq 0,\quad (n,k)\in N\!\,,$

kjer je:

• $n!\!\,$  – fakulteta števila $n\!\,$
• $n \choose k\!\,$  – binomski koeficient (beri $n\!\,$ nad $k\!\,$).

Število kombinacij s ponavljanjem

Kombinacije s ponavljanjem se dobi, če se dovoli, da se v izbranih kombinacijah elementi iz $n\!\,$ ponavljajo, pri tem pa še vedno ni pomembno zaporedje izbranih elementov. Število teh kombinacij se dobi s pomočjo obrazca:

${\frac {(n+k-1)!}{k!(n-1)!}}={{n+k-1} \choose {k}}={{n+k-1} \choose {n-1}}=\left(\!\!{\binom {n}{k}}\!\!\right)\!\,,$

kjer so oznake enake kot zgoraj.

Lastnosti binomskih koeficientov

• ${\binom {n}{0}}={\binom {n}{n}}=1\!\,,$

• ${\binom {n}{k}}=0,\,{\text{ za vse }}k>n\!\,,$

• ${\binom {n}{k}}={\binom {n}{k-1}}{\frac {n-k+1}{k}},\,{\text{ za vse }}k>0\!\,,$

• ${\binom {n}{k}}={\binom {n-1}{k}}{\frac {n}{n-k}},\,{\text{ za vse }}k<n\!\,,$

• ${\binom {n}{k}}={\binom {n-1}{k-1}}{\frac {n}{k}},\,{\text{ za vse }}n,k>0\!\,,$

• ${\binom {n}{k}}={\binom {n}{n-k}},\,{\text{ za vse }}0\leq k\leq n\!\,,$

• ${\binom {n}{n-1}}=n\!\,.$

Glej tudi

• variacija
• particija
• kompozicija

Zunanje povezave

• Weisstein, Eric Wolfgang. »Combination«. MathWorld (v angleščini).
• Kombinacije s ponavljanjem (angleško)