Kombinācija

Vikipēdijas raksts

Kombinatorikā par kombināciju sauc kopas apakškopu (kas var būt arī pati kopa). Elementi apakškopā nedrīkst atkārtoties, un 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 $k$ elementiem.

[izmainīt šo sadaļu] Kombināciju skaits

Ja ir dota kopa ar $n$ 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:

${n \choose k} = C^k_n = \frac {n!} {k! \cdot (n-k)!}$ ,
kur $n!$ ir $n$ faktoriāls.

[izmainīt šo sadaļu] Pierādījums

Dota kopa ar $n$ elementiem. Cik veidos no šīs kopas var izvēlēties sakārtotas $k$ elementu virknes?

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

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

Cik dažādos veidos var sakārtot

k

elementus (

k

elementu kopu)?

Par pirmo elementu varam izvēlēties vienu no

k

elementiem, par otro – vienu no

k - 1

, pat trešo – vienu no

k - 2

utt. Līdz par pēdējo –

k

– elementu varam izvēlēties vienu palikušo elementu.

Pēc kombinatorikas reizināšanas likuma

k

elementu sakārtoto virkņu skaits tātad ir: $k \cdot (k-1) \cdot (k-2) \cdot \ldots \cdot 1$ .

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

k

elementu virknes ${n \choose k} \cdot k \cdot (k-1) \cdot (k-2) \cdot \ldots \cdot 1$ veidos.

Par pirmo elementu varam izvēlēties vienu no

n

elementiem, par otro – vienu no

n - 1

, pat trešo – vienu no

n - 2

utt. Līdz par pēdējo –

k

– elementu varam izvēlēties vienu no palikušajiem

n - k + 1

elementiem.

Pēc kombinatorikas reizināšanas likuma sakārtoto virkņu skaitu tātad var aprēķināt šādi: $n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)$ .

Abu atbilžu vērtībām ir jābūt vienādām: ${n \choose k} \cdot k \cdot (k-1) \cdot (k-2) \cdot \ldots \cdot 1 = n \cdot (n-1) \cdot (n-2) \cdot \ldots \cdot (n-k+1)$