Kombinacija (matematika)

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

Za druge pomene glej kombinacija (razločitev).

Število kombinacij brez ponavljanja

Število kombinacij izbora ${\displaystyle k\,}$ elementov iz množice ${\displaystyle n\,}$ elementov brez možnosti ponavljanja elementov dobimo s pomočjo obrazca

${\displaystyle 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

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

Število kombinacij s ponavljanjem

Kombinacije s ponavljanjem dobimo, če dovolimo, da se v izbranih kombinacijah elementi iz ${\displaystyle n\,}$ ponavljajo, pri tem pa še vedno ni važno zaporedje izbranih elementov. Število teh kombinacij dobimo s pomočjo obrazca

${\displaystyle {{(n+k-1)!} \over {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.

Značilnosti binomskih koeficientov

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

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

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

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

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

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

Glej tudi

• variacija
• particija
• kompozicija

Zunanje povezave

• Weisstein, Eric Wolfgang. »Combination«. MathWorld.
• Kombinacije s ponavljanjem^{[mrtva povezava]} (angleško)