Kalkulator mogućih kombinacija. Elementi kombinatorike

Kombinacija je neuređen izbor elemenata konačnog skupa s fiksnim brojem i bez ponavljanja elemenata. Različite kombinacije moraju se razlikovati barem po jednom elementu, a redoslijed elemenata nije bitan. Na primjer, iz skupa svih samoglasnika latiničnih slova (AEIOU) može se formirati 10 različitih kombinacija od 3 slova, tvoreći sljedeće neuređene trojke:

AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.

Zanimljivo je napomenuti da od istih pet slova možete dobiti i 10 različitih kombinacija ako ih kombinirate po 2 slova, čineći sljedeće nesređene parove:

AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.

Međutim, ako kombinirate iste latinske samoglasnike s 4, tada ćete dobiti samo sljedećih 5 različitih kombinacija:

AEIO, AEIU, AIOU, EIOU, AEOU.

U općem slučaju, za označavanje broja kombinacija n različitih elemenata s m elemenata, koristi se sljedeća funkcionalna, indeksna ili vektorska (Appel) simbolika:

Bez obzira na oblik oznake, broj kombinacija n elemenata s m elemenata može se odrediti pomoću sljedećih multiplikativnih i faktorijalnih formula:

Lako je provjeriti da se rezultat izračuna pomoću ovih formula podudara s rezultatima gornjeg primjera s kombinacijama latinskih samoglasnika. Konkretno, za n=5 i m=3, izračuni pomoću ovih formula dat će sljedeći rezultat:

U općem slučaju, formule za broj kombinacija imaju kombinatorno značenje i vrijede za bilo koje cjelobrojne vrijednosti n i m takve da je n > m > 0. Ako je m > n i m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:

Osim toga, korisno je zapamtiti sljedeće granične brojeve kombinacija, koje je lako provjeriti izravnom zamjenom u multiplikativne i faktorijelne formule:

Također treba napomenuti da multiplikativna formula ostaje važeća čak i kada je n realan broj, sve dok je m još uvijek cijeli broj. Međutim, tada rezultat izračuna na njemu, zadržavajući formalnu valjanost, gubi svoje kombinatorno značenje.

KOMBINACIJSKI IDENTITETI

Praktična uporaba multiplikativnih i faktorskih formula za određivanje broja kombinacija za proizvoljne vrijednosti n i m nije vrlo produktivna zbog eksponencijalnog rasta faktorskih proizvoda njihovog brojnika i nazivnika. Čak i za relativno male vrijednosti n i m, ovi proizvodi često premašuju mogućnosti predstavljanja cijelih brojeva u modernim računalnim i softverskim sustavima. Istodobno, njihove vrijednosti ispadaju mnogo veće od rezultirajuće vrijednosti broja kombinacija, što može biti relativno malo. Na primjer, broj kombinacija n=10 s m=8 elemenata je samo 45. Međutim, da biste pronašli ovu vrijednost koristeći faktorijelnu formulu, prvo morate izračunati mnogo veće vrijednosti od 10! u brojniku i 8! u nazivniku:

Da biste isključili dugotrajne operacije obrade velikih vrijednosti, da biste odredili broj kombinacija, možete koristiti različite odnose ponavljanja koji izravno proizlaze iz multiplikativnih i faktorskih formula. Konkretno, iz multiplikativne formule proizlazi sljedeća relacija ponavljanja, koja nam omogućuje da omjer njezinih indeksa uzmemo iza znaka broja kombinacija:

Konačno, zadržavanje indeksa nepromijenjenim daje sljedeće ponavljanje, koje se lako dobiva iz faktorijelne formule za broj kombinacija:

Nakon elementarnih transformacija, tri rezultirajuće relacije ponavljanja mogu se prikazati u sljedećim oblicima:

Ako sada zbrojimo lijevi i desni dio prve 2 formule i rezultat smanjimo za n, tada ćemo dobiti važnu rekurentnu relaciju, koja se naziva identičnost zbrajanja brojeva kombinacija:

Identitet zbrajanja pruža osnovno rekurzivno pravilo za učinkovito određivanje broja kombinacija za velike vrijednosti n i m, jer dopušta da se operacije množenja u faktorijelnim umnošcima zamijene jednostavnijim operacijama zbrajanja i za manji broj kombinacija. Konkretno, korištenjem adicionog identiteta, sada je lako odrediti broj kombinacija od n=10 sa m=8 elemenata, što je gore razmotreno, izvođenjem sljedećeg niza rekurentnih transformacija:

Osim toga, nekoliko korisnih relacija može se izvesti iz identiteta zbrajanja za izračunavanje konačnih zbroja, posebno, formula zbrajanja indeksa, koja ima sljedeći oblik:

Takav se odnos dobiva proširenjem ponavljanja u identitetu dodavanja preko člana s najvećim indeksom, sve dok je njegov indeks veći od 0. Sljedeći numerički primjer ilustrira naznačeni proces rekurzivnih transformacija:

Formula zbrajanja indeksa često se koristi za izračunavanje zbroja potencija prirodnih brojeva. Konkretno, uz pretpostavku m=1, korištenjem ove formule lako je pronaći zbroj prvih n brojeva prirodnog niza:

Druga korisna inačica formule zbrajanja može se dobiti proširenjem ponavljanja adicionog identiteta preko člana s najmanjim ekspresnim indeksom. Sljedeći numerički primjer ilustrira ovu varijantu rekurentnih transformacija:

U općem slučaju, kao rezultat takvih transformacija, dobiva se zbroj brojeva kombinacija, od kojih se oba indeksa razlikuju za jedan od susjednih članova, a razlika indeksa ostaje konstantna (u razmatranom primjeru također je jednako jedan). Tako se dobiva sljedeća formula zbrajanja preko oba indeksa brojeva kombinacije:

Uz rekurentne relacije i formule zbrajanja o kojima smo gore raspravljali, u kombinatornoj analizi dobiveni su mnogi drugi korisni identiteti za kombinacije brojeva. Najvažniji među njima je identitet simetrije, koji ima sljedeći oblik:

Valjanost identiteta simetrije može se vidjeti u sljedećem primjeru usporedbom brojeva kombinacija 5 elemenata s 2 i s (5 2) = 3:

Identitet simetrije ima očito kombinatorno značenje, jer pri određivanju broja opcija za izbor m elemenata od n elemenata, istovremeno utvrđuje broj kombinacija od preostalih (nm) neodabranih elemenata. Navedena simetrija se odmah dobiva međusobnom zamjenom m sa (nm) u formuli faktorijala za broj kombinacija:

Brojevi i kombinacijski identiteti naširoko se koriste u raznim područjima moderne računalne matematike. Međutim, njihova najpopularnija primjena povezana je s Newtonovim binomom i Pascalovim trokutom.

BINOMNI TEOREM

Za izvođenje raznih matematičkih transformacija i izračuna važno je moći prikazati bilo koju prirodnu potenciju algebarskog binoma (binoma) u obliku polinoma. Za male stupnjeve, željeni polinom može se lako dobiti izravnim množenjem binoma. Konkretno, sljedeće formule za kvadrat i kub zbroja dva člana dobro su poznate iz tečaja elementarne matematike:

U općem slučaju, za proizvoljan stupanj n binoma, željeni prikaz u obliku polinoma osigurava Newtonov binomni teorem, koji izjavljuje da vrijedi sljedeća jednakost:

Ova se jednakost obično naziva Newtonov binom. Polinom na njegovoj desnoj strani je zbroj umnožaka n članova X i Y binoma na lijevoj strani, a koeficijenti ispred njih nazivaju se binomi i jednaki su broju kombinacija s indeksima koji se dobiju od svojih ovlasti. S obzirom na posebnu popularnost Newtonove binomne formule u kombinatornoj analizi, pojmovi binomni koeficijent i broj kombinacija obično se smatraju sinonimima.

Očito, formula kvadrata zbroja i kuba su posebni slučajevi binomnog teorema za n=2 odnosno n=3. Za rukovanje većim potencijama (n>3) treba koristiti Newtonovu binomnu formulu. Njegova primjena za binom četvrtog stupnja (n=4) prikazana je sljedećim primjerom:

Valja napomenuti da je binomna formula bila poznata i prije Newtona srednjovjekovnim matematičarima arapskog istoka i zapadne Europe. Stoga njegov uobičajeni naziv nije povijesno točan. Newtonova zasluga je što je generalizirao ovu formulu na slučaj proizvoljnog realnog eksponenta r, koji može poprimiti bilo koje pozitivne ili negativne racionalne i iracionalne vrijednosti. U općem slučaju, takva Newtonova binomna formula ima beskonačnu sumu na desnoj strani i uobičajeno je pisati je na sljedeći način:

Na primjer, s pozitivnom frakcijskom vrijednošću eksponenta r ​​= 1/2, uzimajući u obzir vrijednosti binomnih koeficijenata, dobiva se sljedeće proširenje:

U općem slučaju, Newtonova binomna formula za bilo koji eksponent posebna je verzija Maclaurinove formule, koja daje širenje proizvoljne funkcije u potencijski niz. Newton je to pokazao za |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Ako sada stavimo Z=X/Y i pomnožimo lijevu i desnu stranu s Yn, tada ćemo dobiti varijantu Newtonove binomne formule o kojoj smo raspravljali gore.

Unatoč svojoj univerzalnosti, binomni teorem zadržava svoje kombinatorno značenje samo za cjelobrojne nenegativne potencije binoma. U ovom slučaju, može se koristiti za dokazivanje nekoliko korisnih identiteta za binomne koeficijente. Konkretno, gore su razmotrene formule zbrajanja za brojeve kombinacija nižeg indeksa i oba indeksa. Identitet sumiranja superskripta koji nedostaje može se lako dobiti iz Newtonove binomne formule postavljanjem X = Y = 1 ili Z = 1 u njoj:

Još jedan koristan identitet utvrđuje jednakost zbroja binomnih koeficijenata s parnim i neparnim brojevima. Odmah se dobiva iz Newtonove binomne formule ako je X = 1 i Y = 1 ili Z = 1:

Konačno, iz oba razmatrana identiteta dobiva se identitet zbroja binomnih koeficijenata samo s parnim ili samo s neparnim brojevima:

Na temelju razmatranih identiteta i rekurzivnog pravila uklanjanja indeksa ispod predznaka broja kombinacija može se dobiti niz zanimljivih relacija. Na primjer, ako u formuli zbrajanja za superskript posvuda zamijenimo n s (n1) i izbacimo indekse u svakom članu, tada ćemo dobiti sljedeću relaciju:

Koristeći sličnu tehniku ​​u formuli za zbroj binomnih koeficijenata s parnim i neparnim brojevima, može se dokazati valjanost, na primjer, sljedeće relacije:

Još jedan koristan identitet olakšava izračunavanje zbroja umnožaka simetrično smještenih binomnih koeficijenata dvaju binoma proizvoljnih stupnjeva n i k pomoću sljedeće Cauchyjeve formule:

Valjanost ove formule proizlazi iz nužne jednakosti koeficijenata za bilo koji stupanj m varijable Z na lijevoj i desnoj strani sljedeće relacije identiteta:

U posebnom slučaju kada je n=k=m, uzimajući u obzir identitet simetrije, dobiva se popularnija formula za zbroj kvadrata binomnih koeficijenata:

Mnogi drugi korisni identiteti za binomne koeficijente mogu se pronaći u opsežnoj literaturi o kombinatornoj analizi. No, njihova najpoznatija praktična primjena vezana je za Pascalov trokut.

PASCALOV TROKUT

Pascalov aritmetički trokut tvori beskonačnu numeričku tablicu sastavljenu od binomnih koeficijenata. Njegovi su redovi poredani binomnim potencijama od vrha prema dolje. U svakom retku binomni koeficijenti poredani su uzlaznim redoslijedom gornjih indeksa odgovarajućih brojeva kombinacija slijeva nadesno. Pascalov trokut obično se piše u jednakokračnom ili pravokutnom obliku.

Vizualniji i uobičajeniji je jednakokračni format, gdje binomni koeficijenti, raspoređeni u šahovnici, tvore beskonačni jednakokračni trokut. Njegov početni fragment za binome do 4. stupnja (n=4) je sljedeći:

Općenito, Pascalov jednakokračni trokut daje prikladno geometrijsko pravilo za određivanje binomnih koeficijenata, koje se temelji na identitetima zbrajanja i simetriji kombinacijskih brojeva. Konkretno, prema identitetu adicije, bilo koji binomni koeficijent je zbroj dvaju njemu najbližih koeficijenata prethodnog reda. Prema identitetu simetrije, Pascalov jednakokračni trokut je simetričan u odnosu na svoju simetralu. Dakle, svaki njegov redak je numerički palindrom binomnih koeficijenata. Ove algebarske i geometrijske značajke olakšavaju proširenje Pascalovog jednakokračnog trokuta i dosljedno pronalaženje vrijednosti binomnih koeficijenata proizvoljnih stupnjeva.

Međutim, za proučavanje različitih svojstava Pascalovog trokuta prikladnije je koristiti formalno stroži pravokutni format. U ovom formatu, dana je niže-trokutastom matricom binomnih koeficijenata, gdje oni tvore beskonačni pravokutni trokut. Početni fragment Pascalovog pravokutnog trokuta za binome do 9. stupnja (n=9) ima sljedeći oblik:

Geometrijski, takav pravokutni stol dobiva se horizontalnim deformiranjem Pascalovog jednakokračnog trokuta. Kao rezultat toga, nizovi brojeva paralelni sa stranicama Pascalovog jednakokračnog trokuta pretvaraju se u okomice i dijagonale Pascalovog pravokutnog trokuta, a horizontale obaju trokuta se podudaraju. U isto vrijeme, pravila zbrajanja i simetrije binomnih koeficijenata ostaju važeća, iako Pascalov pravokutni trokut gubi vizualnu simetriju svojstvenu svom jednakokračnom dvojniku. Kao kompenzacija za to, postaje prikladnije formalno analizirati različita numerička svojstva binomnih koeficijenata za horizontale, okomice i dijagonale Pascalovog pravokutnog trokuta.

Polazeći od analize obrisa Pascalovog pravokutnog trokuta, lako je vidjeti da je zbroj elemenata bilo kojeg retka s brojem n jednak 2 n u skladu s formulom zbrajanja za binom po superskriptu. Iz ovoga slijedi da je zbroj elemenata nad bilo kojom od horizontala s brojem n jednak (2 n 1). Ovaj rezultat postaje sasvim očit ako se vrijednost zbroja elemenata svake horizontale zapiše u binarnom brojevnom sustavu. Na primjer, za n=4, takav dodatak se može napisati na sljedeći način:

Evo još nekoliko zanimljivih svojstava konturnih linija koje su također povezane s potencijama dvojke. Ispada da ako je vodoravni broj potencija dvojke (n=2 k), tada su svi njegovi unutarnji elementi (osim krajnjih jedinica) parni brojevi. Naprotiv, svi vodoravni brojevi bit će neparni ako je njihov broj za jedan manji od potencije broja dva (n=2 k 1). Valjanost ovih svojstava može se provjeriti provjerom pariteta internih binomnih koeficijenata, na primjer, u horizontalama n=4 i n=3 ili n=8 i n=7.

Neka sada broj retka Pascalovog pravokutnog trokuta bude prosti broj p. Tada su svi njegovi unutarnji binomni koeficijenti djeljivi s p. Ovo svojstvo je lako provjeriti za male vrijednosti jednostavnih brojeva horizontala. Na primjer, svi unutarnji binomni koeficijenti pete horizontale (5, 10 i 5) očito su djeljivi s 5. Da bismo dokazali valjanost ovog rezultata za bilo koji prosti broj horizontale p, trebamo napisati multiplikativnu formulu njegovog binoma koeficijenti kako slijedi:

Budući da je p prost broj i stoga nije djeljiv s m!, umnožak ostalih faktora brojnika ove formule mora biti djeljiv s m! kako bi se zajamčila cjelobrojna vrijednost binomnog koeficijenta. Slijedi da je relacija u uglatim zagradama prirodan broj N i željeni rezultat postaje očit:

Koristeći ovaj rezultat, može se utvrditi da su brojevi svih kontura Pascalovog trokuta, čiji su unutarnji elementi djeljivi sa zadanim prostim brojem p, potencija broja p , odnosno da imaju oblik n=p k . Konkretno, ako je p=3, tada prosti broj p ne dijeli samo sve unutarnje elemente reda 3, kao što je gore utvrđeno, već, na primjer, 9. horizontalu (9, 36, 84 i 126). S druge strane, u Pascalovom trokutu nemoguće je pronaći horizontalu čiji su svi unutarnji elementi djeljivi složenim brojem. Inače, broj takve horizontale mora biti ujedno i stupanj prostih djelitelja složenog broja kojim se dijele svi njegovi unutarnji elementi, ali to je nemoguće iz očitih razloga.

Razmotrena razmatranja omogućuju nam formuliranje sljedećeg općeg kriterija djeljivosti horizontalnih elemenata Pascalovog trokuta. Najveći zajednički djelitelj (gcd) svih unutarnjih elemenata bilo koje horizontale Pascalovog trokuta s brojem n jednak je prostom broju p ako je n=pk ili 1 u svim ostalim slučajevima:

GCD(Cmn) = ( ) za bilo koju 0< m < n .

U zaključku analize horizontala, vrijedi razmotriti još jedno neobično svojstvo koje imaju nizovi binomnih koeficijenata koji ih tvore. Ako se binomni koeficijenti bilo koje horizontale s brojem n pomnože s uzastopnim potencijama broja 10, a zatim se svi ti umnošci zbroje, tada će se dobiti 11 n. Formalno potkrepljenje ovog rezultata je zamjena vrijednosti X=10 i Y=1 (ili Z=1) u Newtonovu binomnu formulu. Sljedeći numerički primjer ilustrira implementaciju ovog svojstva za n=5:

Analiza svojstava vertikala Pascalovog pravokutnog trokuta može započeti proučavanjem pojedinačnih karakteristika njihovih sastavnih elemenata. Formalno, svaka okomica m formirana je od sljedećeg beskonačnog niza binomnih koeficijenata s konstantnim indeksom (m) i povećanjem indeksa:

Očito, kada je m=0, dobije se niz jedinica, a kada je m=1, formira se niz prirodnih brojeva. Za m=2 vertikalu čine trokutasti brojevi. Svaki trokutasti broj može se prikazati na ravnini kao jednakostranični trokut, koji je ispunjen proizvoljnim objektima (jezgrama) raspoređenim u šahovskom uzorku. U ovom slučaju vrijednost svakog trokutastog broja T k određuje broj reprezentativnih jezgri, a indeks pokazuje koliko je redova jezgri potrebno za njegovu reprezentaciju. Na primjer, 4 početna trokutasta broja predstavljaju sljedeće konfiguracije iz odgovarajućeg broja znakova jezgre "@":

Valja napomenuti da se na sličan način mogu u razmatranje uvesti kvadratni brojevi S k koji se dobivaju kvadriranjem prirodnih brojeva, te općenito poligonalni figurativni brojevi nastali pravilnim popunjavanjem pravilnih mnogokuta. Konkretno, 4 početna kvadratna broja mogu se predstaviti na sljedeći način:

Vraćajući se na analizu vertikala Pascalovog trokuta, može se primijetiti da je sljedeća vertikala na m=3 ispunjena tetraedarskim (piramidalnim) brojevima. Svaki takav broj P k specificira broj jezgri koje se mogu posložiti u obliku tetraedra, a indeks određuje koliko je vodoravnih trokutastih slojeva iz redova jezgri potrebno da bi se ona prikazala u trodimenzionalnom prostoru. U ovom slučaju, svi horizontalni slojevi trebaju biti predstavljeni kao uzastopni trokutasti brojevi. Elementi sljedećih vertikala Pascalovog trokuta za m>3 tvore nizove hipertetraedskih brojeva koji nemaju jasnu geometrijsku interpretaciju na ravnini ili u trodimenzionalnom prostoru, ali formalno odgovaraju višedimenzionalnim analozima trokutastih i tetraedskih brojeva.

Iako vertikalni numerički nizovi Pascalovog trokuta imaju razmatrane pojedinačne kovrčave značajke, ali za njih je moguće izračunati parcijalne zbrojeve vrijednosti početnih elemenata na isti način, koristeći formulu za zbrajanje brojeva kombinacija prema indeks. U Pascalovom trokutu ova formula ima sljedeću geometrijsku interpretaciju. Zbroj vrijednosti n gornjih binomnih koeficijenata bilo koje vertikale jednak je vrijednosti elementa sljedeće vertikale, koji se nalazi jedan redak ispod. Ovaj rezultat je također u skladu s geometrijskom strukturom trokutastih, tetraedarskih i hipertetraedarskih brojeva, budući da se reprezentacija svakog takvog broja sastoji od slojeva jezgre koji predstavljaju brojeve nižeg reda. Konkretno, n-ti trokutasti broj T n može se dobiti zbrajanjem svih prirodnih brojeva koji predstavljaju njegova linearna vlakna:

Slično, lako je pronaći tetraedarski broj P n izračunavanjem sljedećeg zbroja prvih n trokutastih brojeva koji čine njegove horizontalne nuklearne slojeve:

Osim horizontala i vertikala u Pascalovom pravokutnom trokutu mogu se pratiti dijagonalni nizovi elemenata, čije je proučavanje svojstava također od posebnog interesa. U ovom slučaju obično se razlikuju silazne i rastuće dijagonale. Silazne dijagonale paralelne su s hipotenuzom Pascalovog pravokutnog trokuta. Formiraju ih nizovi binomnih koeficijenata s prirastom oba indeksa. Zbog identiteta simetrije, padajuće dijagonale podudaraju se u vrijednostima svojih elemenata s odgovarajućim okomitim redovima Pascalovog trokuta i stoga ponavljaju sva njihova svojstva koja su gore razmotrena. Navedena korespondencija može se pratiti slučajnošću vrijednosti elemenata padajuće dijagonale i okomice s bilo kojim brojem n, ako se ne uzmu u obzir okomite nule:

Uzlazne dijagonale tvore brojčane retke geometrijski okomite na hipotenuzu Pascalovog pravokutnog trokuta. Ispunjeni su binomnim koeficijentima s indeksnim inkrementom i superskriptnim inkrementom. Konkretno, 7 gornjih uzlaznih dijagonala čine sljedeći numerički niz, isključujući nule na kraju:

U općem slučaju, sljedeći binomni koeficijenti su na rastućoj dijagonali s brojem n, a zbroj indeksa svakog od njih je jednak (n1):

Na temelju adicijskog identiteta za kombinacije brojeva, svaki dijagonalni element jednak je zbroju dvaju elemenata koji odgovaraju indeksima iz dviju prethodnih rastućih dijagonala. To omogućuje izgradnju svake sljedeće uzlazne dijagonale parnim zbrajanjem susjednih horizontalnih elemenata iz dvije prethodne dijagonale, beskonačno šireći Pascalov trokut duž dijagonale. Sljedeći fragment Pascalovog trokuta ilustrira konstrukciju rastuće dijagonale s brojem 8 duž dijagonala s brojevima 6 i 7:

Ovom metodom konstrukcije zbroj elemenata bilo koje uzlazne dijagonale, počevši od 3., bit će jednak zbroju elemenata dviju prethodnih uzlaznih dijagonala, a prve 2 dijagonale sastoje se od samo jednog elementa, vrijednosti od čega je 1. Rezultati odgovarajućih izračuna tvore sljedeći numerički niz prema kojem je moguće provjeriti valjanost razmatranog svojstva rastućih dijagonala Pascalovog pravokutnog trokuta:

Analizirajući ove brojeve, možete vidjeti da se, prema sličnom zakonu, formira dobro poznati niz Fibonaccijevih brojeva, gdje je svaki sljedeći broj jednak zbroju prethodna dva, a prva dva broja jednaka su 1:

Stoga se može izvući sljedeći važan zaključak: dijagonalne sume elemenata Pascalovog trokuta čine Fibonaccijev niz. Ovo nam svojstvo omogućuje da ustanovimo još jednu zanimljivu značajku Pascalovog trokuta. Proširujući Fibonaccijevu formulu rekurzivno, lako je dokazati da je zbroj prvih n Fibonaccijevih brojeva jednak (F n+2 1).

Stoga je zbroj binomnih koeficijenata koji ispunjavaju gornjih n dijagonala također jednak (F n+2 1). Slijedi da je zbroj prvih n dijagonala Pascalovog trokuta za 1 manji od zbroja binomnih koeficijenata koji stoje na njegovoj dijagonali s brojem (n + 2).

Zaključno, treba napomenuti da razmatrana svojstva horizontala, vertikala i dijagonala Pascalovog trokuta ni izdaleka ne iscrpljuju ogromnu raznolikost mogućnosti koje povezuju različite matematičke aspekte koji na prvi pogled nemaju ništa zajedničko. Takva neobična svojstva omogućuju da se Pascalov trokut smatra jednim od najnaprednijih numeričkih sustava, čije se sve mogućnosti ne mogu nabrojati i teško ih je precijeniti.

Algoritam za izračunavanje broja kombinacija pomoću Pascalovog trokuta prikazan je u nastavku:

Privatna funkcija SochTT (ByVal n As Integer, ByVal k As Integer) As Double Dim i As Integer Dim j As Integer Dim TT () As Double ReDim TT (n, k) For i = 0 To n TT (0, i) = 1 TT (i, i) = 1 Sljedeći Za i = 2 Do n Za j = 1 Do i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Sljedeći Sljedeći SochTT = TT (n, k) Krajnja funkcija

Ako trebate izračunati broj kombinacija mnogo puta, možda bi bilo prikladnije izgraditi Pascalov trokut jednom, a zatim dobiti podatke iz niza.

Dim TT () As Double Private Sub CreateTT () ReDim TT (0, 0) BuildTT 0, 0 End Sub Private Function SochTT (ByVal n As Integer, ByVal k As Integer) As Double If n > Ubound (TT) Then BuildTT Ubound (TT) + 1, n SochTT = TT (n, k) End Function Private Sub TerminateTT () ReDim TT (0, 0) End Sub Private Sub BuildTT (ByVal start As Integer, ByVal end As Integer) Dim i As Integer Dim j As Integer ReDim Preserve TT (end, end) Za i = početak Do kraja TT (0, i) = 1 TT (i, i) = 1 Next If end< 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

Prvo morate pozvati CreateTT proceduru. Tada možete dobiti broj kombinacija pomoću funkcije SochTT. Kada više ne trebate trokut, nazovite TerminateTT. U gornjem kodu, prilikom pozivanja funkcije SochTT, ako trokut još nije dovršen do tražene razine, tada se dovršava pomoću procedure BuildTT. Funkcija tada dobiva traženi element TT polja i vraća ga.

Dim X () As Integer Dim Counter () As Integer Dim K As Integer Dim N As Integer Public Sub Soch() Dim i As Integer N = CInt(InputBox("Enter N")) K = CInt(InputBox("Enter K ")) K = K + 1 ReDim X(N) For i = 1 To N X(i) = i Next txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c As Integer) Dim i As Integer Dim j As Integer Dim n1 As Integer Dim Out() As Integer Dim X1() As Integer If c = K Then ReDim Out(K) X1 = X For i = 1 To K - 1 n1 = 0 za j = 1 do N ako je X1(j)<>0 Then n1 = n1 + 1 If n1 = Counter(i) Then Out(i) = X1(j) X1(j) = 0 Exit For End If Next txtOut.Text = txtOut.Text & CStr(Out(i)) Sljedeći txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub

Nabrajanje kombinacija prirodnih brojeva

Za rješavanje mnogih praktičnih problema potrebno je nabrojati sve kombinacije fiksne kardinalnosti koje se mogu dobiti iz elemenata zadanog konačnog skupa, a ne samo odrediti njihov broj. S obzirom na uvijek postojeću mogućnost cjelobrojnog numeriranja elemenata bilo kojeg konačnog skupa, u većini slučajeva dopušteno je ograničiti se na korištenje algoritama za nabrajanje kombinacija prirodnih brojeva. Najprirodniji i najjednostavniji od njih je algoritam za ispisivanje kombinacija prirodnih brojeva u leksikografski red.

Za formalni opis ovog algoritma zgodno je pretpostaviti da glavni skup, čije sve kombinacije od m elemenata moraju biti navedene, tvore uzastopne prirodne brojeve od 1 do n. Zatim bilo koja kombinacija m

Kao rezultat sređivanja, vrijednost u svakoj poziciji takvog vektora kombinacija prirodno se ispostavlja ograničenom vrijednošću odozgo i odozdo kako slijedi:

Leksigrafski algoritam sekvencijalno generira takve vektore kombinacija, počevši od leksikografski najmanjeg vektora, gdje sve pozicije sadrže sljedeće minimalne moguće vrijednosti elemenata jednake njihovim indeksima:

Svaki sljedeći kombinirani vektor formira se iz trenutnog nakon pregledavanja njegovih elemenata s lijeva na desno kako bi se pronašao krajnji desni element koji još nije dosegao svoju graničnu vrijednost:

Vrijednost takvog elementa treba povećati za 1. Svakom elementu desno od njega treba dodijeliti najmanju moguću vrijednost, koja je za 1 veća od susjeda lijevo. Nakon ovih promjena, sljedeći vektor kombinacija imat će sljedeći elementarni sastav:

Dakle, sljedeći kombinirani vektor će biti leksikografski veći od prethodnog, budući da su vrijednosti njegovih početnih (j1) elemenata jednake vrijednosti, a vrijednost elementa na poziciji j je za 1 veća od one prethodnog . Navedeni odnos rastućeg leksikografskog reda zajamčeno je zadovoljen u svim iteracijama algoritma. Kao rezultat toga, formira se rastući leksikografski niz koji nadopunjuje leksikografski najveći vektor kombinacije, gdje elementi na svim pozicijama imaju sljedeće maksimalne vrijednosti:

Razmatrani leksikografski algoritam ilustrira sljedeći primjer, gdje je potrebno navesti uzlaznim leksikografskim redom svih 15 kombinacija od n=6 prvih prirodnih brojeva s m=4 broja, odnosno sve moguće 4-elementne podskupove glavnog generirajućeg skupa ( 1, 2, 3, 4, 5, 6) od 6 elemenata. Rezultati izračuna prikazani su u sljedećoj tablici:

U ovom primjeru, najveće dopuštene vrijednosti brojeva na pozicijama kombinacijskih vektora su 3, 4, 5, odnosno 6. Radi lakšeg tumačenja rezultata u svakom kombinacijskom vektoru, krajnji desni element, koji nije ipak dosegao najveću vrijednost, podcrtano je. Numerički indeksi vektora kombinacija određuju njihove brojeve u leksikografskom redu. U općem slučaju, leksikografski broj N bilo koje kombinacije n elemenata s m može se izračunati pomoću sljedeće formule, gdje se, iz kozmetičkih razloga, koristi Appelov simbolizam za označavanje broja kombinacija:

Konkretno, sljedeći izračuni koji koriste ovu formulu za kombinaciju broja (1, 3, 4, 6) od n=6 elemenata s m=4 u leksikografskom redoslijedu dat će rezultat N=8, što odgovara gore razmotrenom primjeru:

U općem slučaju, korištenjem identiteta za zbroj brojeva kombinacija za oba indeksa, može se pokazati da je broj leksikografski najmanje kombinacije (1, ... i, ... m) kada se izračuna pomoću ove formula će uvijek biti jednaka 1:

Također je očito da će broj leksikografski najveće kombinacije (m, ... nm+i, ... n) pri izračunavanju prema ovoj formuli biti jednak broju kombinacija od n elemenata po m:

Formula za izračunavanje leksikografskog broja kombinacija može se koristiti za rješavanje inverznog problema gdje je potrebno odrediti vektor kombinacije prema njegovom broju u leksikografskom redu. Da bi se riješio takav inverzni problem, mora se napisati kao jednadžba, gdje su sve nepoznate vrijednosti elemenata vektora željene kombinacije (C 1 , ... C i , ... C m) koncentrirane u brojeve kombinacija njegove desne strane, a poznata razlika L broja kombinacija ispisana je s lijeve strane n elemenata s m i brojem željene kombinacije N:

Rješenje ove jednadžbe daje sljedeći "pohlepni" algoritam, na čijim se iteracijama sekvencijalno odabiru vrijednosti elemenata vektora željene kombinacije. U početnoj iteraciji odabire se najmanja moguća (unutar svojih ograničenja) vrijednost C 1, u kojoj će prvi član s desne strane imati najveću vrijednost koja ne prelazi L:

Sada lijevu stranu L treba smanjiti za prvi broj kombinacija na desnoj strani s odabranom vrijednošću C 1 , a vrijednost C 2 treba odrediti na isti način u drugoj iteraciji:

Slično, sve sljedeće iteracije treba izvršiti za odabir vrijednosti svih ostalih elemenata C i željene kombinacije, do posljednjeg elementa C m:

Iz očitih razloga, vrijednost posljednjeg elementa C m može se odrediti na temelju jednakosti broja njegovih kombinacija ostatku vrijednosti lijeve strane L:

Valja napomenuti da se vrijednost posljednjeg elementa kombinacije C m može pronaći još jednostavnije, bez nabrajanja njegovih mogućih vrijednosti:

Implementacija iteracija razmatranog algoritma ilustrirana je sljedećim primjerom, gdje je potrebno odrediti kombinacije s brojem N=8 u leksikografskom redu, ako je n=6 i m=4:

Algoritamska sposobnost određivanja kombinacije zadanim brojem u leksikografskom redu može se koristiti u različitim smjerovima. Konkretno, pri popisu kombinacija u leksikografskom redu potrebno je osigurati povratak na bilo koju kombinaciju koja je ranije dobivena, dovoljno je znati samo njezin broj. Osim toga, postaje moguće generirati kombinacije bilo kojim redoslijedom koji regulira proizvoljno zadani niz njihovih leksikografskih brojeva.

Sada predstavljamo algoritam za generiranje kombinacija u leksikografskom redu:

2 za i:= 1 do k učiniti A[i] := i;

5 početak pisanja(A, …, A[k]);

6 if A[k] = n then p:= p 1 else p:= k;

8 za i:= k downto p do A[i] := A[p] + i p + 1

KOMBINACIJE S PONAVLJANJEM ELEMENATA

Za razliku od klasične kombinacije, gdje su svi elementi različiti, kombinacija s ponavljanjima čini nesređen izbor elemenata konačnog skupa, gdje se bilo koji element može pojavljivati ​​neograničeno često i ne mora nužno biti prisutan u jednom primjerku. Pritom je broj ponavljanja elemenata obično ograničen samo duljinom kombinacije, a kombinacije koje se razlikuju barem po jednom elementu smatraju se različitima. Na primjer, odabirom 4 po izboru različita broja iz skupa 1, 2 i 3, možete napraviti sljedećih 15 kombinacija s ponavljanjima:

1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.

U općem slučaju, kombinacije s ponavljanjem mogu se formirati odabirom od n elemenata proizvoljnih vrsta. Međutim, oni se uvijek mogu povezati s uzastopnim prirodnim brojevima od 1 do n. Tada se bilo koja kombinacija od m izborno različitih brojeva u ovom rasponu može napisati u vektorskom obliku, raspoređujući ih u neopadajućem redoslijedu slijeva nadesno:

Naravno, kod ovog oblika pisanja svi susjedni elementi mogu biti ravnopravni zbog mogućnosti neograničenog ponavljanja. Međutim, svaki vektor kombinacije s ponavljanjima od n elemenata po m može se pridružiti vektoru kombinacije od (n + m − 1) elemenata po m, koji se konstruira na sljedeći način:

Jasno je da za bilo koje vrijednosti elemenata vektora f, elementi vektora C su zajamčeno različiti i strogo poredani uzlaznim redoslijedom svojih vrijednosti od raspona od 1 do (n+m1) :

Prisutnost korespondencije jedan na jedan između elemenata kombinacijskih vektora f i C omogućuje nam da predložimo sljedeću jednostavnu metodu za sustavno nabrajanje kombinacija s ponavljanjem n elemenata preko m. Potrebno je samo navesti, na primjer, leksikografskim redom svih C kombinacija (n + m1) elemenata po m, sekvencijalno pretvarajući elemente svakog od njih u odgovarajuće elemente kombinacija s ponavljanjima f prema sljedećoj formuli:

Kao rezultat toga, formira se niz kombinacijskih vektora s ponavljanjima elemenata, koji su raspoređeni redoslijedom generiranim nabrajanjem odgovarajućih kombinacija bez ponavljanja elemenata. Konkretno, da bi se dobio gornji niz kombinacija od 3 znamenke 1, 2 i 3 s ponavljanjima od 4 znamenke, potrebno je leksikografskim redom navesti sve kombinacije bez ponavljanja od 6 znamenki 1,2,3,4, 5. i 6 puta 4 znamenke, pretvarajući ih na navedeni način. Sljedeći primjer pokazuje takvu transformaciju kombinacije (1,3,4,6) s leksikografskim brojem 8:

Razmotrena korespondencija jedan na jedan između kombinacija s ponavljanjem i bez ponavljanja elemenata znači da su njihovi skupovi ekvivalentni. Dakle, u općem slučaju broj kombinacija s ponavljanjem od n elemenata preko m jednak je broju kombinacija bez ponavljanja od (n + m1) elemenata preko m. Koristeći isti simbolizam za označavanje broja kombinacija s ponavljanjem f i bez ponavljanja C, ova se jednakost može napisati na sljedeći način:

Lako je provjeriti da će za gornji primjer, gdje je n=3 i m=4, broj kombinacija s ponavljanjem biti 15, što se podudara s rezultatom njihovog izravnog nabrajanja:

Treba napomenuti da, za razliku od klasične verzije, vrijednosti parametara kombinacije s ponavljanjima n i m nisu izravno povezane jedna s drugom, stoga je f(n,m)>0 za bilo koju kombinaciju njihovih pozitivnih vrijednosti. Odgovarajući rubni uvjeti određuju se iz jednakosti između vrijednosti (n+m1) i (n1) ili (n+m1) i m:

Također bi trebalo biti sasvim očito da ako je m jednako 1, tada nije moguće ponavljanje elemenata i, prema tome, za bilo koju pozitivnu vrijednost n>0, vrijedit će sljedeća jednakost:

Osim toga, za brojeve kombinacija s ponavljanjima za bilo koje pozitivne vrijednosti n i m vrijedi sljedeća relacija ponavljanja, koja je slična identitetu zbrajanja za brojeve kombinacija bez ponavljanja elemenata:

Zapravo se pretvara u navedeni identitet zbrajanja formalnom zamjenom odgovarajućih brojeva kombinacija bez ponavljanja u lijevom i desnom dijelu:

Razmotrena rekurentna relacija može se koristiti za učinkovito određivanje broja kombinacija s ponavljanjem, kada je važno isključiti dugotrajne operacije izračuna faktorijelnih umnožaka i zamijeniti ih jednostavnijim operacijama zbrajanja. U isto vrijeme, da biste izračunali vrijednost f(n,m), samo trebate primijeniti ovu relaciju ponavljanja dok ne dobijete zbroj članova oblika f(1,m) i f(i,1), gdje i uzima vrijednosti u rasponu od n do 1. Prema definiciji, takvi pojmovi su jednaki 1, odnosno i. Sljedeći primjer ilustrira upotrebu ove tehnike transformacije za slučaj n=3 i m=4:

Nabrajanje binarnih kombinacija

Prilikom implementacije kombinacija u hardveru ili kod programiranja u asemblerskom jeziku, važno je moći obraditi zapise kombinacija u binarnom formatu. U ovom slučaju, bilo koja kombinacija n elemenata s m treba biti specificirana u obliku n-bitnog binarnog broja (B n ,…B j ,…B 1), gdje m jednoznamenkastih znamenki označava elemente kombinacije, a preostale (nm) znamenke imaju nulte vrijednosti. Očito, s ovim oblikom pisanja, različite kombinacije moraju se razlikovati u rasporedu jedinica i postoji samo C (n, m) načina za raspored m jedinica ili (nm) nula u n-bitnom binarnom skupu. Na primjer, sljedeća tablica navodi svih 6 takvih binarnih kombinacija koje daju 4-bitne binarne brojeve za sve kombinacije 4 elementa proizvoljnog skupa (E 1 ,E 2 ,E 3 ,E 4 ) po 2:

U općem slučaju, zadatak nabrajanja takvih binarnih kombinacija sveden je na sustavno nabrajanje svih n-bitnih binarnih skupova s ​​različitim rasporedom m pojedinačnih i (nm) nula bitova. U najjednostavnijem obliku takvo se nabrajanje provodi različitim metodama transpozicije susjednih znamenki s pomakom (transpositive-shift algoritmi). To su iterativni algoritmi, a njihova imena odražavaju prirodu operacija koje se izvode u svakom koraku. Iterativne procedure algoritama transpozitivnog pomaka formiraju nizove binarnih kombinacija koje počinju binarnim skupom, gdje su sve jedinice koncentrirane u nižim bitovima (desno), a završavaju kada su sve jedinice u višim bitovima (lijevo):

Podudarajući se u početnim i završnim kombinacijama, ti se nizovi razlikuju u redoslijedu nabrajanja međubinarnih skupova. Međutim, u svim slučajevima svaka sljedeća binarna kombinacija formira se prema prethodnoj kao rezultat izvođenja odgovarajućih operacija transpozicije i pomaka. Pritom se različiti algoritmi transpozitivnog pomaka razlikuju po načinu odabira para znamenki za transpoziciju i grupe znamenki za pomak. Ova se specifičnost razmatra u nastavku za algoritme transpozicije s pomacima ulijevo i udesno.

U algoritmu transpozicije s pomakom ulijevo u svakom koraku, sljedeća binarna kombinacija dobiva se iz trenutne zamjenom krajnjeg lijevog para bitova 01 s 10 (transpozicija) i pomakom grupe vodećih pojedinačnih bitova, ako ih ima, blizu par 10 dobiven nakon transpozicije (pomaka). Ako u ovom slučaju nema jedinica u najvišim bitovima u trenutnoj binarnoj kombinaciji, tada se pomak ne izvodi, čak ni kada se nakon transpozicije u ovom koraku dobije vodeća jedinica. Pomak se također ne izvodi kada nema nula u bitovima višeg reda prije para desetki dobivenih nakon transpozicije. Razmotrene radnje ilustrirane su sljedećim primjerom izvođenja dvije uzastopne iteracije ovog algoritma, gdje se u jednoj iteraciji (15) izvodi samo transpozicija (T"), a u drugoj iteraciji (16) transpozicija se nadopunjuje pomakom (T"+S"):

U algoritmu transpozicije desnog pomaka, konceptualno slične radnje izvode se u svakom koraku. Samo transpozicija osigurava da se krajnje desne znamenke 01 zamijene s 10 (umjesto krajnje lijevih), a zatim se sve jedinice desno od nje pomiču na niže znamenke. Kao i prije, pomak se izvodi samo ako postoje jedinice koje se mogu pomaknuti udesno. Razmotrene radnje ilustrirane su sljedećim primjerom izvođenja dvije uzastopne iteracije ovog algoritma, gdje se u jednoj iteraciji (3) izvodi samo transpozicija (T"), a u drugoj iteraciji (4) transpozicija se nadopunjuje s pomak (T"+S"):

Treba napomenuti da se iteracije oba algoritma mogu napisati u aditivnom obliku ako se binarne kombinacije interpretiraju kao cijeli brojevi u brojevnom sustavu u bazi 2. Konkretno, za transpozicijski algoritam s desnim pomakom, svaka sljedeća binarna kombinacija (B " n ,…B" j , …B" 1) uvijek se može dobiti iz trenutne kombinacije (B n ,…B j ,…B 1) izvođenjem operacija cjelobrojnog zbrajanja koristeći sljedeću aditivnu formulu:

U ovoj aditivnoj formuli, eksponenti dvojki f i t označavaju redom broj nula trenutne binarne kombinacije i broj jedinica u nizu lijevo od njih. Na primjer, za 4. binarnu kombinaciju (001110) od n=6 bitova, f =1 i t =3. Stoga će izračun sljedeće binarne kombinacije aditivnom formulom u iteraciji 5 dati sljedeći rezultat, koji je ekvivalentan izvođenju operacija transpozicije i pomaka:

Za komparativnu analizu razmatranih transpozicijskih algoritama s pomakom ulijevo i udesno, preporučljivo je usporediti nizove binarnih kombinacija koje oni generiraju u svojim iteracijama. Sljedeća tablica prikazuje dvije takve sekvence binarnih kombinacija 4 elementa sa 2, koje su dobivene algoritmima lijevog (TSL) odnosno desnog (TSR) pomaka:

Uspoređujući ove 2 sekvence, možete vidjeti da su obrnuto zrcalne. To znači da su bilo koje dvije binarne kombinacije koje se u njima nalaze na istoj udaljenosti od međusobno suprotnih krajeva njihovih nizova zrcalne slike jedna druge, odnosno podudaraju se pri promjeni obrnutog indeksiranja bitova u bilo kojoj od njih. Na primjer, drugi binarni uzorak od početka TSL niza (0101) je zrcalna slika binarnog uzorka (1010) koji je drugi od kraja TSR niza. U općem slučaju, svaka binarna kombinacija s brojem i jednog niza zrcalna je slika binarne kombinacije s brojem (ni + 1) drugog niza. Takav omjer ovih nizova posljedica je simetrične prirode operacija transpozicije i posmaka u dva razmatrana algoritma za nabrajanje binarnih kombinacija.

Treba napomenuti da se binarni format također može koristiti za pisanje kombinacija s ponavljanjem elemenata. Da biste to učinili, morate uspostaviti korespondenciju jedan-na-jedan između kombinacija s ponavljanjima i binarnih kombinacija, koje su konstruirane na sljedeći način. Neka postoji proizvoljna kombinacija s ponavljanjima koja se dobiva izborom m opcijski različitih elemenata od n elemenata generirajućeg skupa. Da biste uspostavili željenu korespondenciju, prvo morate kombinaciji priložiti sve elemente generatorskog skupa (cat), a zatim sortirati rezultirajuću konkatenaciju (sort) tako da su svi identični elementi u blizini. Rezultat je niz od (n+m) elemenata, gdje je n grupa identičnih elemenata. Bit će samo (n+m1) praznina između elemenata, među kojima će biti (n1) praznina između grupa identičnih elemenata i m praznina između elemenata unutar grupa. Radi jasnoće, u navedenim intervalima možete postaviti znakove "|" i shodno tome. Ako sada preslikamo 1 na praznine između grupa (|) i 0 na sve ostale praznine (), tada ćemo dobiti binarnu kombinaciju. Sastoji se od binarnog skupa (n+m1) znamenki, gdje su (n1) jedinice, a m nula znamenki, čiji položaj jedinstveno odgovara izvornoj kombinaciji s ponavljanjima od elemenata n do m. Razmotrena tehnika transformacije ilustrirana je sljedećim primjerom konstruiranja binarne kombinacije (1001101) kombinacijom s ponavljanjima (BBD), čiji su elementi odabrani iz generirajućeg skupa prvih pet latiničnih slova:

Općenito, broj takvih binarnih skupova određuje broj načina za raspoređivanje (n1) jedinica (ili m nula) u (n+m1) binarnih znamenki. Ova vrijednost je očito jednaka broju kombinacija od (n+m1) preko (n1) ili preko m, odnosno C(n+m1,n1) ili C(n+m1,m), što je jednako broj kombinacija s ponavljanjem f( n,m) od n elemenata po m. Stoga, imajući korespondenciju jedan na jedan između kombinacija s ponavljanjima i binarnih kombinacija, legitimno je reducirati nabrajanje kombinacija s ponavljanjima na nabrajanje binarnih kombinacija, na primjer, korištenjem algoritama transpozicije s pomakom ulijevo ili udesno. Nakon toga samo trebate obnoviti željene kombinacije s ponavljanjima iz dobivenih binarnih kombinacija. To se uvijek može učiniti primjenom sljedeće restorativne tehnike.

Neka je glavni skup, od čijih se elemenata formiraju kombinacije s ponavljanjem od m po izboru različitih elemenata, poredan proizvoljno tako da svaki njegov element ima određeni redni broj od 1 do n. Neka se također implementira nabrajanje binarnih kombinacija (n+m1) binarnih znamenki, gdje su (n1) jednostruke, a m nula znamenki. Svaka dobivena binarna kombinacija može se nadopuniti s lijeve strane fiktivnom znamenkom jedinice, a sve znamenke jedinice mogu se numerirati s lijeva na desno cijelim brojevima od 1 do n. Tada će broj nula koje stoje u nizu iza svake i-te jedinice binarne kombinacije biti jednak broju instanci i-tog elementa glavnog skupa u odgovarajućoj kombinaciji s ponavljanjima. Razmatrana tehnika ilustrirana je sljedećim primjerom, gdje binarna kombinacija (1001101) obnavlja kombinaciju s BBD ponavljanjima, čiji su elementi odabrani iz generirajućeg skupa prvih pet latiničnih slova napisanih abecednim redom, a nadcrtavanje označava elementi koji nedostaju u ovoj kombinaciji:

Izvodeći slične radnje u uvjetima ovog primjera, možete navesti svih 35 binarnih kombinacija koje tvore 7-bitne binarne skupove, gdje su 4 jedinice i 3 nule, i vratiti odgovarajuće kombinacije s ponavljanjem od 5 elemenata po 3.

Valja napomenuti da je kombinatorika samostalan dio više matematike (a ne dio tervera) iu ovoj su disciplini napisani značajni udžbenici čiji sadržaj ponekad nije lakši od apstraktne algebre. No, mali dio teorijskog znanja bit će nam dovoljan, au ovom ću članku pokušati analizirati osnove teme s tipičnim kombinatornim problemima u pristupačnom obliku. I mnogi od vas će mi pomoći ;-)

Što ćemo učiniti? U užem smislu, kombinatorika je izračunavanje različitih kombinacija koje se mogu napraviti iz određenog skupa diskretna objekti. Pod objektima se podrazumijevaju bilo koji izolirani objekti ili živa bića - ljudi, životinje, gljive, biljke, kukci itd. Pritom kombinatoriku uopće nije briga što se set sastoji od tanjura griza, lemilice i močvarne žabe. Temeljno je važno da su ti objekti nabrojivi - ima ih tri. (diskretnost) a bitno je da nitko od njih nije sličan.

Kad smo dosta toga posložili, sada o kombinacijama. Najčešći tipovi kombinacija su permutacije objekata, njihov izbor iz skupa (kombinacija) i distribucija (postavljanje). Pogledajmo kako se to sada događa:

Permutacije, kombinacije i postavljanja bez ponavljanja

Nemojte se bojati opskurnih izraza, pogotovo jer neki od njih doista nisu baš uspješni. Počnimo s repom naslova - što znači " bez ponavljanja"? To znači da ćemo u ovom dijelu razmatrati skupove koji se sastoje od razne objekti. Na primjer, ... ne, neću nuditi kašu s lemilicom i žabom, bolje je nešto ukusnije =) Zamislite da su se na stolu ispred vas materijalizirale jabuka, kruška i banana (ako ih ima bilo koja, situacija se može simulirati u stvarnom stanju). Voće slažemo s lijeva na desno sljedećim redoslijedom:

jabuka / kruška / banana

Pitanje jedno: Na koliko se načina mogu preurediti?

Jedna kombinacija je već napisana gore, a s ostalima nema problema:

jabuka / banana / kruška
kruška / jabuka / banana
kruška / banana / jabuka
banana / jabuka / kruška
banana / kruška / jabuka

Ukupno: 6 kombinacija ili 6 permutacije.

Dobro, ovdje nije bilo teško nabrojati sve moguće slučajeve, ali što ako ima više stavki? Već s četiri različita voća, broj kombinacija će se značajno povećati!

Molimo otvorite referentni materijal (Priručnik se lako ispisuje) au stavku broj 2 pronađite formulu za broj permutacija.

Bez muke - 3 predmeta mogu se preuređivati ​​na različite načine.

Drugo pitanje: Na koliko načina možete izabrati a) jednu voćku, b) dvije voćke, c) tri voćke, d) barem jednu voćku?

Zašto izabrati? Pa su u prethodnom paragrafu podigli apetit – da bi jeli! =)

a) Jedno voće se može birati, očito, na tri načina - uzeti ili jabuku, ili krušku, ili bananu. Formalno prebrojavanje temelji se na formula za broj kombinacija:

Unos u ovom slučaju treba shvatiti na sljedeći način: "na koliko načina možete odabrati 1 voće od tri?"

b) Navodimo sve moguće kombinacije dva voća:

jabuka i kruška;
jabuka i banana;
kruška i banana.

Broj kombinacija lako je provjeriti pomoću iste formule:

Unos se shvaća slično: "na koliko načina možete odabrati 2 voća od tri?".

c) I na kraju, tri voća mogu se odabrati na jedinstven način:

Usput, formula za broj kombinacija također ima smisla za prazan uzorak:
Na ovaj način ne možete odabrati niti jednu voćku – zapravo, ne uzeti ništa i to je to.

d) Na koliko načina možete uzeti najmanje jedan voće? Uvjet "barem jedan" podrazumijeva da smo zadovoljni s 1 voćkom (bilo kojom) ili bilo koje 2 voćke ili sve 3 voćke:
načina na koje možete odabrati barem jedno voće.

Čitatelji koji su pažljivo proučili uvodnu lekciju o teorija vjerojatnosti već nešto smislio. Ali o značenju znaka plus kasnije.

Za odgovor na sljedeće pitanje trebam dva volontera ... ... Pa pošto nitko ne želi, onda ću se javiti na ploču =)

Pitanje tri: Na koliko se načina jedna voćka može podijeliti Daši i Nataši?

Kako biste podijelili dva voća, prvo ih morate odabrati. Prema odlomku "be" prethodnog pitanja, to se može učiniti na načine, ponovno ću ih napisati:

jabuka i kruška;
jabuka i banana;
kruška i banana.

Ali sada će biti dvostruko više kombinacija. Razmotrimo, na primjer, prvi par plodova:
Dašu možete počastiti jabukom, a Natašu kruškom;
ili obrnuto - Daša će dobiti krušku, a Nataša jabuku.

A takva je permutacija moguća za svaki par plodova.

Razmotrite istu grupu studenata koja je otišla na ples. Na koliko se načina mogu spojiti dječak i djevojčica?

Načini na koje možete izabrati 1 mladića;
načina na koje možete odabrati 1 djevojku.

Dakle, jedan mladić i može se izabrati jedna djevojka: načine.

Kada je iz svakog skupa odabran 1 objekt, tada vrijedi sljedeći princip brojanja kombinacija: “ svaki predmet iz jednog skupa može činiti par sa svakim objekt drugog skupa.

Odnosno, Oleg može pozvati bilo koju od 13 djevojaka na ples, Evgeny - također bilo koju od trinaest, a drugi mladi imaju sličan izbor. Ukupno: mogući parovi.

Treba primijetiti da u ovom primjeru "povijest" formiranja para nije bitna; no ako se uzme u obzir inicijativa, onda se broj kombinacija mora udvostručiti, budući da svaka od 13 djevojaka može pozvati i bilo kojeg dječaka na ples. Sve ovisi o uvjetima pojedinog zadatka!

Slično načelo vrijedi i za složenije kombinacije, npr.: na koliko se načina mogu izabrati dva mladića i dvije djevojke za sudjelovanje u KVN skeču?

Unija I nedvosmisleno ukazuje da se kombinacije moraju umnožiti:

Moguće grupe umjetnika.

Drugim riječima, svaki parovi dječaka (45 jedinstvenih parova) mogu se natjecati s bilo koji par djevojaka (78 jedinstvenih parova). A ako uzmemo u obzir raspodjelu uloga između sudionika, tada će biti još više kombinacija. ... baš želim, ali ipak ću se suzdržati od nastavka, da vam ne usadim averziju prema studentskom životu =).

Pravilo množenja primjenjuje se na više množitelja:

Zadatak 8

Koliko ima troznamenkastih brojeva djeljivih s 5?

Riješenje: radi jasnoće, ovaj broj označavamo s tri zvjezdice: ***

NA stotine mjesta možete napisati bilo koji od brojeva (1, 2, 3, 4, 5, 6, 7, 8 ili 9). Nula nije dobra, jer u tom slučaju broj prestaje biti troznamenkasti.

Ali u mjesto desetica(“u sredini”) možete odabrati bilo koju od 10 znamenki: .

Prema uvjetu, broj mora biti djeljiv s 5. Broj je djeljiv s 5 ako završava s 5 ili 0. Dakle, u najmanjoj znamenki zadovoljavamo se s 2 znamenke.

Ukupno, postoji: troznamenkasti brojevi djeljivi s 5.

Istodobno, rad se dešifrira na sljedeći način: „9 načina na koje možete odabrati broj stotine mjesta i 10 načina za odabir broja u mjesto desetica i 2 ulaza znamenka jedinice»

Ili još jednostavnije: svaki od 9 znamenki do stotine mjesta kombinirani sa svakim od 10 znamenki mjesto desetica i sa svakim od dvije znamenke znamenka jedinica».

Odgovor: 180

A sada…

Da, skoro sam zaboravio na obećani komentar problema br. 5, u kojem Borja, Dima i Volodja mogu dobiti po jednu kartu na različite načine. Množenje ovdje ima isto značenje: na načine na koje možete izvući 3 karte iz špila I u svakom uzorak da ih preuredite.

A sada problem za neovisno rješenje ... sada ću smisliti nešto zanimljivije, ... neka bude o istoj ruskoj verziji blackjacka:

Zadatak 9

Koliko ima dobitnih kombinacija od 2 karte u "point" igri?

Za one koji ne znaju: dobitna kombinacija 10 + KEC (11 bodova) = 21 bod i, razmislimo o dobitnoj kombinaciji od dva asa.

(redoslijed karata u bilo kojem paru nije bitan)

Kratko rješenje i odgovor na kraju lekcije.

Usput, nije potrebno smatrati primjer primitivnim. Blackjack je gotovo jedina igra za koju postoji matematički opravdan algoritam koji vam omogućuje da pobijedite kasino. Oni koji to žele lako mogu pronaći mnoštvo informacija o optimalnoj strategiji i taktici. Istina, takvi majstori brzo padaju na crnu listu svih ustanova =)

Vrijeme je da učvrstimo pređeno gradivo s nekoliko solidnih zadataka:

Zadatak 10

Vasya ima 4 mačke kod kuće.

a) Na koliko se načina mačke mogu smjestiti u kutove sobe?
b) Na koliko se načina mačkama može dopustiti da lutaju?
c) na koliko načina Vasja može pokupiti dvije mačke (jednu s lijeve strane, drugu s desne strane)?

Mi odlučujemo: prvo, treba ponovno napomenuti da je problem oko drugačiji predmete (čak i ako su mačke jednojajčane blizanke). Ovo je vrlo važan uvjet!

a) Šutnja mačaka. Ovo izvršenje podliježe sve mačke odjednom
+ njihov položaj je važan, tako da ovdje postoje permutacije:
načine na koje možete postaviti mačke u kutove sobe.

Ponavljam da je kod permutiranja bitan samo broj različitih objekata i njihov relativni položaj. Ovisno o svom raspoloženju, Vasya može smjestiti životinje u polukrug na sofu, u nizu na prozorsku dasku itd. - bit će 24 permutacije u svim slučajevima.Za praktičnost, oni koji žele mogu zamisliti da su mačke višebojne (na primjer, bijele, crne, crvene i prugaste) i navesti sve moguće kombinacije.

b) Na koliko se načina mačkama može dopustiti da lutaju?

Pretpostavlja se da mačke idu u šetnju samo kroz vrata, dok pitanje implicira indiferentnost o broju životinja - 1, 2, 3 ili sve 4 mačke mogu ići u šetnju.

Razmatramo sve moguće kombinacije:

Načini na koje možete pustiti u šetnju jednu mačku (bilo koju od četiri);
načine na koje možete pustiti dvije mačke u šetnju (mogućnosti navedite sami);
kako možete pustiti tri mačke u šetnju (jedna od četiri sjedi kod kuće);
način na koji možete osloboditi sve mačke.

Vjerojatno ste pogodili da dobivene vrijednosti treba zbrojiti:
načina da pustite mačke u šetnju.

Za entuzijaste nudim kompliciranu verziju problema - kada bilo koja mačka u bilo kojem uzorku može nasumično izaći van, kroz vrata i kroz prozor na 10. katu. Bit će još kombinacija!

c) Na koliko načina Vasja može pokupiti dvije mačke?

Situacija uključuje ne samo izbor 2 životinje, već i njihovo postavljanje na ruke:
načini na koje možete pokupiti 2 mačke.

Drugo rješenje: na neki način možete odabrati dvije mačke i načina sadnje svaki par u ruci:

Odgovor: a) 24, b) 15, c) 12

Pa da očistim savjest nešto konkretnije o množenju kombinacija.... Neka Vasya ima 5 dodatnih mačaka =) Na koliko načina možete pustiti 2 mačke u šetnju i 1 mačka?

Odnosno sa svaki može se pustiti par mačaka svaki mačka.

Još jedna harmonika s gumbima za neovisno rješenje:

Zadatak 11

3 putnika su ušla u lift zgrade od 12 katova. Svatko, neovisno o drugima, može izaći na bilo kojem (počevši od 2.) kata s istom vjerojatnošću. Na koliko načina:

1) Putnici mogu izaći na istom katu (izlazni redoslijed nije bitan);
2) dvije osobe mogu sići na jednom katu, a treće na drugom;
3) ljudi mogu sići na različitim katovima;
4) Mogu li putnici izaći iz dizala?

I ovdje često opet pitaju, pojašnjavam: ako 2 ili 3 osobe izlaze na istom katu, onda redoslijed izlaska nije bitan. RAZMIŠLJAJ, koristi formule i pravila za kombinacije zbrajanja/množenja. U slučaju poteškoća, korisno je da putnici navedu imena i razloge u kojim kombinacijama mogu izaći iz dizala. Nema potrebe da se uzrujavate ako nešto ne uspije, na primjer, točka broj 2 prilično je podmukla.

Cjelovito rješenje s detaljnim komentarima na kraju vodiča.

Posljednji odlomak posvećen je kombinacijama koje se također javljaju prilično često - prema mojoj subjektivnoj procjeni, u oko 20-30% kombinatornih problema:

Permutacije, kombinacije i postavljanja s ponavljanjima

Navedene vrste kombinacija navedene su u odlomku br. 5 referentnog materijala Osnovne formule kombinatorike, međutim, neke od njih možda neće biti vrlo jasne na prvo čitanje. U ovom slučaju, preporučljivo je prvo se upoznati s praktičnim primjerima, a tek onda shvatiti opću formulaciju. Ići:

Permutacije s ponavljanjima

U permutacijama s ponavljanjima, kao u "običnim" permutacijama, cijeli niz objekata odjednom, ali postoji jedna stvar: u ovom se skupu jedan ili više elemenata (objekata) ponavlja. Ispunite sljedeći standard:

Zadatak 12

Koliko se različitih kombinacija slova može dobiti preslagivanjem karata sa sljedećim slovima: K, O, L, O, K, O, L, L, H, I, K?

Riješenje: u slučaju da su sva slova bila različita, tada treba primijeniti trivijalnu formulu, međutim, sasvim je jasno da će za predloženi set karata neke manipulacije raditi "u praznom hodu", pa, na primjer, ako zamijenite bilo koja dva kartice sa slovima "K u bilo kojoj riječi, to će biti ista riječ. Štoviše, fizički karte mogu biti vrlo različite: jedna može biti okrugla s otisnutim slovom "K", druga je četvrtasta s nacrtanim slovom "K". Ali prema značenju problema, čak i takve karte smatrao istim, budući da uvjet pita o kombinacijama slova.

Sve je vrlo jednostavno - ukupno: 11 kartica, uključujući pismo:

K - ponovljeno 3 puta;
O - ponovljeno 3 puta;
L - ponovljeno 2 puta;
b - ponovljeno 1 put;
H - ponovljeno 1 put;
I - ponavlja 1 put.

Provjera: 3 + 3 + 2 + 1 + 1 + 1 = 11, što smo htjeli provjeriti.

Prema formuli broj permutacija s ponavljanjima:
mogu se dobiti razne kombinacije slova. Više od pola milijuna!

Za brzi izračun velike faktorijelne vrijednosti prikladno je koristiti standardnu ​​Excelovu funkciju: poentiramo u bilo kojoj ćeliji =ČINJENICA(11) i kliknite Unesi.

U praksi je sasvim prihvatljivo ne zapisati opću formulu i, osim toga, izostaviti jedinične faktorijele:

Ali potrebni su preliminarni komentari o ponovljenim slovima!

Odgovor: 554400

Još jedan tipičan primjer permutacija s ponavljanjima nalazimo u problemu slaganja šahovskih figura koje se nalaze u skladištu gotova rješenja u pripadajućem pdf-u. A za neovisno rješenje smislio sam zadatak s manje šablona:

Zadatak 13

Alexey se bavi sportom, a 4 dana u tjednu - atletikom, 2 dana - vježbama snage i 1 dan odmora. Na koliko načina može rasporediti svoje tjedne satove?

Formula ovdje ne funkcionira jer uzima u obzir permutacije koje se preklapaju (na primjer, kada se vježbe snage u srijedu zamijene vježbama snage u četvrtak). I opet - zapravo, ista 2 treninga snage mogu se jako razlikovati jedan od drugog, ali u kontekstu zadatka (u smislu rasporeda), smatraju se istim elementima.

Rješenje u dva retka i odgovor na kraju lekcije.

Kombinacije s ponavljanjima

Karakteristična značajka ove vrste kombinacije je da se uzorak izvlači iz nekoliko skupina, od kojih se svaka sastoji od istih objekata.

Danas su svi vrijedno radili, pa je vrijeme da se okrijepite:

Zadatak 14

U studentskoj menzi prodaju se kobasice u tijestu, sirnice i krafne. Na koliko se načina može kupiti pet kolača?

Riješenje: odmah obratite pozornost na tipični kriterij za kombinacije s ponavljanjima - prema stanju, ne skup predmeta kao takvih, već različite vrste objekti; pretpostavlja se da je na akciji najmanje pet hrenovki, 5 kolača sa sirom i 5 krafni. Pite u svakoj skupini su, naravno, različite - jer potpuno identične krafne mogu se simulirati samo na računalu =) Međutim, fizičke karakteristike pita nisu bitne u smislu problema, a hrenovke / kolači od sira / krafne u svojim skupinama smatraju se istima.

Što može biti u uzorku? Prije svega treba napomenuti da će u uzorku sigurno biti identične pite (jer biramo 5 komada, a na izbor su ponuđene 3 vrste). Mogućnosti za svačiji ukus: 5 hrenovki, 5 torti sa sirom, 5 krafni, 3 hrenovke + 2 torte sa sirom, 1 hrenovka + 2 + torte sa sirom + 2 krafne itd.

Kao i kod "običnih" kombinacija, redoslijed odabira i postavljanja pita u uzorak nije bitan - samo su odabrali 5 komada i to je to.

Koristimo formulu broj kombinacija s ponavljanjima:
način na koji možete kupiti 5 pita.

Uživajte u jelu!

Odgovor: 21

Koji se zaključak može izvući iz mnogih kombinatornih problema?

Ponekad je najteže razumjeti stanje.

Sličan primjer za rješenje "uradi sam":

Zadatak 15

Novčanik sadrži prilično velik broj kovanica od 1, 2, 5 i 10 rubalja. Na koliko se načina iz novčanika mogu izvaditi tri novčića?

U svrhu samokontrole, odgovorite na nekoliko jednostavnih pitanja:

1) Mogu li se svi novčići u uzorku razlikovati?
2) Navedite "najjeftiniju" i "najskuplju" kombinaciju kovanica.

Rješenje i odgovori na kraju lekcije.

Iz osobnog iskustva mogu reći da su kombinacije s ponavljanjima najrjeđi gost u praksi, što se ne može reći za sljedeće vrste kombinacija:

Plasmani s ponavljanjima

Iz skupa koji se sastoji od elemenata biraju se elementi, a bitan je redoslijed elemenata u svakom uzorku. I sve bi bilo u redu, ali prilično neočekivana šala je da možemo odabrati bilo koji predmet originalnog skupa koliko god puta želimo. Slikovito rečeno, od "mnoštva se neće smanjiti".

Kada se to događa? Tipičan primjer je šifrirana brava s nekoliko diskova, no zbog razvoja tehnologije relevantnije je uzeti u obzir njezinog digitalnog potomka:

Zadatak 16

Koliko ima 4-znamenkastih pin kodova?

Riješenje: zapravo, za rješavanje problema dovoljno je poznavati pravila kombinatorike: prvu znamenku pin koda možete odabrati na različite načine i načine - druga znamenka pin koda i na isto toliko načina – trećina i isto toliko – četvrti. Dakle, prema pravilu množenja kombinacija, četveroznamenkasti pin kod može se sastaviti: na načine.

A sada s formulom. Po uvjetu nudi nam se skup brojeva iz kojeg se odabiru i postavljaju brojevi određenim redoslijedom, dok se brojevi u uzorku mogu ponavljati (tj. bilo koja znamenka izvornog skupa može se koristiti proizvoljan broj puta). Prema formuli za broj plasmana s ponavljanjima:

Odgovor: 10000

Što vam ovdje pada na pamet ... ... ako bankomat "pojede" karticu nakon trećeg neuspješnog pokušaja unosa pin koda, onda su šanse da ga nasumično pokupi vrlo iluzorne.

A tko je rekao da kombinatorika nema nikakvog praktičnog smisla? Kognitivni zadatak za sve čitatelje stranice:

Problem 17

Prema državnom standardu, registarska pločica automobila sastoji se od 3 brojke i 3 slova. U ovom slučaju nije dopušten broj s tri nule, a slova se biraju iz skupa A, B, E, K, M, H, O, R, C, T, U, X (korištena su samo ona ćirilična slova čiji je način pisanja usklađen s latiničnim slovima).

Koliko se različitih registarskih pločica može sastaviti za regiju?

Ne tako, usput, i puno. U velikim regijama ovaj broj nije dovoljan, pa za njih postoji nekoliko kodova za natpis RUS.

Rješenje i odgovor na kraju lekcije. Ne zaboravite koristiti pravila kombinatorike ;-) … Htio sam se pohvaliti da sam ekskluzivan, ali pokazalo se da nije ekskluzivan =) Pogledao sam Wikipediju - ima izračuna, ali bez komentara. Iako je u obrazovne svrhe, vjerojatno, malo ljudi to riješilo.

Našoj uzbudljivoj lekciji došao je kraj, a na kraju želim reći da niste uzalud gubili vrijeme - iz razloga što formule kombinatorike nalaze još jednu važnu praktičnu primjenu: nalaze se u raznim zadacima na teorija vjerojatnosti,
i u zadaci na klasičnu definiciju vjerojatnosti- osobito često

Hvala svima na aktivnom sudjelovanju i vidimo se uskoro!

Rješenja i odgovori:

Zadatak 2: Riješenje: pronađite broj svih mogućih permutacija 4 karte:

Kada je karta s nulom na 1. mjestu, broj postaje troznamenkasti, pa te kombinacije treba isključiti. Neka je nula na prvom mjestu, tada se preostale 3 znamenke u najmanje značajnim znamenkama mogu preurediti na različite načine.

Bilješka : jer ima nekoliko kartica, lako je navesti sve takve opcije ovdje:
0579
0597
0759
0795
0957
0975

Dakle, iz predloženog skupa možete napraviti:
24 - 6 = 18 četveroznamenkastih brojeva
Odgovor : 18

Zadatak 4: Riješenje: 3 karte se mogu odabrati na 36 načina.
Odgovor : 7140

Zadatak 6: Riješenje: načine.
Još jedno rješenje : načini na koje možete odabrati dvije osobe iz grupe i i
2) "Najjeftiniji" set sadrži 3 kovanice rublje, a "najskuplji" set sadrži 3 kovanice od deset rubalja.

Zadatak 17: Riješenje: načini na koje možete napraviti digitalnu kombinaciju registarske pločice, a jedan od njih (000) treba isključiti:.
načini na koje možete napraviti kombinaciju slova od broja automobila.
Po pravilu množenja kombinacija sve se može sastaviti:
brojevi automobila
(svaki digitalna kombinacija kombinirana sa svakim kombinacija slova).
Odgovor : 1726272

KOMBINATORIKA

Kombinatorika je grana matematike koja proučava probleme izbora i rasporeda elemenata iz nekog osnovnog skupa u skladu sa zadanim pravilima. Formule i principi kombinatorike koriste se u teoriji vjerojatnosti za izračunavanje vjerojatnosti slučajnih događaja i, sukladno tome, za dobivanje zakona raspodjele slučajnih varijabli. To pak omogućuje proučavanje zakonitosti masovnih slučajnih pojava, što je vrlo važno za ispravno razumijevanje statističkih zakonitosti koje se manifestiraju u prirodi i tehnici.

Pravila zbrajanja i množenja u kombinatorici

Pravilo zbroja. Ako se dvije radnje A i B međusobno isključuju, a radnja A se može izvesti na m načina, a B na n načina, tada se bilo koja od ovih radnji (bilo A ili B) može izvesti na n + m načina.

Primjer 1

U razredu je 16 dječaka i 10 djevojčica. Na koliko se načina može imenovati jedan pratitelj?

Riješenje

Za dežurstvo možete postaviti ili dječaka ili djevojčicu, tj. na dužnosti može biti bilo koji od 16 dječaka ili bilo koja od 10 djevojčica.

Prema pravilu zbroja dobivamo da se jedan dežurni može rasporediti na 16+10=26 načina.

Pravilo proizvoda. Neka se zahtijeva uzastopno izvršiti k radnji. Ako se prva radnja može izvesti na n 1 načina, druga radnja na n 2 načina, treća na n 3 načina, i tako dalje do k-te radnje koja se može izvesti na n k načina, tada svih k radnji zajedno mogu biti izvedena:

načine.

Primjer 2

U razredu je 16 dječaka i 10 djevojčica. Na koliko se načina mogu imenovati dva pratitelja?

Riješenje

Prva dežurna osoba može biti dječak ili djevojčica. Jer u razredu ima 16 dječaka i 10 djevojčica, tada prvog dežurnog možete imenovati na 16 + 10 = 26 načina.

Nakon što smo odabrali prvog dežurnog, možemo izabrati drugog od preostalih 25 ljudi, tj. 25 načina.

Po teoremu o množenju, dva polaznika mogu se izabrati na 26*25=650 načina.

Kombinacije bez ponavljanja. Kombinacije s ponavljanjima

Klasični problem kombinatorike je problem broja kombinacija bez ponavljanja, čiji se sadržaj može izraziti pitanjem: koliko načine limenka izabrati m od n različitih predmeta?

Primjer 3

Morate odabrati 4 od 10 različitih knjiga dostupnih kao dar. Na koliko načina se to može učiniti?

Riješenje

Trebamo izabrati 4 od 10 knjiga, a redoslijed izbora nije bitan. Dakle, morate pronaći broj kombinacija od 10 elemenata za 4:

.

Razmotrimo problem broja kombinacija s ponavljanjima: postoji r identičnih objekata svakog od n različitih tipova; koliko načine limenka izabrati m() od ove (n*r) stavke?

.

Primjer 4

U slastičarnici su se prodavale 4 vrste kolača: napoleoni, ekleri, prhki kolači i lisnati. Na koliko se načina može kupiti 7 kolača?

Riješenje

Jer među 7 kolača mogu biti kolači iste vrste, tada je broj načina na koji se može kupiti 7 kolača određen brojem kombinacija s ponavljanjem od 7 do 4.

.

Plasmani bez ponavljanja. Plasmani s ponavljanjima

Klasični problem kombinatorike je problem broja plasmana bez ponavljanja, čiji se sadržaj može izraziti pitanjem: koliko načine limenka izabrati i mjesto na m drugačiji mjesta m od n drugačiji stavke?

Primjer 5

Neke novine imaju 12 stranica. Na stranicama ovih novina potrebno je postaviti četiri fotografije. Na koliko se načina to može učiniti ako ni na jednoj stranici novina ne smije biti više od jedne fotografije?

Riješenje.

U ovom problemu ne odabiremo samo fotografije, već ih postavljamo na određene stranice novina, a svaka stranica novina ne smije sadržavati više od jedne fotografije. Time se problem svodi na klasični problem određivanja broja plasmana bez ponavljanja od 12 elemenata po 4 elementa:

Dakle, 4 fotografije na 12 stranica mogu se posložiti na 11880 načina.

Također, klasični zadatak kombinatorike je problem broja plasmana s ponavljanjima, čiji se sadržaj može izraziti pitanjem: koliko načine limenka vasbvojska i mjesto na m drugačiji mjesta m od n predmetaSredi koji tamo je isto?

Primjer 6

Dječak je iz kompleta za društvenu igru ​​imao pečate s brojevima 1, 3 i 7. Odlučio je pomoću tih pečata na sve knjige staviti peteroznamenkastih brojeva - kako bi sastavili katalog. Koliko različitih peteroznamenkastih brojeva dječak može sastaviti?

Permutacije bez ponavljanja. Permutacije s ponavljanjima

Klasični problem kombinatorike je problem broja permutacija bez ponavljanja, čiji se sadržaj može izraziti pitanjem: koliko načine limenka mjesto n razne stavke na n drugačiji mjesta?

Primjer 7

Koliko se "riječi" od četiri slova može sastaviti od slova riječi "brak"?

Riješenje

Opći skup čine 4 slova riječi "brak" (b, p, a, k). Broj "riječi" određen je permutacijama ova 4 slova, tj.

Za slučaj kada se među odabranim n elementima nalaze isti (selekcija s povratkom), problem broja permutacija s ponavljanjem može se izraziti pitanjem: Na koliko načina se n objekata može preurediti na n različitih mjesta ako među n objekata postoji k različitih vrsta (k< n), т. е. есть одинаковые предметы.

Primjer 8

Koliko se različitih kombinacija slova može napraviti od slova riječi "Mississippi"?

Riješenje

Ima 1 slovo "m", 4 slova "i", 3 slova "c" i 1 slovo "p", ukupno 9 slova. Stoga je broj permutacija s ponavljanjima

SAŽETAK POZADINE O ODSJEKU "KOMBINATORIKA"

Bilo koji od N elemenata može zauzeti prvo mjesto u nizu, stoga se dobiva N opcija. Na drugom mjestu - bilo koji, osim onog koji je već korišten za prvo mjesto. Stoga, za svaku od N već pronađenih opcija, postoje (N - 1) drugoplasirane opcije, a ukupan broj kombinacija postaje N*(N - 1).
Isto se može ponoviti za preostale elemente niza. Za posljednje mjesto ostaje samo jedna opcija - zadnji preostali element. Za pretposljednju - dvije opcije, i tako dalje.
Dakle, za niz od N elemenata koji se ne ponavljaju, moguće permutacije su jednake umnošku svih cijelih brojeva od 1 do N. Taj umnožak se zove N i N! (čitaj "en factorial").

U prethodnom slučaju, broj mogućih elemenata i broj mjesta u nizu su se podudarali, a njihov broj je bio jednak N. No moguća je situacija kada u nizu ima manje mjesta nego mogućih elemenata. Drugim riječima, broj elemenata u uzorku jednak je nekom broju M, a M< N. В этом случае задача определения возможных комбинаций может иметь два различных варианта.
Prvo, možda će biti potrebno izbrojati ukupan broj mogućih načina na koje se M elemenata iz N može poredati u nizu. Takvi načini su plasmani.
Drugo, istraživača može zanimati broj načina na koji se M elemenata može odabrati iz N. U ovom slučaju, redoslijed elemenata više nije važan, ali bilo koje dvije opcije moraju se razlikovati jedna od druge za barem jedan element . Takve se metode nazivaju kombinacijama.

Da bi se odredio broj smještaja M elemenata od N, može se pribjeći istom načinu zaključivanja kao u slučaju permutacija. Na prvom mjestu i dalje može biti N elemenata, na drugom (N - 1) i tako dalje. Ali za posljednje mjesto, broj mogućih opcija nije jedan, već (N - M + 1), jer će po završetku postavljanja još uvijek biti (N - M) neiskorištenih elemenata.
Dakle, broj plasmana preko M elemenata od N jednak je umnošku svih cijelih brojeva od (N - M + 1) do N, ili, ekvivalentno, kvocijentu N!/(N - M)!.

Očito je da će broj kombinacija M elemenata iz N biti manji od broja plasmana. Za svaku moguću kombinaciju postoji M! mogući rasporedi ovisno o redoslijedu elemenata ove kombinacije. Stoga, da biste pronašli ovaj broj, trebate podijeliti broj položaja na M elemenata od N s N!. Drugim riječima, broj kombinacija M elemenata iz N je N!/(M!*(N - M)!).

Izvori:

• broj kombinacija

Faktorijel prirodni broj je umnožak svih prethodnih prirodnih brojeva, uključujući i sam broj. Faktorijel nula je jednaka jedan. Čini se da je izračunavanje faktorijela broja vrlo jednostavno - dovoljno je pomnožiti sve prirodne brojeve koji nisu veći od zadanog. Međutim, vrijednost faktorijela raste tako brzo da se neki kalkulatori ne mogu nositi s ovim zadatkom.

Trebat će vam

• kalkulator, računalo

Uputa

Da biste izračunali faktorijel prirodnog broja, pomnožite sve koji ne prelaze zadani broj. Svaki broj se broji samo jednom. U obliku formule to se može napisati na sljedeći način: n! = 1*2*3*4*5*…*(n-2)*(n-1)*n, gdje je n prirodni broj čiji faktorijel treba izračunati.
0! uzima se jednak jedan (0!=1) Kako se argument povećava, vrijednost faktorijela raste vrlo brzo, tako da uobičajeni (računovodstveni) faktorijel od 15 umjesto rezultata može dati pogrešku.

Da biste izračunali faktorijel velikog prirodnog broja, uzmite inženjerski kalkulator. Odnosno takav kalkulator na čijoj se tipkovnici nalaze simboli matematičkih funkcija (cos, sin, √). Unesite izvorni broj u kalkulator, a zatim kliknite gumb faktorijel. Obično gumb poput "n!" ili slično (umjesto "n" može biti "N" ili "x", ali uskličnik "!" u zapisu faktorijela u svakom slučaju mora biti prisutan).
S velikim vrijednostima argumenta, rezultati izračuna počinju se prikazivati ​​u "eksponencijalnom" (eksponencijalnom) obliku. Tako bi, na primjer, faktorijel od 50 bio u obliku: 3,0414093201713378043612608166065e+64 (ili sličan). Da biste dobili rezultat izračuna u uobičajenom obliku, dodajte onoliko nula broju prikazanom prije simbola "e" koliko je naznačeno nakon "e +" (ako, naravno, ima dovoljno prostora).