Šī 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