Iespējamās kombinācijas. Kombinatorikas elementi
Kombinācija ir ierobežotas kopas elementu nesakārtota atlase ar fiksētu skaitu un bez elementu atkārtojumiem. Dažādām kombinācijām ir jāatšķiras vismaz vienā elementā, un elementu secībai nav nozīmes. Piemēram, no visu latīņu burtu patskaņu kopas (AEIOU) varat izveidot 10 dažādas 3 burtu kombinācijas, veidojot šādus nesakārtotus trīskāršus:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Interesanti atzīmēt, ka no tiem pašiem pieciem burtiem var iegūt arī 10 dažādas kombinācijas, ja tos apvienojat pa 2 burtiem vienlaikus, veidojot šādus nesakārtotus pārus:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
Tomēr, ja jūs apvienojat tos pašus patskaņu latīņu burtus ar 4, jūs iegūsit tikai šādas 5 dažādas kombinācijas:
AEIO, AEIU, AIOU, EIOU, AEOU.
Kopumā, lai apzīmētu n dažādu m elementu elementu kombināciju skaitu, tiek izmantota šāda funkcionālā, indeksa vai vektora (Appel) simbolika:
Neatkarīgi no apzīmējuma formas n elementu kombināciju skaitu ar m elementiem var noteikt, izmantojot šādas reizināšanas un faktoru formulas:
Ir viegli pārbaudīt, vai aprēķinu rezultāts, izmantojot šīs formulas, sakrīt ar iepriekš apskatītā piemēra rezultātiem ar patskaņu kombinācijām latīņu burtiem. Konkrēti, ja n=5 un m=3, aprēķini, izmantojot šīs formulas, dos šādu rezultātu:
Vispārīgā gadījumā kombināciju skaita formulām ir kombinatoriska nozīme, un tās ir derīgas jebkuram veselam skaitlim n un m, lai n > m > 0. Ja m > n un m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
Turklāt ir lietderīgi atcerēties šādus ierobežojošos kombināciju skaitu, ko var viegli pārbaudīt, tieši aizstājot reizināšanas un faktoriālās formulas:
Jāņem vērā arī tas, ka reizināšanas formula paliek spēkā pat tad, ja n ir reāls skaitlis, kamēr m joprojām ir vesels skaitlis. Taču tad aprēķina rezultāts, izmantojot to, saglabājot formālo derīgumu, zaudē savu kombinatorisko nozīmi.
KOMBINĀCIJU IDENTITĀTES
Reizināšanas un faktoriālo formulu praktiskā izmantošana, lai noteiktu kombināciju skaitu patvaļīgām vērtībām n un m, izrādās maz produktīva, jo to skaitītāja un saucēja faktoriālie reizinājumi pieaug eksponenciāli. Pat salīdzinoši nelielām n un m vērtībām šie produkti bieži vien pārsniedz veselu skaitļu attēlošanas iespējas mūsdienu skaitļošanas un programmatūras sistēmās. Turklāt to vērtības izrādās ievērojami lielākas par iegūto kombināciju skaita vērtību, kas var būt salīdzinoši maza. Piemēram, n=10 ar m=8 elementiem kombināciju skaits ir tikai 45. Tomēr, lai atrastu šo vērtību, izmantojot faktoru formulu, vispirms jāaprēķina daudz lielākas vērtības 10! skaitītājā un 8! saucējā:
Lai novērstu laikietilpīgas darbības lielu daudzumu apstrādei, lai noteiktu kombināciju skaitu, var izmantot dažādas atkārtošanās attiecības, kas tieši izriet no reizināšanas un faktoru formulām. Jo īpaši no reizināšanas formulas izriet šāda atkārtošanās attiecība, kas ļauj ņemt tās indeksu attiecību ārpus kombināciju skaita zīmes:
Visbeidzot, saglabājot apakšindeksa konstantu, tiek iegūta šāda atkārtošanās sakarība, ko viegli iegūt no kombināciju skaita faktoriālās formulas:
Pēc elementārām transformācijām trīs iegūtās atkārtošanās attiecības var attēlot šādās formās:
Ja tagad saskaitām pirmo 2 formulu kreiso un labo pusi un samazinām rezultātu par n, iegūstam svarīgu atkārtošanās sakarību, ko sauc par kombinācijas skaitļu pievienošanas identitāti:
Saskaitīšanas identitāte nodrošina pamata atkārtošanās noteikumu, lai efektīvi noteiktu kombināciju skaitu lielām n un m vērtībām, jo tā ļauj reizināšanas darbības faktoriālos reizinājumus aizstāt ar vienkāršākām saskaitīšanas darbībām un mazākam kombināciju skaitam. Jo īpaši, izmantojot pievienošanas identitāti, tagad ir viegli noteikt kombināciju skaitu n=10 ar m=8 elementiem, kas tika apspriests iepriekš, veicot šādu atkārtotu transformāciju secību:
Turklāt no saskaitīšanas identitātes var iegūt vairākas noderīgas attiecības galīgo summu aprēķināšanai, jo īpaši formulas summēšanai pēc apakšindeksa, kurai ir šāda forma:
Šī sakarība tiek iegūta, ja pievienošanas identitātē atkārtošanos izvēršam gar vārdu ar lielāko augšindeksu, kamēr tā apakšindekss ir lielāks par 0. Šis skaitliskais piemērs ilustrē šo atkārtoto transformāciju procesu:
Apakšindeksi summēšanas formulu bieži izmanto, lai aprēķinātu naturālu skaitļu pakāpju summu. Konkrēti, pieņemot, ka m=1, izmantojot šo formulu, ir viegli atrast naturālās rindas pirmo n skaitļu summu:
Vēl vienu noderīgu summēšanas formulas versiju var iegūt, paplašinot pievienošanas identitātes atkārtošanos gar terminu ar mazāko augšējo indeksu. Šis skaitlisks piemērs ilustrē šo atkārtoto transformāciju versiju:
Vispārīgā gadījumā šādu pārveidojumu rezultātā tiek iegūta to kombināciju skaitļu summa, kuru abi indeksi par vienu atšķiras no blakus esošajiem vārdiem, un indeksu atšķirība paliek nemainīga (aplūkotajā piemērā tā ir arī vienāds ar vienu). Tādējādi abiem kombinācijas skaitļu indeksiem iegūstam šādu summēšanas formulu:
Papildus iepriekš apskatītajām atkārtošanās relācijām un summēšanas formulām kombinatoriskajā analīzē ir iegūtas daudzas citas noderīgas kombinācijas skaitļu identitātes. Vissvarīgākais starp tiem ir simetrijas identitāte, kas izskatās šādi:
Simetrijas identitātes derīgumu var pārbaudīt šajā piemērā, salīdzinot 5 elementu kombināciju skaitu ar 2 un ar (5 2) = 3:
Simetrijas identitātei ir acīmredzama kombinatoriska nozīme, jo, nosakot opciju skaitu m elementu atlasei no n elementiem, tā vienlaikus nosaka kombināciju skaitu no atlikušajiem (nm) neatlasītajiem elementiem. Norādīto simetriju uzreiz iegūst, kombināciju skaita faktoru formulā aizstājot m ar (nm):
Cipari un kombināciju identitātes tiek plaši izmantotas dažādās mūsdienu skaitļošanas matemātikas jomās. Tomēr to populārākie lietojumi ir saistīti ar Ņūtona binomiālu un Paskāla trīsstūri.
BINOMĀLA TEORĒMA
Lai veiktu dažādas matemātiskas transformācijas un aprēķinus, ir svarīgi prast jebkuru algebriskā binoma (binoma) dabisko jaudu polinoma formā. Mazām pakāpēm vēlamo polinomu var viegli iegūt, tieši reizinot binomiālus. Jo īpaši no elementārās matemātikas kursa ir labi zināmas šādas divu terminu summas kvadrāta un kuba formulas:
Vispārīgā gadījumā patvaļīgai binoma pakāpei n nepieciešamo attēlojumu polinoma formā nodrošina Ņūtona binoma teorēma, kas pasludina šādu vienādību par patiesu:
Šo vienādību parasti sauc par Ņūtona binomiālu. Polinomu tā labajā pusē veido kreisās puses binoma n vārdu X un Y reizinājumu summa, un tiem priekšā esošie koeficienti tiek saukti par binomiālu un ir vienādi ar kombināciju skaitu ar indeksiem, kas tiek iegūti no viņu pilnvarām. Ņemot vērā Ņūtona binomiālās formulas īpašo popularitāti kombinatoriskajā analīzē, termini binomiālais koeficients un kombināciju skaits parasti tiek uzskatīti par sinonīmiem.
Acīmredzot kvadrātu un kubu summas formulas ir īpaši binomiālās teorēmas gadījumi attiecīgi n=2 un n=3. Lai apstrādātu augstākus grādus (n>3), jāizmanto Ņūtona binomiālā formula. Tā pielietojums ceturtās pakāpes binomiālam (n=4) ir parādīts ar šādu piemēru:
Jāpiebilst, ka binominālā formula bija zināma jau pirms Ņūtona viduslaiku arābu austrumu un Rietumeiropas matemātiķiem. Tāpēc tā vispārpieņemtais nosaukums nav vēsturiski pareizs. Ņūtona nopelns ir tas, ka viņš vispārināja šo formulu patvaļīga reālā eksponenta r gadījumam, kas var iegūt jebkuras pozitīvas vai negatīvas racionālas un iracionālas vērtības. Vispārīgā gadījumā šādai Ņūtona binoma formulai labajā pusē ir bezgalīga summa, un to parasti raksta šādi:
Piemēram, ar pozitīvu eksponenta daļu vērtību r=1/2, ņemot vērā binomiālo koeficientu vērtības, tiek iegūts šāds paplašinājums:
Vispārīgā gadījumā Ņūtona binomiālā formula jebkuram eksponentam ir īpaša Maklorina formulas versija, kas dod patvaļīgas funkcijas izvēršanu pakāpju rindā. Ņūtons parādīja, ka |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Ja tagad iestatām Z=X/Y un reizinām kreiso un labo pusi ar Yn, mēs iegūstam iepriekš apskatītās Ņūtona binominālās formulas versiju.
Neskatoties uz tās universālumu, binoma teorēma saglabā savu kombinatorisko nozīmi tikai binoma nenegatīviem veseliem skaitļiem. Šajā gadījumā to var izmantot, lai pierādītu vairākas noderīgas binomiālo koeficientu identitātes. Jo īpaši iepriekš tika apspriestas formulas kombināciju skaita summēšanai pēc apakšindeksa un abiem indeksiem. Trūkstošo virsraksta summēšanas identitāti var viegli iegūt no Ņūtona binominālās formulas, ievietojot tajā X = Y = 1 vai Z = 1:
Vēl viena noderīga identitāte nosaka binominālo koeficientu summu vienādību ar pāra un nepāra skaitļiem. To uzreiz iegūst no Ņūtona binominālās formulas, ja X = 1 un Y = 1 vai Z = 1:
Visbeidzot, no abām aplūkotajām identitātēm mēs iegūstam binominālo koeficientu summas identitāti tikai ar pāra vai tikai nepāra skaitļiem:
Balstoties uz aplūkotajām identitātēm un atkārtojošo noteikumu par indeksu izņemšanu no zem kombināciju skaita zīmes, var iegūt vairākas interesantas attiecības. Piemēram, ja virsraksta summēšanas formulā n visur aizstājam ar (n1) un noņemam indeksus katrā terminā, mēs iegūstam šādu sakarību:
Izmantojot līdzīgu paņēmienu binominālo koeficientu summas formulā ar pāra un nepāra skaitļiem, ir iespējams pierādīt, piemēram, šādas attiecības derīgumu:
Vēl viena noderīga identitāte ļauj viegli aprēķināt divu patvaļīgu n un k binomiālu binomiālu koeficientu reizinājumu summu, izmantojot šādu Košī formulu:
Šīs formulas derīgums izriet no nepieciešamās koeficientu vienādības jebkurai mainīgā Z pakāpei m, kas atrodas šādas identiskas attiecības kreisajā un labajā pusē:
Īpašā gadījumā, kad n=k=m, ņemot vērā simetrijas identitāti, iegūst populārāku binomiālo koeficientu kvadrātu summas formulu:
Plašajā kombinatoriskās analīzes literatūrā var atrast daudzas citas noderīgas binomiālo koeficientu identitātes. Tomēr viņu slavenākais praktiskais pielietojums ir saistīts ar Paskāla trīsstūri.
PASKĀLA Trijstūris
Paskāla aritmētiskais trīsstūris veido bezgalīgu skaitlisko tabulu, kas sastāv no binomiāliem koeficientiem. Tās līnijas ir sakārtotas pēc binomiālu pakāpēm no augšas uz leju. Katrā rindā binomiālie koeficienti ir sakārtoti atbilstošo kombināciju skaitļu augšējo indeksu augošā secībā no kreisās uz labo. Paskāla trīsstūri parasti raksta vienādsānu vai taisnstūrveida formā.
Vizuālāks un izplatītāks ir vienādsānu formāts, kur binomiālie koeficienti, sakārtoti, veido bezgalīgu vienādsānu trīsstūri. Tā sākotnējam fragmentam binomiem līdz 4. pakāpei (n=4) ir šāda forma:
Kopumā Paskāla vienādsānu trijstūris nodrošina ērtu ģeometrisko noteikumu binomiālo koeficientu noteikšanai, kura pamatā ir saskaitīšanas identitātes un skaitļu kombināciju simetrija. Konkrēti, saskaņā ar saskaitīšanas identitāti jebkurš binominālais koeficients ir tai tuvākās iepriekšējās rindas divu koeficientu summa. Saskaņā ar simetrijas identitāti Paskāla vienādsānu trīsstūris ir simetrisks attiecībā pret tā bisektoru. Tādējādi katra tā līnija ir binomiālo koeficientu skaitlisks palindroms. Norādītās algebriskās un ģeometriskās īpašības ļauj viegli paplašināt Paskāla vienādsānu trīsstūri un konsekventi atrast patvaļīgu pakāpju binomiālo koeficientu vērtības.
Tomēr, lai pētītu dažādas Paskāla trīsstūra īpašības, ērtāk ir izmantot formāli stingrāko taisnstūra formātu. Šajā formātā to nosaka zemāka binomiālo koeficientu trīsstūrveida matrica, kur tie veido bezgalīgu taisnleņķa trīsstūri. Sākotnējam Paskāla taisnleņķa trijstūra fragmentam binomiem līdz 9. pakāpei (n=9) ir šāda forma:
Ģeometriski šādu taisnstūrveida tabulu iegūst, horizontāli deformējot Paskāla vienādsānu trīsstūri. Rezultātā skaitļu rindas, kas ir paralēlas Paskāla vienādsānu trijstūra sānu malām, pārvēršas par Paskāla taisnstūra trīsstūra vertikālēm un diagonālēm, un abu trīsstūru horizontālās līnijas sakrīt. Tajā pašā laikā binomiālo koeficientu saskaitīšanas un simetrijas noteikumi paliek spēkā, lai gan Paskāla taisnleņķa trīsstūris zaudē vizuālo simetriju, kas raksturīgs tā vienādsānu līdziniekam. Lai to kompensētu, kļūst ērtāk formāli analizēt Paskāla taisnleņķa trīsstūra horizontālo, vertikālo un diagonāļu binomiālo koeficientu dažādās skaitliskās īpašības.
Sākot Paskāla taisnleņķa trijstūra horizontu analīzi, ir viegli pamanīt, ka jebkuras rindas ar skaitli n elementu summa ir vienāda ar 2n saskaņā ar formulu binomiālu summēšanai ar augšējo indeksu. No tā izriet, ka elementu summa virs jebkuras horizontālās līnijas ar skaitli n ir vienāda ar (2 n 1). Šis rezultāts kļūst diezgan acīmredzams, ja katras horizontālās elementu summas vērtību ieraksta binārajā skaitļu sistēmā. Piemēram, ja n=4 šo papildinājumu var uzrakstīt šādi:
Šeit ir vēl dažas interesantas horizontāļu īpašības, kas ir saistītas arī ar divu pakāpēm. Izrādās, ja horizontālais skaitlis ir divnieka pakāpums (n=2 k), tad visi tā iekšējie elementi (izņemot ārējos) ir pāra skaitļi. Gluži pretēji, visi horizontālās līnijas skaitļi būs nepāra, ja tās skaitlis ir par vienu mazāks par pakāpju divi (n=2 k 1). Šo īpašību derīgumu var pārbaudīt, pārbaudot iekšējo binomiālo koeficientu paritāti, piemēram, horizontālēs n=4 un n=3 vai n=8 un n=7.
Tagad Paskāla taisnleņķa trijstūra rindas numurs ir pirmskaitlis p. Tad visi tā iekšējie binomiālie koeficienti dalās ar p. Šo īpašību ir viegli pārbaudīt, vai ir nelielas primāro kontūru skaitļu vērtības. Piemēram, visi piektās horizontālās daļas iekšējie binomiālie koeficienti (5, 10 un 5) acīmredzami dalās ar 5. Lai pierādītu šo rezultātu jebkuram primārajam horizontālajam skaitlim p, tā binominālo koeficientu reizināšanas formula ir jāuzraksta šādi:
Tā kā p ir pirmskaitlis un tāpēc nedalās ar m!, tad šīs formulas skaitītāja atlikušo faktoru reizinājumam ir jādalās ar m!, lai garantētu binominālā koeficienta veselu skaitļu vērtību. No tā izriet, ka attiecība kvadrātiekavās ir naturāls skaitlis N un vēlamais rezultāts kļūst acīmredzams:
Izmantojot šo rezultātu, varam konstatēt, ka visu Paskāla trijstūra horizontālo līniju skaitļi, kuru iekšējie elementi dalās ar doto pirmskaitli p, ir p pakāpes, tas ir, tiem ir forma n=p k. Konkrēti, ja p=3, tad pirmskaitlis p dala ne tikai visus 3. rindas iekšējos elementus, kā noteikts iepriekš, bet, piemēram, 9. horizontāli (9, 36, 84 un 126). No otras puses, Paskāla trīsstūrī nav iespējams atrast horizontālu līniju, kuras iekšējie elementi dalās ar saliktu skaitli. Pretējā gadījumā šādas horizontālas līnijas skaitam vienlaikus jābūt saliktā skaitļa pirmreizējo dalītāju pakāpei, ar kuru tiek dalīti visi tās iekšējie elementi, taču tas nav iespējams acīmredzamu iemeslu dēļ.
Apsvērtie apsvērumi ļauj formulēt šādu vispārīgo Paskāla trijstūra horizontālo elementu dalāmības kritēriju. Jebkuras Paskāla trijstūra horizontālas līnijas ar skaitli n visu iekšējo elementu lielākais kopējais dalītājs (GCD) ir vienāds ar pirmskaitli p, ja n=pk vai 1 visos citos gadījumos:
GCD(Cmn) = ( ) jebkuram 0< m < n .
Horizontāšu analīzes noslēgumā ir vērts apsvērt vēl vienu interesantu īpašību, kas piemīt tās veidojošajām binomiālo koeficientu sērijām. Ja jebkuras horizontālas līnijas ar skaitli n binomiālos koeficientus reizina ar skaitļa 10 secīgām pakāpēm un pēc tam saskaita visus šos reizinājumus, rezultāts ir 11 n. Formālais šī rezultāta pamatojums ir vērtību X=10 un Y=1 (vai Z=1) aizstāšana ar Ņūtona binominālo formulu. Šis skaitlisks piemērs ilustrē šīs īpašības izpildi n=5:
Paskāla taisnleņķa trijstūra vertikālu īpašību analīzi var sākt ar to veidojošo elementu individuālo īpašību izpēti. Formāli katru vertikāli m veido šāda bezgalīga binoma koeficientu secība ar nemainīgu augšējo indeksu (m) un apakšindeksa pieaugumu:
Acīmredzot, kad m=0 tiek iegūta vieninieku virkne, un kad m=1 veidojas naturālu skaitļu virkne. Ja m = 2, vertikāli veido trīsstūrveida skaitļi. Katru trīsstūra skaitli var attēlot plaknē vienādmalu trīsstūra formā, kas ir piepildīta ar patvaļīgiem objektiem (kodoliem), kas sakārtoti šaha zīmē. Šajā gadījumā katra trīsstūra skaitļa T k vērtība nosaka attēlojošo kodolu skaitu, un indekss parāda, cik kodolu rindu ir nepieciešams, lai to attēlotu. Piemēram, 4 sākotnējie trīsstūrveida skaitļi apzīmē šādas atbilstošā skaita kodola simbolu "@" konfigurācijas:
Jāņem vērā, ka līdzīgā veidā var ņemt vērā kvadrātskaitļus S k , kas iegūti, izliekot kvadrātā naturālus skaitļus, un kopumā daudzstūru skaitļus, kas veidoti, regulāri aizpildot regulārus daudzstūrus. Konkrēti, 4 sākotnējos kvadrātu skaitļus var attēlot šādi:
Atgriežoties pie Paskāla trijstūra vertikālu analīzes, var atzīmēt, ka nākamā vertikāle pie m=3 ir piepildīta ar tetraedriskiem (piramīdas) skaitļiem. Katrs šāds skaitlis P k norāda serdeņu skaitu, ko var izkārtot tetraedra formā, un indekss nosaka, cik horizontāli trīsstūrveida serdeņu rindu slāņi ir nepieciešami, lai to attēlotu trīsdimensiju telpā. Šajā gadījumā visi horizontālie slāņi ir jāattēlo kā secīgi trīsstūrveida skaitļi. Turpmāko Paskāla trijstūra vertikālu elementi m>3 veido hipertetraedālu skaitļu virkni, kurām nav vizuālas ģeometriskas interpretācijas plaknē vai trīsdimensiju telpā, bet formāli atbilst trijstūra un tetraedāla skaitļu daudzdimensiju analogiem.
Lai gan Paskāla trijstūra vertikālajām skaitļu sērijām ir aplūkotās individuālās formas pazīmes, tām ir iespējams aprēķināt sākotnējo elementu vērtību daļējās summas tādā pašā veidā, izmantojot formulu kombināciju skaitļu summēšanai pēc apakšindeksa . Paskāla trijstūrī šai formulai ir šāda ģeometriskā interpretācija. Jebkuras vertikāles n augšējo binoma koeficientu vērtību summa ir vienāda ar nākamās vertikāles elementa vērtību, kas atrodas vienu rindiņu zemāk. Šis rezultāts atbilst arī trīsstūrveida, tetraedru un hipertetraedu skaitļu ģeometriskajai struktūrai, jo katra šāda skaitļa attēlojums sastāv no pamata slāņiem, kas attēlo zemākus kārtas numurus. Jo īpaši n-to trīsstūra skaitli Tn var iegūt, summējot visus naturālos skaitļus, kas attēlo tā lineāros slāņus:
Tāpat nav grūti atrast tetraedrisko skaitli Pn, aprēķinot šādu pirmo n trīsstūrveida skaitļu summu, kas veido tā horizontālos serdes slāņus:
Papildus horizontālēm un vertikālēm Paskāla taisnleņķa trijstūrī var izsekot elementu diagonālās rindas, kuru īpašību izpēte arī rada zināmu interesi. Šajā gadījumā parasti izšķir dilstošās un augošās diagonāles. Lejupvērstās diagonāles ir paralēlas Paskāla taisnleņķa trijstūra hipotenūzai. Tos veido binomiālo koeficientu sērijas ar abu indeksu pieaugumu. Simetrijas identitātes dēļ dilstošās diagonāles to elementu vērtībās sakrīt ar atbilstošajām Paskāla trijstūra vertikālajām rindām un tāpēc atkārto visas iepriekš apskatītās īpašības. Norādīto atbilstību var izsekot pēc dilstošās diagonāles un vertikāles elementu vērtību sakritības ar jebkuru skaitli n, ja neņem vērā vertikālās nulles:
Augošas diagonāles veido skaitļu virkni ģeometriski perpendikulāri Paskāla taisnleņķa trijstūra hipotenūzai. Tie ir aizpildīti ar binomiāliem koeficientiem, samazinot augšējo indeksu un palielinot to. Jo īpaši 7 augšējās augošās diagonāles veido šādu skaitlisko secību, neņemot vērā beigu nulles:
Kopumā augošā diagonāles skaitlis n satur šādus binomiālos koeficientus, kuru katra indeksu summa ir vienāda ar (n1):
Ņemot vērā kombināciju numuru saskaitīšanas identitāti, katrs diagonāles elements ir vienāds ar divu elementu summu, kas atbilst indeksiem no divām iepriekšējām augošām diagonālēm. Tas ļauj konstruēt katru nākamo augošo diagonāli, pa pāriem summējot blakus esošos horizontālos elementus no divām iepriekšējām diagonālēm, bezgalīgi paplašinot Paskāla trīsstūri pa diagonāli. Šis Paskāla trijstūra fragments ilustrē augoša diagonāles skaitļa 8 uzbūvi pa diagonālēm ar 6 un 7:
Izmantojot šo konstruēšanas metodi, jebkuras augošās diagonāles elementu summa, sākot no 3., būs vienāda ar divu iepriekšējo augošo diagonāļu elementu summu, un pirmās 2 diagonāles sastāv tikai no viena elementa, vērtība no kuriem ir 1. Atbilstošo aprēķinu rezultāti veido šādu skaitlisko sēriju, saskaņā ar kuru var pārbaudīt Paskāla taisnleņķa trijstūra augošās diagonāļu aplūkotās īpašības derīgumu:
Analizējot šos skaitļus, var redzēt, ka saskaņā ar līdzīgu likumu tiek veidota labi zināmā Fibonači skaitļu secība, kur katrs nākamais skaitlis ir vienāds ar divu iepriekšējo skaitļu summu, bet pirmie divi skaitļi ir vienādi ar 1:
Tādējādi mēs varam izdarīt šādu svarīgu secinājumu: Paskāla trīsstūra elementu diagonālās summas veido Fibonači secību. Šis īpašums ļauj mums izveidot vēl vienu interesantu Paskāla trīsstūra iezīmi. Rekursīvi izvēršot Fibonači formulu, ir viegli pierādīt, ka pirmo n Fibonači skaitļu summa ir vienāda ar (F n+2 1).
Tāpēc arī binomiālo koeficientu summa, kas aizpilda augšējās n diagonāles, ir vienāda ar (F n+2 1). No tā izriet, ka Paskāla trijstūra pirmo n diagonāļu summa ir par 1 mazāka nekā binominālo koeficientu summa, kas atrodas tā diagonālē ar skaitli (n+2).
Nobeigumā jāatzīmē, ka Paskāla trijstūra horizontāles, vertikāles un diagonāles aplūkotās īpašības neizsmeļ milzīgo iespēju daudzveidību, kas savieno kopā dažādus matemātiskos aspektus, kuriem no pirmā acu uzmetiena nav nekā kopīga. Šādas neparastas īpašības ļauj uzskatīt Paskāla trīsstūri par vienu no perfektākajām skaitliskajām sistēmām, kuras visas iespējas nevar uzskaitīt un ir grūti pārvērtēt.
Tālāk ir parādīts algoritms kombināciju skaita aprēķināšanai, izmantojot Paskāla trīsstūri:
Privātā funkcija SochTT (ByVal n kā vesels skaitlis, ByVal k kā vesels skaitlis) kā dubults Dim i kā vesels skaitlis Dim j kā vesels skaitlis Dim TT () kā dubultā ReDim TT (n, k) Ja i = 0 līdz n TT (0, i) = 1 TT (i, i) = 1 nākamais i = 2 līdz n — j = 1 līdz i — 1 TT (i, j) = TT (i — 1, j — 1) + TT (i — 1, j) Nākamais Nākamais SochTT = TT (n, k) Beigu funkcija
Ja kombināciju skaits ir jāaprēķina vairākas reizes, iespējams, ērtāk ir izveidot Paskāla trīsstūri vienu reizi un pēc tam saņemt datus no masīva.
Dim TT () Kā Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 Beigt subprivāto funkciju SochTT (ByVal n kā vesels skaitlis, ByVal k kā vesels skaitlis) kā dubultā If n > Ubound (TT) Tad BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) Beigu funkcija Privāts Apakšējais izbeigtTT () RedDim TT (0, 0) Beigas Sub Private Sub BuildTT (ByVal sākums kā vesels skaitlis, ByVal beigas kā vesels skaitlis) Dim i As Integer Dim j Kā vesels skaitlis RedDim Saglabāt TT (beigas, beigas) For i = sākums Līdz beigām TT (0, i) = 1 TT (i, i) = 1 Nākamais Ja beigas< 2 Then Exit Sub If start < 2 Then start = 2 For i = start To end For j = 1 To i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Next Next End Sub
Vispirms jāizsauc CreateTT procedūra. Pēc tam jūs varat iegūt kombināciju skaitu, izmantojot SochTT funkciju. Kad jums vairs nav nepieciešams trīsstūris, izsauciet procedūru TerminateTT. Iepriekš minētajā kodā, izsaucot SochTT funkciju, ja trīsstūris vēl nav pabeigts līdz vajadzīgajam līmenim, tad tas tiek pabeigts, izmantojot BuildTT procedūru. Pēc tam funkcija iegūst vajadzīgo TT masīva elementu un atgriež to.
Dim X () Kā vesels skaitlis Dim skaitītājs () Kā vesels skaitlis Dim K kā vesels skaitlis Dim N Kā vesels skaitlis Public Sub Soch() Dim i Kā vesels skaitlis N = CInt(InputBox("Ievadiet N")) K = CInt(InputBox("Ievadiet K ")) K = K + 1 ReDim X(N) For i = 1 uz N X(i) = i Nākamais txtOut.Text = "" RedDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Kā vesels skaitlis) Dim i kā vesels skaitlis Dim j kā vesels skaitlis Dim n1 kā vesels skaitlis Dim Out() kā vesels skaitlis Dim X1() kā vesels skaitlis Ja c = K Tad rediģēt Out(K) X1 = X For i = 1 uz K - 1 n1 = 0 Ja j = 1 līdz N, ja X1(j)<>0 Tad n1 = n1 + 1 Ja n1 = Skaitītājs(i) Tad Out(i) = X1(j) X1(j) = 0 Iziet uz beigu, ja nākamais txtOut.Text = txtOut.Text & CStr(Out(i)) Nākamais txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Skaitītājs(c - 1) Uz N - c + 1 SochGenerate c + 1 Next End If End Sub
DABAS NUMURU KOMBINĀCIJAS SARAKSTS
Lai atrisinātu daudzas praktiskas problēmas, ir jāuzskaita visas fiksētās kardinalitātes kombinācijas, kuras var iegūt no dotās galīgās kopas elementiem, nevis tikai jānosaka to skaits. Ņemot vērā vienmēr pastāvošo iespēju jebkuras galīgas kopas elementiem numerēt veselus skaitļus, vairumā gadījumu ir pieļaujams aprobežoties ar naturālu skaitļu kombināciju uzskaitīšanas algoritmu izmantošanu. Dabiskākais un vienkāršākais no tiem ir algoritms naturālu skaitļu kombināciju uzskaitīšanai leksigrāfiskā kārtība.
Lai formāli aprakstītu šo algoritmu, ir ērti pieņemt, ka galvenā kopa, kuras visas m elementu kombinācijas ir jāuzskaita, veido secīgus naturālus skaitļus no 1 līdz n. Tad jebkura m kombinācija Pasūtīšanas rezultātā šāda kombināciju vektora vērtība katrā pozīcijā, protams, ir ierobežota no augšas un apakšas šādi: Leksigrāfiskais algoritms secīgi ģenerē tādus kombināciju vektorus, sākot ar leksigrāfiski mazāko vektoru, kur visās pozīcijās ir šādas minimālās iespējamās elementu vērtības, kas vienādas ar to indeksiem: Katrs secīgais kombinācijas vektors tiek veidots no pašreizējā pēc tā elementu skenēšanas no kreisās uz labo pusi, lai atrastu galējo labo elementu, kas vēl nav sasniedzis robežvērtību: Šāda elementa vērtība jāpalielina par 1. Katram elementam pa labi no tā jāpiešķir mazākā iespējamā vērtība, kas ir par 1 lielāka nekā tā kaimiņš kreisajā pusē. Pēc šīm izmaiņām nākamajam kombināciju vektoram būs šāds elementu sastāvs: Tādējādi nākamais kombinācijas vektors būs leksigrāfiski lielāks nekā iepriekšējais, jo to sākotnējo (j1) elementu vērtības ir vienādas, un elementa vērtība pozīcijā j ir par 1 lielāka nekā iepriekšējā. . Norādītā pieaugošās leksigrāfiskās kārtas sakarība tiek garantēta visās algoritma iterācijās. Rezultātā tiek iegūta pieaugoša leksigrāfiskā secība, kuru noslēdz leksigrāfiski lielākais kombinācijas vektors, kur elementiem visās pozīcijās ir šādas maksimālās vērtības: Aplūkoto leksigrāfisko algoritmu ilustrē šāds piemērs, kur augošā leksigrāfiskā secībā nepieciešams uzskaitīt visas n=6 pirmo naturālo skaitļu kombinācijas ar m=4 skaitļiem, tas ir, visas iespējamās galvenās ģenerējošās 4 elementu apakškopas. komplekts (1, 2, 3, 4, 5, 6) no 6 elementiem. Aprēķinu rezultāti ir parādīti tabulā: Šajā piemērā lielākās pieļaujamās skaitļu vērtības kombināciju vektoru pozīcijās ir attiecīgi 3, 4, 5 un 6. Rezultātu interpretācijas vienkāršības labad katrā kombinācijas vektorā ir galējais labais elements, kuram ir vēl nav sasniegusi maksimālo vērtību, ir pasvītrota. Kombināciju vektoru skaitliskie indeksi nosaka to skaitu leksigrāfiskā secībā. Vispārīgā gadījumā leksigrāfisko skaitli N jebkurai n elementu kombinācijai ar m var aprēķināt, izmantojot šādu formulu, kur kosmētisku iemeslu dēļ kombināciju skaitļu apzīmēšanai tiek izmantota Appel simbolika: Jo īpaši šādi aprēķini, izmantojot šo formulu kombinācijas skaitam (1, 3, 4, 6) n=6 elementiem m=4 leksigrāfiskā secībā, dos rezultātu N=8, kas atbilst iepriekš apskatītajam piemēram: Vispārīgā gadījumā, izmantojot identitāti abu indeksu kombināciju skaitļu summai, var parādīt, ka leksigrāfiski mazākās kombinācijas skaitlis (1, ... i, ... m), aprēķina, izmantojot šo. formula vienmēr būs vienāda ar 1: Ir arī skaidrs, ka leksigrāfiski lielākās kombinācijas (m, … nm+i, … n) skaits, aprēķinot pēc šīs formulas, būs vienāds ar n elementu kombināciju skaitu ar m: Leksigrāfisko kombināciju skaitļu aprēķināšanas formulu var izmantot, lai atrisinātu apgriezto uzdevumu, kur jums ir jānosaka kombinācijas vektors pēc tā skaitļa leksigrāfiskā secībā. Lai atrisinātu šādu apgrieztu problēmu, tas jāraksta vienādojuma veidā, kur visas nezināmās vajadzīgās kombinācijas vektora elementu vērtības (C 1, ... C i, ... C m ) ir koncentrēti tās labās puses kombināciju skaitļos, un zināmā kombināciju skaita starpība L ir uzrakstīta n elementu kreisajā pusē katram m un vajadzīgās kombinācijas numurs N: Šī vienādojuma risinājumu nodrošina šāds “mantkārīgais” algoritms, kura iterāciju laikā secīgi tiek atlasītas vajadzīgās kombinācijas vektora elementu vērtības. Sākotnējā iterācijā tiek izvēlēta minimālā iespējamā (saskaņā ar ierobežojumiem) C 1 vērtība, pie kuras pirmajam vārdam labajā pusē būs maksimālā vērtība, kas nepārsniedz L: Tagad L kreisā puse jāsamazina par pirmo kombināciju skaitu labajā pusē ar atlasīto vērtību C 1 un līdzīgi jānosaka C 2 vērtība otrajā iterācijā: Tāpat visas turpmākās iterācijas jāveic, lai atlasītu visu pārējo vajadzīgās kombinācijas elementu C i vērtības līdz pēdējam elementam C m: Acīmredzamu iemeslu dēļ pēdējā elementa C m vērtību var noteikt, pamatojoties uz tā kombināciju skaita vienādību ar L kreisās puses atlikušo vērtību: Jāpiebilst, ka kombinācijas C m pēdējā elementa vērtību var atrast vēl vienkāršāk, neuzskaitot tās iespējamās vērtības: Aplūkotā algoritma iterāciju realizāciju ilustrē šāds piemērs, kur nepieciešams noteikt kombinācijas ar skaitli N=8 leksigrāfiskā secībā, ja n=6 un m=4: Algoritmisko spēju noteikt kombināciju pēc noteikta skaitļa leksigrāfiskā secībā var izmantot dažādos virzienos. Jo īpaši, uzskaitot kombinācijas leksigrāfiskā secībā, ir jānodrošina atgriešanās pie jebkuras kombinācijas, kas iegūta agrāk, pietiek zināt tikai tās numuru. Turklāt kļūst iespējams ģenerēt kombinācijas jebkurā secībā, ko regulē patvaļīgi noteikta to leksigrāfisko skaitļu secība. Tagad mēs piedāvājam algoritmu kombināciju ģenerēšanai leksikogrāfiskā secībā: 2 i:= 1 līdz k do A[i] := i; 5 sākt rakstīt(A, …, A[k]); 6 ja A[k] = n, tad p:= p 1 cits p:= k; 8 — i:= k līdz p do A[i] := A[p] + i p + 1 KOMBINĀCIJAS AR ATKĀRTOJOŠIEM ELEMENTIEM Atšķirībā no klasiskās kombinācijas, kur visi elementi ir atšķirīgi, kombinācija ar atkārtojumiem veido nesakārtotu ierobežotas kopas elementu izlasi, kur jebkurš elements var parādīties neierobežoti bieži un ne vienmēr ir vienā eksemplārā. Šajā gadījumā elementu atkārtojumu skaitu parasti ierobežo tikai kombinācijas garums, un kombinācijas, kas atšķiras vismaz vienā elementā, tiek uzskatītas par atšķirīgām. Piemēram, izvēloties 4 pēc izvēles dažādus skaitļus no komplekta 1, 2 un 3, varat izveidot šādas 15 kombinācijas ar atkārtojumiem: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Kopumā kombinācijas ar atkārtojumiem var veidot, atlasot n patvaļīgu veidu elementus. Tomēr tos vienmēr var saistīt ar secīgiem naturāliem skaitļiem no 1 līdz n. Tad jebkuru m kombināciju pēc izvēles dažādu skaitļu šajā diapazonā var uzrakstīt vektora formā, sakārtojot tos nesamazināmā secībā no kreisās uz labo: Protams, ar šo apzīmējuma formu visi blakus esošie elementi var būt vienādi, jo ir iespējama neierobežota atkārtošanās iespēja. Tomēr katru kombinācijas vektoru ar n elementu atkārtojumiem ar m var saistīt ar (n+m−1) elementu kombinācijas vektoru ar m, kas tiek konstruēts šādi: Ir skaidrs, ka jebkurām vektora f elementu vērtībām vektora C elementi tiek garantēti atšķirīgi un stingri sakārtoti to vērtību pieaugošā secībā no diapazona no 1 līdz (n+m1) : Atbilstības viens pret vienu klātbūtne starp kombināciju vektoru f un C elementiem ļauj mums piedāvāt šādu vienkāršu metodi, lai sistemātiski uzskaitītu kombinācijas ar n elementu atkārtojumiem ar m. Atliek tikai uzskaitīt, piemēram, leksigrāfiskā secībā visas m (n+m1) elementu C kombinācijas, secīgi pārveidojot katras no tām elementus atbilstošajos kombināciju elementos ar atkārtojumiem f, izmantojot šādu formulu: Rezultātā veidojas kombināciju vektoru secība ar elementu atkārtojumiem, kas tiek sakārtoti secībā, kas ģenerēta, uzskaitot atbilstošās kombinācijas bez elementu atkārtojumiem. Jo īpaši, lai iegūtu iepriekš minēto 3 ciparu 1, 2 un 3 kombināciju secību ar 4 ciparu atkārtojumiem, ir nepieciešams leksigrāfiskā secībā uzskaitīt visas kombinācijas bez 6 ciparu 1,2,3,4, 5 atkārtojumiem. un 6 katrs ir 4 cipari, pārvēršot tos, kā norādīts. Nākamajā piemērā ir parādīta šāda kombinācijas (1,3,4,6) pārveidošana ar leksikogrāfisko numuru 8: Aplūkotā savstarpējā atbilstība kombinācijām ar un bez elementu atkārtojumiem nozīmē, ka to kopas ir vienlīdz spēcīgas. Tāpēc vispārīgā gadījumā kombināciju skaits ar n elementu atkārtojumiem ar m ir vienāds ar kombināciju skaitu bez (n+m1) elementu atkārtojumiem ar m. Izmantojot to pašu simboliku, lai apzīmētu kombināciju skaitu ar atkārtojumiem f un bez atkārtojumiem C, šo vienādību var uzrakstīt šādi: Ir viegli pārbaudīt, vai iepriekš aplūkotajā piemērā, kur n=3 un m=4, atkārtojumu kombināciju skaits būs vienāds ar 15, kas sakrīt ar to tiešā saraksta rezultātu: Jāatzīmē, ka atšķirībā no klasiskās versijas kombinācijas parametru vērtības ar atkārtojumiem n un m nav tieši saistītas viena ar otru, tāpēc f(n,m)>0 jebkurai to pozitīvo vērtību kombinācijai. Atbilstošie robežnosacījumi tiek noteikti no vienādības starp vērtībām (n+m1) un (n1) vai (n+m1) un m: Ir arī skaidri redzams, ka, ja m ir vienāds ar 1, tad elementu atkārtošanās nav iespējama, un tāpēc jebkurai pozitīvai vērtībai n>0 būs patiesa šāda vienādība: Turklāt kombināciju skaitam ar atkārtojumiem jebkurām pozitīvām vērtībām n un m ir spēkā šāda atkārtošanās sakarība, kas ir līdzīga kombināciju skaita pievienošanas identitātei bez elementu atkārtojumiem: Faktiski tas pārvēršas par norādīto pievienošanas identitāti, formāli aizstājot atbilstošo kombināciju skaitu bez atkārtojumiem tās kreisajā un labajā pusē: Aplūkoto atkārtošanās sakarību var izmantot, lai efektīvi noteiktu kombināciju skaitu ar atkārtojumiem, kad ir svarīgi likvidēt darbietilpīgās faktoriālo reizinājumu aprēķināšanas darbības un aizstāt tās ar vienkāršākām saskaitīšanas darbībām. Šajā gadījumā, lai aprēķinātu f(n,m) vērtību, ir jāpiemēro šī atkārtošanās relācija, līdz iegūstat formas f(1,m) un f(i,1) vārdu summu, kur i ņem vērtības diapazonā no n līdz 1. Pēc daudzuma definīcijas šādi termini ir attiecīgi vienādi ar 1 un i. Šis piemērs ilustrē šīs transformācijas metodes izmantošanu gadījumam, kad n=3 un m=4: BINĀRO KOMBINĀCIJU SARAKSTS Ieviešot kombinācijas aparatūrā vai programmējot montāžas valodā, ir svarīgi spēt apstrādāt kombināciju ierakstus binārā formātā. Šajā gadījumā jebkura n elementu kombinācija m jānorāda n-bitu bināra skaitļa formā (B n,...B j,...B 1), kur m vienības cipari norāda kombinācija, un atlikušajiem (nm) cipariem ir nulle vērtības. Acīmredzot, izmantojot šo apzīmējuma formu, dažādām kombinācijām ir jāatšķiras 1. ciparu izkārtojumā, un ir tikai C(n,m) veidi, kā sakārtot m vieniniekus vai (nm) nulles n-bitu binārajā kopā. Piemēram, šajā tabulā ir uzskaitītas visas 6 šādas binārās kombinācijas, kas nodrošina 4 bitu bināros skaitļus visām patvaļīgas kopas 4 elementu (E 1 , E 2 , E 3 , E 4 ) kombinācijām ar 2: Vispārīgā gadījumā šādu bināro kombināciju uzskaitīšanas uzdevums ir sistemātiska visu n-bitu bināro kopu meklēšana ar dažādiem m viena un (nm) nulles bitu izvietojumiem. Vienkāršākajā veidā šāda meklēšana tiek īstenota ar dažādām blakus bitu transponēšanas metodēm ar nobīdi (transpozitīvās nobīdes algoritmi). Tie ir iteratīvi algoritmi, un to nosaukumi atspoguļo katrā solī veikto darbību raksturu. Transpozitīvās nobīdes algoritmu iteratīvās procedūras veido bināro kombināciju secības, kas sākas ar bināro kopu, kur visas ir koncentrētas zemas kārtas cipariem (labajā pusē) un beidzas, kad visi 1 ir augstākās kārtas cipariem ( pa kreisi): Saskaņojot sākotnējās un galīgās kombinācijas, šīs secības atšķiras secībā, kādā tiek uzskaitītas starpposma binārās kopas. Taču visos gadījumos katra nākamā binārā kombinācija tiek veidota no iepriekšējās, veicot atbilstošās transponēšanas un nobīdes darbības. Tajā pašā laikā dažādi transpozitīvās nobīdes algoritmi atšķiras ar to, kā tie izvēlas bitu pāri transponēšanai un bitu grupu pārslēgšanai. Šī specifika ir aplūkota tālāk transponēšanas algoritmiem ar nobīdi pa kreisi un pa labi. Transponēšanas algoritmā ar nobīdi pa kreisi katrā solī tiek iegūta nākamā binārā kombinācija no pašreizējās, aizstājot vistālāk esošo ciparu pāri 01 ar 10 (transponēšana) un nobīdot vadošo vienības ciparu grupu, ja tāda ir, tuvu pēc transponēšanas (shift) iegūtais pāris 10. Ja šajā gadījumā pašreizējā binārajā kombinācijā vadošajos ciparos nav vienību, nobīde netiek veikta, pat ja pēc transponēšanas šajā solī tiek iegūta vadošā vienība. Nobīde netiek veikta arī tad, ja nozīmīgākajos bitos pirms pāra 10, kas iegūts pēc transponēšanas, nav nulles. Aplūkotās darbības ilustrē sekojošais piemērs divu secīgu šī algoritma iterāciju veikšanai, kur vienā iterācijā (15) tiek veikta tikai transponēšana (T"), bet otrā iterācijā (16) transponēšana tiek papildināta ar nobīdi ( T"+S"): Labās nobīdes transponēšanas algoritmā katrā solī tiek veiktas konceptuāli līdzīgas darbības. Tikai transponēšana nodrošina, ka 01. labākie biti tiek aizstāti ar 10 (nevis galēji pa kreisi), un pēc tam visi, kas atrodas pa labi no tā, tiek pārvietoti uz vismazāk nozīmīgajiem bitiem. Tāpat kā iepriekš, maiņa tiek veikta tikai tad, ja ir vienības, kuras var pārvietot pa labi. Aplūkotās darbības ilustrē sekojošais piemērs divu secīgu šī algoritma iterāciju veikšanai, kur vienā iterācijā (3) tiek veikta tikai transponēšana (T"), bet otrā iterācijā (4) transponēšana tiek papildināta ar nobīdi ( T"+S"): Jāņem vērā, ka abu algoritmu iterācijas var rakstīt aditīvā formā, ja binārās kombinācijas interpretē kā veselus skaitļus bāzes 2 skaitļu sistēmā. Jo īpaši transponēšanas algoritmam ar nobīdi pa labi katra nākamā binārā kombinācija (B" n ,…B" j , …B" 1), vienmēr var iegūt no pašreizējās kombinācijas (B n,…B j,…B 1), veicot veselu skaitļu saskaitīšanas darbības, izmantojot šādu aditīvu formulu: Šajā aditīvajā formulā divnieku f un t pakāpju eksponenti attiecīgi apzīmē pašreizējās binārās kombinācijas zemas kārtas nulles ciparu skaitu un vieninieku skaitu rindā pa kreisi no tiem. Piemēram, 4. binārajai kombinācijai (001110), kurā ir n=6 cipari f =1 un t =3. Tāpēc, aprēķinot nākamo bināro kombināciju, izmantojot aditīvās formulas 5. atkārtojumā, tiks iegūts šāds rezultāts, kas ir līdzvērtīgs transponēšanas un nobīdes darbību veikšanai: Lai veiktu salīdzinošu analīzi par aplūkotajiem transponēšanas algoritmiem ar nobīdēm pa kreisi un pa labi, ieteicams salīdzināt bināro kombināciju secības, ko tie ģenerē savās iterācijās. Nākamajā tabulā ir parādītas divas šādas bināro kombināciju secības no 4 elementiem no 2, kas iegūtas attiecīgi ar kreisās (TSL) un labās (TSR) maiņas algoritmiem: Salīdzinot šīs divas secības, jūs varat redzēt, ka tās ir atpakaļgaitas spogulis. Tas nozīmē, ka jebkuras divas binārās kombinācijas, kas tajās atrodas vienādā attālumā no to secību savstarpēji pretējiem galiem, ir viena otras spoguļattēls, tas ir, tās sakrīt, kad bitu indeksācija jebkurā no tām ir apgriezta. Piemēram, otrais binārais modelis no TSL secības sākuma (0101) ir binārā modeļa (1010) spoguļattēls, kas ir otrais pēc TSR secības beigām. Kopumā jebkura bināra kombinācija ar vienas secības skaitli i ir spoguļattēls binārai kombinācijai ar citas secības skaitli (ni+1). Šīs attiecības starp šīm sekvencēm ir transponēšanas un nobīdes darbību simetriskā rakstura sekas abos aplūkotajos bināro kombināciju uzskaitīšanas algoritmos. Jāņem vērā, ka bināro formātu var izmantot arī kombinācijas ar elementu atkārtojumiem ierakstīšanai. Lai to izdarītu, ir jāizveido savstarpēja atbilstība starp kombinācijām ar atkārtojumiem un binārajām kombinācijām, kuras tiek konstruētas šādi. Lai ir patvaļīga kombinācija ar atkārtojumiem, ko iegūst, izvēloties m neobligāti dažādus elementus no ģenerējošās kopas n elementiem. Lai noteiktu vēlamo atbilstību, vispirms kombinācijai jāpievieno visi veidojošās kopas (cat) elementi un pēc tam jāsakārto iegūtā saite (kārtot), lai visi identiskie elementi būtu blakus. Rezultāts ir (n+m) elementu secība, kur ir n identisku elementu grupas. Starp elementiem kopā būs (n+m1) atstarpes, starp kurām būs (n1) atstarpes starp identisku elementu grupām un m atstarpes starp elementiem grupu iekšienē. Skaidrības labad norādītajās vietās varat ievietot simbolus “|”. un attiecīgi. Ja tagad saskaņojam 1 ar atstarpēm starp grupām (|) un 0 ar visām pārējām atstarpēm (), mēs iegūstam bināru kombināciju. To veido (n+m1) bitu bināra kopa, kur (n1) ir vieninieki un m nulles biti, kuru atrašanās vieta unikāli atbilst sākotnējai kombinācijai ar elementu n līdz m atkārtojumiem. Aplūkoto transformācijas paņēmienu ilustrē šāds piemērs bināras kombinācijas (1001101) konstruēšanai, izmantojot kombināciju ar atkārtojumiem (BBD), kuras elementi ir atlasīti no pirmo piecu latīņu burtu ģenerēšanas kopas: Kopumā šādu bināro kopu skaits nosaka veidus, kā sakārtot (n1) vieniniekus (vai m nulles) (n+m1) bināros ciparus. Šī vērtība acīmredzami ir vienāda ar kombināciju skaitu no (n+m1) ar (n1) vai ar m, tas ir, C(n+m1,n1) vai C(n+m1,m), kas ir vienāds ar kombināciju skaits ar atkārtojumiem f(n,m) no n elementiem, m katrs. Tādējādi, ja ir viena pret vienu atbilstība starp kombinācijām ar atkārtojumiem un binārajām kombinācijām, ir leģitīmi kombināciju uzskaitīšanu ar atkārtojumiem reducēt līdz bināro kombināciju uzskaitīšanai, piemēram, izmantojot transponēšanas algoritmus ar nobīdi pa kreisi vai pa labi. Pēc tam jums tikai jāatjauno vajadzīgās kombinācijas ar atkārtojumiem, izmantojot iegūtās binārās kombinācijas. To vienmēr var izdarīt, izmantojot šādu atkopšanas paņēmienu. Ļaujiet galvenajai kopai, no kuras elementiem veidojas kombinācijas ar atkārtojumiem m, ne vienmēr ir dažādi elementi, sakārtotu patvaļīgi tā, lai katram tās elementam būtu noteikts kārtas numurs no 1 līdz n. Realizēsim arī (n+m1) bināro ciparu bināro kombināciju uzskaiti, kur (n1) vieninieki un m nulles cipari. Katru iegūto bināro kombināciju kreisajā pusē var papildināt ar fiktīvu vienības ciparu, un visus vienības ciparus var numurēt no kreisās uz labo ar veseliem skaitļiem no 1 līdz n. Tad nuļļu skaits rindā pēc katras binārās kombinācijas i-tās vienības būs vienāds ar galvenās kopas i-tā elementa gadījumu skaitu attiecīgajā kombinācijā ar atkārtojumiem. Aplūkoto paņēmienu ilustrē šāds piemērs, kur, izmantojot bināro kombināciju (1001101), tiek atjaunota kombinācija ar BBD atkārtojumiem, kuras elementi ir atlasīti no pirmo piecu latīņu burtu ģenerēšanas kopas, kas rakstīta alfabētiskā secībā. , un virslīnija norāda elementus, kuru šajā kombinācijā nav: Veicot līdzīgas darbības šī piemēra apstākļos, varat uzskaitīt visas 35 binārās kombinācijas, kas veido 7 bitu binārās kopas, kur ir 4 vieninieki un 3 nulles, un atjaunot atbilstošās kombinācijas ar 5 elementu atkārtojumiem no 3. Ziema tuvojās, un Homa un Susliks nolēma uzkrāt zirņus. Visu dienu viņi skrēja uz šķūni un nesa vairākas pākstis: Khoma, četri, un Suslik, divi. Līdz vakaram viņi saskaitīja visas novāktās pākstis un prātoja, kā tagad šos zirņus sadalīt. Homa apgalvoja, ka, ja viņš vienā reizē vilks divreiz vairāk nekā Susliks, tad viņam vajadzētu iegūt divreiz vairāk zirņu. Susliks pamatoti iebilda pret to, ka, pirmkārt, Khoma ātrums ir ievērojami mazāks nekā Suslikam, un, otrkārt, kas zina, varbūt Homa tikai vienu vai divas reizes aizbēga, bet pārējo laiku viņš bija dīkstāvē... Palīdziet saviem draugiem vismaz nedaudz izprast šo sarežģīto situāciju. Nosakiet visas iespējamās iespējas, cik pākstis atnesa Susliks un cik Khoma. Pirmajā rindā ir naturāls pāra skaitlis M – nozagto pākstīm, 2 ≤ M ≤ 1000. Visas iespējamās Suslik un Khoma atvesto pākšu daudzuma kombinācijas, viena kombinācija katrā rindā. Katra kombinācija apzīmē divus nenegatīvus veselus skaitļus, kas atdalīti ar atstarpi: pirmais skaitlis ir Suslik atnesto pākstu skaits, otrais – Khoma. Sakārtojiet kombinācijas dilstošā secībā pēc pirmā skaitļa. #iekļauts izmantojot namespace std ; int main()( int a, b = 0; cin >> a ; kamēr (a >= 0 ) ( cout<<
a
<<
" "
<<
b
<<
"\n"
;
a -= 4; b += 4; atgriezties 0 ; Ļaujiet a apzīmēt Homa atnesto pākstīšu skaitu un b būt Suslika atnesto pākstīm. Tā kā saskaņā ar problēmas apstākļiem Khoma nēsāja tikai četras pākstis, mēs apsvērsim a = a-4 un b = b + 4, lai tādējādi uzskaitītu visas iespējamās Suslik un Khoma atvesto pākstīm. Izmantosim arī cilpu kamēr, kas atkārtos iepriekš aprakstīto darbību līdz \geq 0. Atbildē izdrukājam visas iespējamās draugu atnesto pākstu skaita kombinācijas, pa vienai rindā, sakārtotas dilstošā secībā pēc pirmā skaitļa. Piemērs // Kombinācijas 3 no 52 par (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Šeit mēs apskatīsim sarežģītāku problēmu, kuras risinājumu es neesmu atradis RuNet (tomēr iedošu vienu saiti, bet tā formula ir acīmredzami nepareiza) - pamatojoties uz pašu kombināciju (šajā gadījumā komplektu trīs skaitļi) atrodiet tā indeksu. Noteiktības labad pieņemsim, ka pēc secības i1 = 3, i2 = 7, i3 = 12. Tipisks ģenerēšanas algoritms ir tāds, ka mēs ģenerējam kombinācijas 2 no 52, un katrai šādai kombinācijai ligzdotajā cilpā mēs ģenerējam kombinācijas 3 no 50 un pārbaudām, vai ligzdotās kombinācijas indeksi (i3, i4, i5) atbilst. nesakrīt ar indeksiem (i1, i2) ārējā kombinācijā: C++ kods // ĀRĒJĀ KOMBINĀCIJA priekš (int i1 = 0; i1< 51; ++i1)
for (int i2 = i1+1; i2 < 52; ++i2)
// ВНУТРЕННЕЕ СОЧЕТАНИЕ
for (int i3 = 0; i3 < 50; ++i3)
if (i3 != i1 && i3 != i2)
for (int i4 = i3+1; i4 < 51; ++i4)
if (i4 != i1 && i4 != i2)
for (int i5 = i4+1; i5 < 52; ++i5)
if (i5 != i1 && i5 != i2)
// ...
C++ kods ja (i3 >= i1) --i3; ja (i3 >= i2) --i2; // līdzīgi i4, i5 Piemēra kods indeksa sadalīšanai ar 2, 3, 47 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Indekss kombinācijai 2 no 52, reizināts ar C(3, 50) int nobīde = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // "Pārindeksēt" iekšējo grupu tā, lai numerācija būtu 0...49, ja (i3 > = i1) -i3; ja (i3 >= i2) -i3; ja (i4 >= i1) -i4; ja (i4 >= i2) -i4; ja (i5 >= i1) -i5 ; if (i5 >= i2) --i5; // Tagad pievienojiet kombinācijas indeksu ar 3 // 0: // SUM for n = 0 ar i3-1 KOMBINĀCIJAS (2, 49-n) // = SUM ja m = 50-i3 x 49 (m * (m-1) / 2) nobīde += (19600 - (((49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2); // 1: // SUMMA n = i3+1 līdz i4-1 KOMBINĀCIJAS (1, 49-n) nobīde += (( (48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2); // 2: // SUMMA n = i4+1 līdz i5-1 (1) nobīde + = (i5 - i4 - 1); atgriešanas nobīde ;) Kopumā es sadalītu kombinatoriskos algoritmus šādās klasēs: Kombināciju skaits Kombinācija no n Autors k sauc par komplektu k elementi, kas atlasīti no datiem n elementi. Kopas, kas atšķiras tikai elementu secībā (bet ne pēc sastāva), tiek uzskatītas par identiskām, tāpēc kombinācijas atšķiras no izvietojumiem. Kombināciju skaits no n Autors k
vienāds ar binomiālo koeficientu Par fiksētu vērtību n kombināciju skaita ģenerēšanas funkcija ar atkārtojumiem no n Autors k ir: Kombināciju ar atkārtojumiem skaitļu divdimensiju ģenerēšanas funkcija ir: Wikimedia fonds. 2010. gads. 70 septiņdesmit 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Faktorizācija: 2×5×7 Romiešu apzīmējums: LXX Binārais: 100 0110 ... Wikipedia Gaismas skaitlis, nosacīts skaitlis, kas unikāli izsaka ārējo apstākļi fotografēšanas laikā (parasti objekta spilgtums un izmantotā fotografēšanas materiāla fotosensitivitāte). Jebkuru E.h vērtību var atlasīt vairākas reizes. kombinācijas apertūras numurs ... ... Lielā enciklopēdiskā politehniskā vārdnīca Skaitļa forma, kas atšķir divus objektus gan attiecībā pret vienu objektu, gan attiecībā uz daudziem objektiem. Šī forma mūsdienu krievu valodā nepastāv, bet paliek tās ietekmes paliekas. Tātad, divu tabulu kombinācijas (sal. daudzskaitļa... ... Valodniecības terminu vārdnīca Kombinatoriskā matemātika, kombinatorika, matemātikas nozare, kas veltīta noteiktas, parasti galīgas kopas elementu izvēles un sakārtošanas uzdevumu risināšanai saskaņā ar dotajiem noteikumiem. Katrs šāds noteikums nosaka būvniecības metodi...... Matemātiskā enciklopēdija Kombinatorikā kombinācija ar ir elementu kopa, kas atlasīta no dotās kopas, kurā ir dažādi elementi. Kopas, kas atšķiras tikai elementu secībā (bet ne pēc sastāva), tiek uzskatītas par identiskām, šīs kombinācijas ... ... Wikipedia Nodarbojas ar tādu notikumu izpēti, kuru rašanās nav droši zināma. Tas ļauj spriest par dažu notikumu sagaidīšanas pamatotību salīdzinājumā ar citiem, lai gan skaitlisku vērtību piešķiršana notikumu varbūtībām bieži vien nav nepieciešama... ... Koljēra enciklopēdija 1) tas pats, kas matemātiskā kombinatoriskā analīze. 2) Elementārās matemātikas sadaļa, kas saistīta ar kombināciju skaita izpēti, ievērojot noteiktus nosacījumus, kuras var izveidot no noteiktas ierobežotas objektu kopas... ... Lielā padomju enciklopēdija - (grieķu paradoxos negaidīts, dīvains) plašā nozīmē: apgalvojums, kas krasi atšķiras no vispārpieņemtā, iedibinātā viedokļa, noliegums tam, kas šķiet “beznosacījumu pareizi”; šaurākā nozīmē divi pretēji apgalvojumi, par... ... Filozofiskā enciklopēdija - (vai iekļaušanas un izslēgšanas princips) kombinatoriskā formula, kas ļauj noteikt ierobežota skaita galīgo kopu savienības kardinalitāti, kuras vispārīgā gadījumā var krustoties savā starpā ... Wikipedia Matemātiskā teorija, kas saistīta ar dažādu veidu noteikšanu, kā noteikt objektus zināmā secībā; ir īpaši svarīga vienādojumu teorijā un varbūtību teorijā. Vienkāršākie šāda veida uzdevumi ir...... Enciklopēdiskā vārdnīca F.A. Brokhauss un I.A. EfronsIevadiet datus
Izvade
Pārbaudes
Ievadiet datus
Izvade
6
\\ 6 \; 0 \\ 2 \; 4
11
\\ 11\;0 \\ 7\;4 \\ 3\;8
18
\\ 18\;0 \\ 14\;4 \\ 10\;8 \\ 6\;12 \\ 2\;16
Programmas kods
Problēmas risinājums
Kombinācijas indekss
Katru kombināciju, permutāciju, izkārtojumu un citus kombinatoriskus objektus var saistīt ar indeksu - tas ir skaitlis, kurā tas parādās, atkārtojot šo algoritmu.
Ir iespēja meklēt “uz priekšu”. Mēs ieslēdzam kombināciju skaitītāju, ņemam iepriekš norādīto algoritmu un izmēģinām visu, līdz sasniedzam vēlamo opciju. Šai opcijai ir ļoti augsta laika sarežģītība, tāpēc mēs atmetīsim šo iespēju.
Pieņemsim, ka ievade satur skaitļus i1, i2, i3. Pirmkārt, mums tie ir jāsakārto augošā secībā (ņemiet vērā, ka pats ģenerēšanas algoritms, kas norādīts iepriekš, vienmēr tos veido sakārtotā formā, lai gan pats “kombinācijas” jēdziens nozīmē patvaļīgu secību).
Tas nozīmē, ka mēs “izgājām cauri” visām kombinācijām, kur i1 bija vienāds ar 0, 1 un 2.
Ja i1 = 0, mēs esam izgājuši cauri C(2, 51) kombinācijai, jo indeksi i1, i2 iet cauri visām 2 no 51 skaitļa kombinācijām.
Ja i1 = 1, mēs izmantojām C(2, 50) kombinācijas.
Ja i1 = 2, mēs izmantojām C(2, 49) kombinācijas.
Kopumā mēs izgājām cauri SUM (no n = 0 līdz n = i1-1) C(2, 51-n).
Ja i1 = 3, ņemsim vērā tās kombinācijas, kurām mēs izgājām cauri indeksam i2 (un mums tas sākas ar i2 = i1+1 = 4).
Ja i2 = 4, izturēja C(1, 47) kombinācijas, kad i2 = 5, C(1, 46) kombinācijas izturēja, ja i2 = 6, C(1, 45) kombinācijas.
Pēc pilnīgas analoģijas, ja i2 = 7, mēs ņemam vērā kombinācijas, kuras indekss i3 skrēja cauri.
Mēs iegūstam vispārīgo formulu:
Nepieciešamās kombinācijas indekss = SUM (no n = 0 līdz i1-1) C(2, 51-n) + SUM (no n = i1+1 līdz i2-1) C(1, 51-n) + SUM (no n = i2+1 līdz i3-1) C (0, 51-n).Apakškopas indekss
Kombinatorikā ir sarežģītāks objekts - sadalīšana apakškopās. Piemēram, 52 elementu kopas sadalīšana trīs apakškopās, piemēram, attiecīgi, 2, 3 un 47 elementi, kur elementu secība katrā apakškopā nav svarīga. (Starp citu, kombinācija 2 no 52 ir vienkārši īpašs gadījums, kad sadalīšana divās apakškopās ir attiecīgi 2 un 50 elementi).
Atkal, katram šādam nodalījumam ir savs indekss.
Izrādās, ka mūsu algoritmu kombinācijas indeksa atrašanai var modificēt, lai atrastu nodalījuma indeksu.
Jāpiebilst, ka indeksi “ārējā kombinācijā” i1, i2 ir jāsakārto savā starpā un indeksi i3, i4, i5 savā starpā, bet neatkarīgi no pirmajiem diviem.
Jāņem vērā arī tas, ka “ligzdotajā kombinācijā” būtībā strādājam ar 50 elementu kopu, bet indeksus i3, i4, i5 vajag “nobīdīt” noteiktā veidā, lai tie nemainītos no 0 līdz 51, bet no 0 līdz 49:
(tā teikt, mēs izgriežam indeksus i1, i2 no mūsu 52 elementu kopas un pēc tam pārbīdām atlikušo kopu, lai aizvērtu caurumus, savukārt indeksi i3-i5 tiek pārvietoti).
Jāņem vērā, ka katras “ārējās” kombinācijas iekšienē mums ir tieši C(3, 50) “ligzdotas” kombinācijas.
Tad algoritms tiks samazināts līdz šādam:
COMBINATION_INDEX (i1, i2 no 52) * COMBINATION_NUMBER BY_3_OF_50 + COMBINATION_INDEX (i3, i4, i5 no 50 pēc indeksa maiņas). Algoritmu nepārtraukta sarežģītība
Man nekavējoties jāatzīmē, ka formulā rodas “kļūda”, ja, piemēram, i1 = 0 (mēs skaitām summu, ja n = no 0 līdz -1) vai i2 = 1 (skaitām summu no 1 līdz 0). Faktiski šādos gadījumos atbilstošā summa jāpieņem vienāda ar nulli, un rezultāts būs pareizs.
Man vajadzētu pievērst uzmanību arī mūsu algoritmu laika sarežģītībai: tiem ir lineāra sarežģītība, ja jūs uzskatāt, ka C ir nemainīgs laiks. Tas jau ir daudz labāk par brutālu spēku.
Bet patiesībā (mūsu gadījumā 52) nekas neliedz mums samazināt algoritmu līdz pastāvīgai sarežģītībai. Lai to izdarītu, mēs izmantosim matemātikas zināšanas un analītiski aprēķināsim visas summas.
Piemēram, kombināciju skaits C(2, K), ja to “paplašināt” formulas K formā! / ((K-2)! * 2!), samazina līdz 2. pakāpes polinomam. Un, tā kā mums tas ir zem summas zīmes, mēs varam izmantot formulas skaitļu N-to pakāpju summai naturālajās rindās (sk. Wikipedia) un iegūt vienu 3. pakāpes polinomu. Kurai acīmredzami ir pastāvīga laika sarežģītība. (Turklāt “kļūda”, ko minēju apakšvirsraksta sākumā, nekādi neizpaužas; formula paliek pareiza).
Es atkārtoju, šis pamatkomplekta fiksētam izmēram. Tomēr esmu pārliecināts, ka ar metaprogrammēšanas palīdzību jūs varat “iemācīt” kompilatoru, lai tas paveiktu šo darbu jūsu vietā. Pēcvārds
Savā pokera simulatorā (Texas Hold'em) es vēlējos iepriekš aprēķināt un saglabāt laimesta varbūtības visām iespējamām manu kombināciju kāršu kombinācijām (2 gab.) un visām flopa kārtīm (3 kārtis uz galda). Tas atbilst dalīšanai. 52 kopa ar 2, 3, 47 apakškopām.
Aprēķināts un saglabāts.
Bet, kad pienāca laiks nolasīt datus no faila konkrētai kombinācijai, es patiešām negribēju kaut ko ilgi aprēķināt vai meklēt gigabaitu failā. Tagad es vienkārši nosaku nobīdi failā un tieši nolasu to, kas man ir nepieciešams.
Interesanti būtu uzziņu grāmata par kombinatoriskajiem algoritmiem visiem kombinatoriskajiem objektiem, ieskaitot permutācijas, kombinācijas, izvietojumus, apakškopas, kombinācijas ar atkārtojumiem, izvietojumus ar atkārtojumiem. Skaidras formulas
Saites
Skatiet, kas ir “Kombināciju skaits” citās vārdnīcās:
Grāmatas