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 $(\genfrac{}{}{0ex}{}{n}{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}=(\genfrac{}{}{0ex}{}{n+k-1}{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