Kombinācija

Kombinācija kombinatorikā ir galīgas kopas apakškopa, kas var būt arī pati kopa. Elementi apakškopā drīkst atkārtoties (tomēr biežāk apskata gadījumu, kad elementi neatkārtojas), bet atšķirībā no variācijām to secībai nav nozīmes (kopas pieraksti ar atšķirīgu vienu un to pašu elementu novietojumu apraksta vienu un to pašu kopu).

Bieži runā arī par k-kombinācijām vai k-apakškopām — tās ir apakškopas ar  elementiem.

 Kombināciju skaits 
Ja ir dota kopa ar  elementiem, tad tās k-kombināciju (k-apakškopu) skaitu, sauktu par kombinācijām no n pa k, var aprēķināt pēc formulas:

,

kur  ir  faktoriāls un  ir binomiālkoeficienti.

 Pierādījums 
Dota kopa ar  elementiem. Cik veidos no šīs kopas var izvēlēties sakārtotas  elementu virknes?

Apskatām divus variantus, kā nonākt līdz atbildei.

1)

Pēc kombināciju skaita definīcijas — no dotās kopas var izvēlēties  dažādas (nesakārtotas) apakškopas.

Cik dažādos veidos var sakārtot  elementus ( elementu kopu)?

Par pirmo elementu varam izvēlēties vienu no  elementiem, par otro — vienu no , pat trešo — vienu no  utt. Līdz par pēdējo —  — elementu varam izvēlēties vienu palikušo elementu.

Pēc kombinatorikas reizināšanas likuma  elementu sakārtoto virkņu skaits tātad ir: .

Līdz ar to no sākotnēji dotās kopas var paņemt sakārtotas  elementu virknes  veidos.

2)

Par pirmo elementu varam izvēlēties vienu no  elementiem, par otro — vienu no , pat trešo — vienu no  utt. Līdz par pēdējo —  — elementu varam izvēlēties vienu no palikušajiem  elementiem.

Pēc kombinatorikas reizināšanas likuma sakārtoto virkņu skaitu tātad var aprēķināt šādi: .

Abu atbilžu vērtībām ir jābūt vienādām: 

Tātad 

 Kombināciju skaits ar atkārtojošiem elementiem 
Ja ir dota kopa ar  elementiem, no kuras jāizvēlas multikopa ar  elementiem (elementi var atkārtoties), tad šīs kombinācijas var aprēķināt pēc formulas:

Piemēram, ja eksistē piecu veidu konfektes () un tiek izvēlētas trīs ar pieļaujamu atkārtošanos (). Šo uzdevumu var interpretēt ģeometriski/algoritmiski, ka iespējamie konfekšu veidi tiek novietoti virknē un tiek padotas instrukcijas vai nu izvēlēties esošo konfekti vai doties pie nākamās konfektes. Tiek sākts no pirmā konfekšu veida virknē. Kopumā pilnā instrukcija sastāv no  izvēlēm un  došanās pie nākamās izvēlēm. Līdz ar to uzdevums tiek pārfrāzēts kāds ir kombināciju skaits šīm instrukcijām. Tiek izvēlētas  no visām instrukcijām būt par izvēles instrukcijām vai  no visām instrukcijām būt par došanos tālāk instrukcijām, tādēļ 

Līdz ar to no pieciem konfekšu veidiem izvēlēties trīs ar atkārtošanos var  veidos.

 Skatīt arī 
 Permutācija
 Binomiālkoeficients

 Atsauces 

Kategorija:Matemātika