Kombináció

A kombináció a kombinatorika egyik gyakran használt fogalma. Egy halmaz elemeinek ismétlés nélküli kombinációi a halmaz részhalmazai. A részhalmazok helyett multihalmazokat tekintve jutunk az ismétléses kombinációkhoz. Halmazokról illetve multihalmazokról lévén szó, a kiválasztott elemek sorrendjét nem vesszük figyelembe.

Ismétlés nélküli kombinációk

Mind a $k$ elem különböző. Az így képzett $k$ elemű halmazok az $n$ elem $k$-adosztályú kombinációi. Ezen kombinációk számát $C_{n}^{k}$ szimbólummal jelöljük. Belátható, hogy

$C_{n}^{k}={\frac {n!}{k!(n-k)!}}$

Ugyanis az ${\frac {n!}{(n-k)!}}$ képlet adja n elem k-adosztályú variációinak számát. A nevezőben lévő k! pedig, mivel itt a sorrend nem számít, elosztja a lehetőségek számát a k elem permutációinak számával.

A képletet szokás az ${n \choose k}={\frac {n!}{k!(n-k)!}}$ szimbólummal is jelölni, melyet „n alatt a k”-nak olvassuk.

Ismétléses kombinációk

A kiválasztott $k$ elem nem feltétlenül különböző. Az így képzett multihalmazok, az $n$ elem $k$-adosztályú ismétléses kombinációi. Számukat $C_{n}^{k,i}$-val jelöljük, ahol belátható:

$C_{n}^{k,i}={{n+k-1} \choose k}$.

Alkalmazások

Az ismétlés nélküli kombinációk számát, azaz a $C_{n}^{k}$ értékeket hívják binomiális együtthatóknak is a binomiális tétel miatt. Különböző matematikai szoftverekben emiatt jellemzően a binomial nevű kétváltozós függvény adja vissza a $C_{n}^{k}$ értéket. Például a Maple-ben vagy MuPAD-ban így:

binomial(n,k)

A MATLAB rendszerben az nchoosek beépített függvény használható a binomiális együtthatók számítására.

Lásd még

• kombinatorika
• variáció
• permutáció
• Pascal-háromszög