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

Permutācijas

 

Jānis, kā parasti, ieradās savas klases diskotēkā, mājas ballītē, kur priekšā jau bija Pēteris, Kārlis, Kristaps, Ilze, Anniņa, Silvija un Mārīte. Ballītes sākumā viņi iedomājās paspēlēt rotaļu, cik dažādi viņi var apsēsties uz Kārļa mājās gar sienu noliktos krēslos. Izrādījās, ka jebkura pārvietošanās ir jauna dažādība, un ka var sēsties un sēsties, bet gala kā nav tā nav. Pēc kāda brīža Jānim apnika un viņš sāka rēķināt, cik ilgi viņiem nāksies nodarboties ar jautri iesākto, bet nu jau apnicīgo rotaļu. Izrādījās, ka tas ir milzu skaitlis, un tāpēc šo nodarbi ātri pārtrauca. Jāni var apsēdināt 8 krēslos, Pēteri jau tālāk 7 krēslos, Anniņu 6 utt., kamēr Marītei paliek tikai viens krēsls. Šo sēdināšanu matemātiķi sauc par permutāciju, un tā nav atkarīga no sēdināšanas kārtības, bet krēsliem gan ir jābūt dažādiem.

 

 

Sakārtoti iztvērumi (variācijas)

 

Tālāk sākās dejas, kur, kā izrādījās, arī bija dažādas iespējas visiem dejot pa pāriem. Jānis dejoja ar Anniņu, tad ar Ilzīti, tad ar... Kārlis darīja tāpat, un kādā starpbrīdī viņi sāka rēķināt, cik dejas ir jānodejo, lai katrs puisis padejotu ar katru meiteni, pie kam būtu jādejo visiem. Katram ir jāizdancina pārējie, un, ja Jānis uzlūdz Ilzi, tad tas nenozīmē, ka Ilze ir uzlūgusi Jāni, un tāpēc viņai Jāni savukārt ir jālūdz dāmu dejā. Lai visa bilde būtu pilnīga, izrādījās, ka puišiem un meitenēm tāpat ir jādejo savā starpā, lai matemātiķi varētu nosaukt šo gadījumu par variācijām no 8 pa 2.

 

 

Nesakārtoti iztvērumi (kombinācijas)

 

Jānim nepatika arī variācijas, jo tas bija un palika par garu. Tik liels matemātikas entuziasts viņš nebija. Tāpēc viņam ienāca prātā ballītes jautrās idejas mazliet saīsināt. Viņš izdomāja, ka Ilzītes dāmu deja nekādu jaunu pāri neradīs, ja Jānis būs paspējis viņu izdancināt. Tāpat Anniņas jautrā tarantella ar Mārīti skaitās tikai vienreiz, jo Mārītes tarantellu ar Anniņu uzskatīs par vienu un to pašu. Taču arī šoreiz iznāca, ka kaukāziešu vai grieķu dejas nācās dejot savstarpēji arī puišiem, meitenēm arī. Šo mazāka pāru skaita iegūšanas veidu matemātiķi sauc par kombinācijām no 8 pa 2.

 

Saprotams, ka var veidot dažādas grupiņas no 8 pa 3 vai 5 utt. Tāpat var būt nevis 8, bet 600 cilvēku utt..

 

 

Modeļi:
Kombinatorika Reitings: 4 Skatījumi: 2378 +

Autors: Anonīms Klase: -
1 2