Atjaunots 2023. gada 20. janvārī
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

Saskaitīšanas (jeb summas) likums.

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 b₁, b₂..., b_mtā, ka nekādiem diviem no tiem nav kopīgu variantu, un, ja izvēlei b_i(i = 1, 2, ..., m) ir k_i varianti, tad pilno izvēli b var izdarīt k₁ + k₂ +...+ k_m 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 C_nⁱ veidos. Tātad patvaļīgu K apakškopu var izvēlēties Σ_i=₀ⁿ C_nⁱ 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 A₁, A₂, ..., A_m nav divu ar kopīgiem elementiem, tad

|A₁ ∪ A₂ ∪ ··· ∪ A_m| = |A₁| + |A₂| + ··· + |A_m|.

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 b_i var būt kopīgi varianti (jeb kopām A_i – kopīgi elementi). To parasti apraksta kopu valodā, kas ir ievērojami vienkāršāk.

Patvaļīgām kopām A₁, A₂, ..., A_m to apvienojuma elementu skaits ir

N₁ – N₂ + N₃– N₄ + ··· + (-1)^k--1N_k + ··· + (-1)^m--1N_m,

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

Elementu kopskaits visos i kopu šķēlumos.

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

N₁ = |A| + |B| + |C|,

N₂= |A ∩ B| + |A ∩ C| + |B ∩ C|,

N₃ = |A ∩ B ∩ C|.

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

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 k₁ varianti, bet pēc i-tā soļa (1 ≤ i < m) izpildes nākamo var izdarīt k_i₊₁ veidos, tad visai izvēlei b ir pavisam k₁k₂ ··· k_m 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ā k₁ = n), otro no pārējiem — n – 1 veidā (k₂ = n -- 1), trešo — n -- 2 veidos (k₃ = n -- 2) utt. Līdzīgi - sakārtotu izlašu skaits ar atkārtojumiem no n pa m ir n^m.

Likuma formulējums kopu teorijas valodā:

|A₁ × A₂ × ··· × A_m| = |A₁| × |A₂| × ··· × |A_m|.

(atgādne: kopu A₁, A₂, ..., A_m Dekarta reizinājums A₁× A₂ × ··· × A_m ir visu sakārtoto kortežu (a₁, a₂, ..., a_m) kopa, kur a_i pieder A_i, 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)

(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.

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

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 2ⁿ (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 C_n^k veidos. Bet šādu apkškopu kopai ir tikpat, cik to papildinājumu (tajos katrā tad ir n – k elementi), jo katrai apkš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 C_n^k = C_n^n-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 C_n^k 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 C_n^k 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 C_n-1^k-1. Otrā veida apakškopu skaits ir C_n-₁^k^. Rezultātā noskaidrots, ka C_n^k = C_n-₁^k-¹ + C_n-₁^k.

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=₀ⁿC_nⁱdažādu apakškopu. Skaitot citādi, sadaļā par vienlieluma principu bija parādīts, ka šis apakškopu skaits ir 2ⁿ. Ar to pierādīta vienādība Σ_i=₀ⁿC_nⁱ= 2ⁿ.

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.

Avots: Shutterstock.com.

Multivide

Saskaitīšanas (jeb summas) likums.

Elementu kopskaits visos i kopu šķēlumos.

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).

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.

kombinatorikas pamatprincipi

Saistītie šķirkļi

Saskaitīšanas (jeb summas) likums.

Satura rādītājs

Satura rādītājs

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).

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

Multivide

Autora ieteiktie papildu resursi

kombinatorikas pamatprincipi

Saistītie šķirkļi

Saskaitīšanas (jeb summas) likums.

Satura rādītājs

Satura rādītājs

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).

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

Multivide

Saistītie šķirkļi

Autora ieteiktie papildu resursi

Tīmekļa vietnes

Ieteicamā literatūra