AizvērtIzvēlne
Sākums
Atjaunots 2025. gada 7. jūlijā
Jānis Cīrulis

kombinatorikas pamatprincipi

(angļu basic principles of combinatorics, vācu Grundprinzipien der Kombinatorik, franču principes de base de la combinatoire, krievu основные принципы комбинаторики)
kombinatorikā biežāk lietotie fakti, likumi un metodes, ko izmanto konfigurāciju skaita aprēķinos un novērtējumos, kā arī dažādu vienādību pamatošanai

Saistītie šķirkļi

  • diskrētā matemātika
  • izlase, kombinatorikā
  • kombinatorika
Saskaitīšanas (jeb summas) likums.

Saskaitīšanas (jeb summas) likums.

Satura rādītājs

  • 1.
    Kopsavilkums
  • 2.
    Skaitīšanas principi
  • 3.
    Pierādīšanas metodes
  • 4.
    Vēsturiskas piezīmes
  • Multivide 5
  • Saistītie šķirkļi
  • Tīmekļa vietnes
  • Ieteicamā literatūra
  • Kopīgot
  • Izveidot atsauci
  • Drukāt

Satura rādītājs

  • 1.
    Kopsavilkums
  • 2.
    Skaitīšanas principi
  • 3.
    Pierādīšanas metodes
  • 4.
    Vēsturiskas piezīmes
Kopsavilkums

Kombinatorikas praksē ir svarīgi dažādus lietotus izvēļu variantu vai konfigurāciju skaitīšanas paņēmienus apzināt un formulēt vispārīgā veidā. Biežāk sastopamie ieguvuši kombinatorikas pamatprincipu nosaukumu. Daļa to ir acīmredzami, taču ir arī tādi, kas, kaut intuitīvi skaidri, faktiski ir nopietnas matemātiskas teorēmas. Gandrīz katram literatūrā atrodami dažādi paveidi un ekvivalenti formulējumi, dažreiz piemin arī tādus, kas ir divu vai vairāku principu vai to paveidu kombinējums vienā vispārīgā. 

Bez šiem t. s. skaitīšanas principiem kombinatorikas pamatprincipu klāstā dažkārt iekļauj arī pazīstamākās metodes vienādību atklāšanai un pamatošanai, un pat kombinatorisku virkņu apstrādei (rekurento sakarību un veidotājfunkciju metodes).

Skaitīšanas principi
Saskaitīšanas (jeb summas) likums

Formulējums. Ja kādu izvēli b (beta) var sadalīt m apakšgadījumos b1, b2 ..., bm tā, ka nekādiem diviem no tiem nav kopīgu variantu, un, ja izvēlei bi (i = 1, 2, ..., m) ir ki varianti, tad pilno izvēli b var izdarīt k1 + k2 +...+ km veidos.

Piemērs. Apakškopas izvēli n-elementu kopā K var sadalīt n + 1 vienkāršākos gadījumos (tā m = n + 1), kad apakškopā ir i elementi, i = 0,1, ..., n. Zināms, ka tādu apakškopu var izvēlēties Cni veidos. Tātad patvaļīgu K apakškopu var izvēlēties Σi=0n Cni veidos.

Pievēršot uzmanību izvēļu iznākumu kopām, saskaitīšanas likumam var dot līdzvērtīgu formulējumu kopu valodā (galīgai kopai X ar |X| apzīmē tās elementu skaitu): 

Ja starp kopām A1, A2, ..., Am nav divu ar kopīgiem elementiem, tad

|A1 ∪ A2 ∪ ··· ∪ Am| = |A1| + |A2| + ··· + |Am|.

Ieslēgšanas un izslēgšanas likums

Formulējums. Šis ir saskaitīšanas likuma vispārinājums gadījumam, kad tajā pieminētajām izlasēm bi var būt kopīgi varianti (jeb kopām Ai – kopīgi elementi). To parasti apraksta kopu valodā, kas ir ievērojami vienkāršāk.

Patvaļīgām kopām A1, A2, ..., Am to apvienojuma elementu skaits ir 

N1 – N2 + N3 – N4 + ··· + (-1)k--1Nk + ··· + (-1)m--1Nm,

kur Ni (i = 1,2, ..., m) ir elementu kopskaits visos kopu šķēlumos pa i, t. i.,

 Piemēram, trim kopām A,B,C,

N1 = |A| + |B| + |C|,

N2 = |A ∩ B| + |A ∩ C| + |B ∩ C|,

N3 = |A ∩ B ∩ C|.

Sareizināšanas (jeb reizinājuma) likums

Formulējums. Ja izvēles b (beta) procedūru var sadalīt m soļos un ja pirmajam solim ir k1 varianti, bet pēc i-tā soļa (1 ≤ i < m) izpildes nākamo var izdarīt ki+1 veidos, tad visai izvēlei b ir pavisam k1 k2 ··· km variantu. 

Piemērs. Sakārtotu izlašu bez atkārtojumiem skaits no n-elementu kopas pa m elementiem ir n(n – 1) ··· (n – m + 1): pirmo izlases locekli no kopas var izvēlēties n veidos (tā k1 = n), otro no pārējiem — n – 1 veidā (k2 = n -- 1), trešo — n -- 2 veidos (k3 = n -- 2) utt. Līdzīgi - sakārtotu izlašu skaits ar atkārtojumiem no n pa m ir nm.

Likuma formulējums kopu teorijas valodā:

|A1 × A2 × ··· × Am| = |A1| × |A2| × ··· × |Am|.

(atgādne: kopu A1, A2, ..., Am Dekarta reizinājums A1 × A2 × ··· × Am ir visu sakārtoto kortežu (a1, a2, ..., am) kopa, kur ai pieder Ai, bet i = 1, 2, ..., m).

Dalīšanas (jeb dalījuma) likums

Formulējums. Ja pavisam ir m dažādu darbību, kas katra beidzas ar kādu rezultātu, un pie ikviena no tiem noved tieši k darbības, tad dažādu iespējamo rezultātu skaits ir m/k. 

Piemērs. Ikvienu kādas kopas K r-elementu apakškopu var sastādīt, izvēloties tai citu aiz cita r dažādus elementus no K. Ja kopā ir n elementu, tā veidojas dažādas elementu virknes, kuru skaits pēc sareizināšanas likuma ir n(n – 1) ··· (n – r + 1), taču tās virknes, kas atšķiras vien ar locekļu secību, dod vienu un to pašu apakškopu. Virknē, kuras garums ir r, locekļus var samainīt vietām r! veidos (tā k = r!), tāpēc pašu apakškopu skaits pēc dalīšanas likuma ir:

n(n – 1) ··· (n – r + 1)

                 r!                

(Vienlaikus kombinatoriski pamatots šāds secinājums: jebkurš tāda izskata dalījums nozīmē veselu skaitli.)

Ekvivalents likuma formulējums kopu valodā ir: Ja m-elementu kopa ir vairāku savstarpēji šķirtu kopu apvienojums ar k elementiem katrā, tad kopu skaits ir m/k, un tas ir reizinājuma likuma divām kopām tiešas sekas.

Dirihlē princips

Formulējums. Ja n priekšmeti izvietoti pa m dažādām vietām un n > m, tad vismaz vienā vietā novietots vairāk nekā viens priekšmets. 

Šo principu parasti izmanto elementu skaita novērtējumiem kopā, arī eksistences pierādījumos.

Piemērs. Starp n veseliem skaitļiem vienmēr ir divi tādi, kuru starpība dalās ar n – 1. Pamatojums: dalot šos skaitļus ar n – 1, iespējamie atlikumi ir robežās starp un n – 2, tāpēc to (proti, atlikumu) skaits nepārsniedz n – 1. Taču pašu skaitļu ir n; pēc Dirihlē principa tad vismaz diviem no tiem ir vienādi atlikumi. Tas nozīmē, ka pašu šo divu skaitļu starpība dalās ar n – 1 bez atlikuma.

Vienlieluma (arī bijekcijas) princips

Atgādne: atbilstību starp divām kopām (to elementiem) sauc par savstarpēji viennozīmīgu jeb bijekciju, ja katram vienas kopas elementam atbilst kāds otras kopas elements, pie kam dažādiem pirmās kopas elementiem atbilst dažādi elementi otrajā kopā un katrs otrās kopas elements atbilst kādam elementam pirmajā kopā. Ja tāda atbilstība pastāv, saka, ka kopas ir vienlielas.

Princips nosaka, ka vienlielām galīgām kopām ir vienāds elementu skaits. 

Tas pats princips izvēlēm: ja starp divu izvēļu iznākumiem pastāv kāda atbilstība, kas ir savstarpēji viennozīmīga, un ja vienu no abām izvēlēm var izdarīt n veidos, tad arī otru var izdarīt n veidos. 

Šo principu elementu skaitīšanā bieži izmanto tā: lai noskaidrotu elementu skaitu kādā kopā, nodibina savstarpēji viennozīmīgu atbilstību starp šo kopu un citu, kuras elementu skaits jau zināms vai tie parocīgāki skaitīšanai.

Piemērs. Lai saskaitītu kādas n-elementu kopas visas apakškopas, tās elementus iedomājas sanumurētus. Tad katru apakškopu var attēlot ar n-locekļu bināru (t. i., no nullēm un vieniniekiem sastāvošu) virkni: ja i-tais kopas elements pieder apakškopai, par virknes i-to locekli ņem 1, pretējā gadījumā 0. Redzams, ka dažādām kopām atbilstošās virknes arī ir dažādas, un katra bināra virkne tiešām attēlo kādu apakškopu. Visu šo virkņu skaits ir 2n (pēc reizināšanas principa), un tas tad ir arī visu apakškopu skaits.

Pierādīšanas metodes
Vienlieluma (arī bijekcijas) metode

Tā balstās uz iepriekš iztirzāto vienlieluma principu.

Formulējums. Lai pierādītu, ka divas izteiksmes ir skaitliski vienādas, parāda, ka tās attiecīgi nozīmē elementu skaitu divās kopās, kas ir vienlielas.

Piemērs. Zināms, ka n-elementu kopā A kādu tās k-elementu apakškopu var izvēlēties Cnk veidos. Bet šādu apakškopu kopai ir tikpat, cik to papildinājumu (tajos katrā tad ir n – k elementi), jo katrai apakškopai ir tieši viens papildinājums un katra (n – k)-elementu apakškopa ir kādas k-elementu kopas papildinājums. Tā nonāk pie vienādības Cnk = Cnn-k.

Iezīmētā elementa metode

Tā ir konkrēts paņēmiens, kā izmantot saskaitīšanas likumu (divām kopām), un ir noderīga dažos kombinatoriskos pierādījumos. 

Formulējums. Lai nonāktu pie kāda noteikta veida konfigurāciju skaita, izraugās kādu pamatkopas elementu un tad saskaita atsevišķi tās konfigurācijas, kas šo elementu satur, un tās, kas to nesatur. Pēc saskaitīšanas principa abu skaitu summa dod visu konfigurāciju kopskaitu.

Piemērs. Zināms, ka n-elementu kopai A ir Cnk k-elementu apakškopas. Tās var saskaitīt šādi: izraugās patvaļīgu kopas elementu a un saskaita, cik kopai ir to k-apakškopu, kas šo elementu satur, un cik ir to, kas nesatur; tātad Cnk ir abu skaitu summa. Pēc vienlieluma principa, pirmā veida apakškopu skaits sakrīt ar (k – 1)-elementu apakškopu skaitu kopai A∖{a}; tas ir Cn-1k-1. Otrā veida apakškopu skaits ir Cn-1k. Rezultātā noskaidrots, ka Cnk = Cn-1k-1 + Cn-1k.

Divkāršas skaitīšanas metode

Formulējums. Lai pierādītu, ka divas izteiksmes ir skaitliski vienādas, parāda, ka tās atspoguļo kādas kopas elementu skaita aprēķinus atbilstoši diviem dažādiem to skaitīšanas veidiem.

Piemērs. Sadaļā par saskaitīšanas likumu bija parādīts, ka n-elementu kopai ir Σi=0n Cni dažādu apakškopu. Skaitot citādi, sadaļā par vienlieluma principu bija parādīts, ka šis apakškopu skaits ir 2n. Ar to pierādīta vienādība Σi=0n Cni = 2n.

Vēsturiskas piezīmes

Ir ziņas, ka arābu matemātiķi jau 10. un 11. gs. mijā prata skaitīt sakārtotas izlases, tātad lietoja sareizināšanas likumu. Ieslēgšanas un izslēgšanas principu saista ar Abrāmu de Muavru (Abraham de Moivre; 18. gs.), tomēr publikācijās tas pirmoreiz parādās 1854. gadā (Daniels da Silva, Daniel da Silva), pēc tam 1883. gadā (Džeimss Silvestrs, James Joseph Sylvester), un attiecīgo vienādību joprojām dažkārt sauc par Silvas jeb Silvestra formulu.

Dirihlē princips literatūrā apspriests jau 17. gs. 20. gados (Žans Lerešons, Jean Leurechon). Tā mūsdienu nosaukums radies pēc 1834. gada, kad Pēters Dirihlē (Peter Gustav Lejeune Dirichlet) iztirzāja to vairākos rakstos gan vācu, gan franču valodās ar nosaukumu attiecīgi vācu valodā Schubfachprinzip, franču valodā principe des tiroirs, ko var tulkot kā ‘atvilktņu princips’. Šāds principa nosaukums ir sastopams vairākās Eiropas valodās. To bieži sauc arī par baložbūru principu (arī vācu valodā) – pēc angļu pigeonhole principle, kaut gan, jādomā, tas radies pārpratuma pēc, jo angļu valodā pigeonhole nozīmē arī nelielu atvilktni dokumentu glabāšanai. 

Dirihlē princips: ja desmit baloži jāizvieto deviņos būros, tad vismaz vienā būrī to būs vairāk nekā viens.

Dirihlē princips: ja desmit baloži jāizvieto deviņos būros, tad vismaz vienā būrī to būs vairāk nekā viens.

Avots: Shutterstock.com. 

Multivide

Saskaitīšanas (jeb summas) likums.

Saskaitīšanas (jeb summas) likums.

Elementu kopskaits visos i kopu šķēlumos.

Elementu kopskaits visos i kopu šķēlumos.

Ieslēgšanas un izslēgšanas principa trim kopām ilustrācija.

Ieslēgšanas un izslēgšanas principa trim kopām ilustrācija.

Sareizināšanas un dalīšanas likumi darbībā: no katras n-stūra virsotnes var vilkt n - 3 diagonāles; kopā n(n - 3)). Bet tad katra novilkta divreiz, tātad tam pavisam ir n(n - 3) / 2 diagonāļu (sešstūrim deviņas).

Sareizināšanas un dalīšanas likumi darbībā: no katras n-stūra virsotnes var vilkt n - 3 diagonāles; kopā n(n - 3)). Bet tad katra novilkta divreiz, tātad tam pavisam ir n(n - 3) / 2 diagonāļu (sešstūrim deviņas).

Dirihlē princips: ja desmit baloži jāizvieto deviņos būros, tad vismaz vienā būrī to būs vairāk nekā viens.

Dirihlē princips: ja desmit baloži jāizvieto deviņos būros, tad vismaz vienā būrī to būs vairāk nekā viens.

Avots: Shutterstock.com. 

Saskaitīšanas (jeb summas) likums.

Saistītie šķirkļi:
  • kombinatorikas pamatprincipi
Izmantošanas tiesības
Skatīt oriģinālu

Saistītie šķirkļi

  • diskrētā matemātika
  • izlase, kombinatorikā
  • kombinatorika

Autora ieteiktie papildu resursi

Tīmekļa vietnes

  • Dirihlē princips (Pigeonhole Principle)
  • Par un ap ieslēgšanas un izslēgšanas principu (Формула включений и исключений)
  • Rekurentās sakarības. Piemēri un uzdevumi (Big-Oh for Recursive Functions: Recurrence Relations)
  • Veidotājfunkcijas. Lietojumu piemēri (Generating Functions)

Ieteicamā literatūra

  • Rosen, K.H., Shier, D.R., Goddard, W. (eds.), Handbook of discrete and combinatorial mathematics, 2nd edn., Boca Raton, FL, CRC Press, 2018.
    Skatīt bibliotēku kopkatalogā
  • Sagan, B.E., Combinatorics, The Art of Counting, Rhode Island, American Mathematical Society, Providence, 2020.
  • Strazdiņš, I., Diskrētās matemātikas pamati, Rīga, Zvaigne, 1980 (3.2 paragrāfs).
    Skatīt bibliotēku kopkatalogā

Jānis Cīrulis "Kombinatorikas pamatprincipi". Nacionālā enciklopēdija. https://enciklopedija.lv/skirklis/114942-kombinatorikas-pamatprincipi (skatīts 26.09.2025)

Kopīgot


Kopīgot sociālajos tīklos


URL

https://enciklopedija.lv/skirklis/114942-kombinatorikas-pamatprincipi

Šobrīd enciklopēdijā ir 0 šķirkļi,
un darbs turpinās.
  • Par enciklopēdiju
  • Padome
  • Nozaru redakcijas kolēģija
  • Ilustrāciju redakcijas kolēģija
  • Redakcija
  • Sadarbības partneri
  • Atbalstītāji
  • Sazināties ar redakciju

© Latvijas Nacionālā bibliotēka, 2025. © Tilde, izstrāde, 2025. © Orians Anvari, dizains, 2025. Autortiesības, datu aizsardzība un izmantošana