Kombinācija

Ja ir dota kopa ar ${\displaystyle 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:

${\displaystyle {n \choose k}=C_{n}^{k}={\frac {n!}{k!\cdot (n-k)!}}}$ ,

kur ${\displaystyle n!}$  ir ${\displaystyle n}$  faktoriāls un ${\displaystyle {\tbinom {n}{k}}}$  ir binomiālkoeficienti.

Dota kopa ar ${\displaystyle n}$  elementiem. Cik veidos no šīs kopas var izvēlēties sakārtotas ${\displaystyle k}$  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 ${\displaystyle n \choose k}$  dažādas (nesakārtotas) apakškopas.

Cik dažādos veidos var sakārtot ${\displaystyle k}$  elementus (${\displaystyle k}$  elementu kopu)?

Par pirmo elementu varam izvēlēties vienu no ${\displaystyle k}$  elementiem, par otro — vienu no ${\displaystyle k-1}$ , pat trešo — vienu no ${\displaystyle k-2}$  utt. Līdz par pēdējo — ${\displaystyle k}$  — elementu varam izvēlēties vienu palikušo elementu.

Pēc kombinatorikas reizināšanas likuma ${\displaystyle k}$  elementu sakārtoto virkņu skaits tātad ir: ${\displaystyle 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 ${\displaystyle k}$  elementu virknes ${\displaystyle {n \choose k}\cdot k\cdot (k-1)\cdot (k-2)\cdot \ldots \cdot 1}$  veidos.

2)

Par pirmo elementu varam izvēlēties vienu no ${\displaystyle n}$  elementiem, par otro — vienu no ${\displaystyle n-1}$ , pat trešo — vienu no ${\displaystyle n-2}$  utt. Līdz par pēdējo — ${\displaystyle k}$  — elementu varam izvēlēties vienu no palikušajiem ${\displaystyle n-k+1}$  elementiem.

Pēc kombinatorikas reizināšanas likuma sakārtoto virkņu skaitu tātad var aprēķināt šādi: ${\displaystyle 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: ${\displaystyle {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)}$ 

Tātad ${\displaystyle {n \choose k}={\frac {n\cdot (n-1)\cdot (n-2)\cdot \ldots \cdot (n-k+1)}{k\cdot (k-1)\cdot (k-2)\cdot \ldots \cdot 1}}=}$ 

${\displaystyle ={\frac {n\cdot (n-1)\cdot (n-2)\cdot \ldots \cdot (n-k+1)}{k!}}={\frac {n!}{(n-k)!}}\cdot {\frac {1}{k!}}}$ 

 

Ja ir dota kopa ar ${\displaystyle n}$  elementiem, no kuras jāizvēlas multikopa ar ${\displaystyle k}$  elementiem (elementi var atkārtoties), tad šīs kombinācijas var aprēķināt pēc formulas:

${\displaystyle \left(\!\!{n \choose k}\!\!\right)={\frac {(k+n-1)!}{k!\cdot (n-1)!}}={k+n-1 \choose k}={k+n-1 \choose n-1}}$ 

Piemēram, ja eksistē piecu veidu konfektes (${\displaystyle n=5}$ ) un tiek izvēlētas trīs ar pieļaujamu atkārtošanos (${\displaystyle k=3}$ ). Š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 ${\displaystyle k}$  izvēlēm un ${\displaystyle n-1}$  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 ${\displaystyle k}$  no visām instrukcijām būt par izvēles instrukcijām vai ${\displaystyle n-1}$  no visām instrukcijām būt par došanos tālāk instrukcijām, tādēļ ${\displaystyle \left(\!\!{n \choose k}\!\!\right)={k+n-1 \choose k}={k+n-1 \choose n-1}}$ ^[1]

Līdz ar to no pieciem konfekšu veidiem izvēlēties trīs ar atkārtošanos var ${\displaystyle \left(\!\!{5 \choose 3}\!\!\right)={\frac {(3+5-1)!}{3!\cdot (5-1)!}}={\frac {7!}{3!\cdot 4!}}=35}$  veidos.

• Permutācija
• Binomiālais koeficients

1. ↑ Rod Pierce. «Combinations and Permutations».