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