Šī paragrāfa ietvaros k un n – veseli nenegatīvi skaitļi, kas apmierina nevienādību .

 

definīcija. 0!=1; (n+1)!=(n+1)n!

 

definīcija. Skaitli =n! sauc par permutāciju skaitu no n elementiem.

definīcija. Skaitli  sauc par variāciju skaitu no n elementiem pa k elementiem.

definīcija. Skaitli  sauc par kombināciju skaitu no n elementiem pa k elementiem.

 

Kombinatorikas reizināšanas likums. Ja objektu var izvēlēties m veidos, bet pēc katras šādas izvēles citu objektu  var izvēlēties (neatkarīgi no objekta izvēles) k veidos, tad objektu un  pārus var izraudzīt mk veidos.

Matemātiski šis likums precizējams sekojoši.

 

teorēma. Ja kopas A apjoms ir m, bet kopas B apjoms ir k, tad kopas apjoms ir mk.

 

Uzmanību! Pieraksts  nozīmē to, ka tiek saskaitīti visi i, piešķirot tiem vērtības no 1 līdz n.

 

Kombināciju īpašības

 

,   .

Ja k tad .

.

, .

Ja n>0, tad .

Ja , tad .

 

Sakārtoti iztvērumi (variāciju izmantošana).

 

Aplūkosim n-elementu kopu N. No šīs kopas elementiem konstruēsim dažādus k-dimensionālus kortežus; katru šādu kortežu kombinatorikā (varbūtību teorijā) mēdz saukt par sakārtotu apjoma k iztvērumu ar atkārtojumiem.

 

Ja N={a,b,c}, tad n=3, un dotajā gadījumā var izveidot deviņus apjoma 2 iztvērumus, proti (a,a), (a,b), (a,c), (b,a), (b,b), (b,c), (c,a), (c,b) un  (c,c).

 

teorēma. Sakārtotu apjoma k iztvērumu skaits ar atkārtojumiem no n-elementīgas kopas ir .

 

Pierādījums. Ja ir apjoma k izvērtums, ko mēs vēlamies konstruēt, tad elementa  lomā varam izvēlēties jebkuru no kopas n elementiem, tāpat arī elementa  lomā varam izvēlēties jebkuru no kopas n elementiem. Ja esam jau izvēlējušies elementus , tad arī  lomai varam izvēlēties jebkuru no kopas n elementiem. Tā rezultātā dažādo      k-dimensionālo kortežu skaits vienāds ar reizinājumu  .

 

Otra iespēja, no kopas N elementiem konstruēt tikai k-dimensionālos kortežus  ar dažādām koordinātām, t.i., , ja . Katru šādu kortežu kombinatorikā  (varbūtību teorijā) mēdz saukt  par sakārtotu apjoma k iztvērumu bez atkārtojumiem.

 

teorēma. Sakārtotu apjoma k iztvērumu skaits bez atkārtojumiem no n-elementīgas kopas ir .

 

Pierādījums.  Ja  ir apjoma k izvērtums, ko mēs vēlamies konstruēt, tad elementa  lomā varam izvēlēties jebkuru no kopas n elementiem. Turpretī  lomā nevaram izvēlēties elementu , jo tas jau izvēlēts. Tātad atliek izvēle no n–1 elementa. Ja esam jau izvēlējušies elementus , tad šos elementus  elementa  lomai vairs nevar izvēlēties. Tātad atliek izvēle no atlikušajiem n–i elementiem. Tā rezultātā dažādo kortežu skaits vienāds ar reizinājumu  

 

Speciālā gadījumā, ja k=n, sakārtotu apjoma k iztvērumu skaits bez atkārtojumiem no n-elementīgas kopas ir .

 

Nesakārtoti iztvērumi (kombināciju izmantošana)

 

Aplūkosim n-elementu kopu N. No šīs kopas elementiem konstruēsim dažādas k-elementīgas kopas; katru šādu apakškopu kombinatorikā (varbūtību teorijā) mēdz saukt par nesakārtotu apjoma k iztvērumu bez atkārtojumiem.

 

Ja N={a,b,c,d}, tad n=4, un dotajā gadījumā var izveidot sešus  apjoma 2 iztvērumus, proti, , , , ,  un .

 

teorēma. Nesakārtotu apjoma k iztvērumu skaits bez atkārtojumiem no n-elementīgas kopas ir .

 

Pierādījums.  Ja ir apjoma k izvērtums, ko mēs vēlamies konstruēt, tad mēs varam rīkoties sekojoši. Konstruējam kādu sakārtotu apjoma k iztvērumu  bez atkārtojumiem, un tad mūsu rīcībā ir arī kopa – atliek tikai ignorēt sakārtojumu. Šīs rīcības attaisnojums balstīts uz faktu, ka mēs jau zinām, cik dažādu kortežu  var iegūt – to skaits ir.

 

Tomēr ievērosim, ka konkrēto kopu I mēs varējām iegūt arī no sakārtota iztvēruma , kas atšķiras no  tikai ar elementu izvietojumu. Tātad kopas Ik iztvērums bez atkārtojumiem no kopas . Ņemot vērā iepriekšējās teorēmas speciālo gadījumu, secināms, ka vienu kopu Ik! dažādiem kortežiem . Tātad dažādo kopu skaits ir vienāds ar . konstrukcijai jāizvēlas jebkurš sakārtots apjoma mēs varam uzkonstruēt no