Kombinasjoner med gjentakelser av elementer. Kombinatoriske algoritmer: kombinasjonsindeks, delsettpartisjonsindeks Bringer algoritmer til konstant kompleksitet
Alle N elementer, og ingen gjentas, så er dette et problem med antall permutasjoner. Løsningen kan finnes enkel. Det første stedet i en rad kan være et av N elementer, derfor er det N alternativer. På andreplass - hvilken som helst, bortsett fra den som allerede er brukt til førsteplassen. Derfor, for hvert av de N alternativene som allerede er funnet, er det (N - 1) andreplassalternativer, og det totale antallet kombinasjoner blir N*(N - 1).
Det samme kan gjentas for de resterende elementene i serien. For den aller siste plassen er det bare ett alternativ igjen - det siste gjenværende elementet. For den nest siste er det to alternativer, og så videre.
Derfor, for en serie av N ikke-repeterende elementer, er de mulige permutasjonene lik produktet av alle heltall fra 1 til N. Dette produktet kalles faktorialet til N og betegnes N! (les «en factorial»).
I det forrige tilfellet falt antall mulige elementer og antall plasser i raden sammen, og antallet var lik N. Men en situasjon er mulig når det er færre plasser i raden enn det er mulige elementer. Med andre ord, antall elementer i prøven er lik et visst antall M, og M< N. В этом случае задача определения количества возможных комбинаций может иметь два различных варианта.
Først kan det være lurt å telle det totale antallet mulige måter som M-elementer av N kan ordnes i en rad. Disse måtene kalles arrangementer.
For det andre kan forskeren være interessert i antall måter M-elementer kan velges fra N. I dette tilfellet er ikke lenger rekkefølgen på elementene viktig, men to alternativer må avvike fra hverandre med minst ett element . Slike metoder kalles kombinasjoner.
For å finne antall plasseringer av M-elementer ut av N, kan du ty til samme metode for resonnement som ved permutasjoner. Det kan fortsatt være N elementer i første omgang, N - 1 på andre plass, og så videre. Men for den siste plassen er antallet mulige alternativer ikke lik én, men (N - M + 1), siden når plasseringen er fullført, vil det fortsatt være (N - M) ubrukte elementer.
Dermed er antallet plasseringer av M elementer fra N lik produktet av alle heltall fra (N - M + 1) til N, eller, hva er det samme, kvotienten N!/(N - M)!.
Det er klart at antall kombinasjoner av M elementer fra N vil være mindre enn antall plasseringer. For hver mulig kombinasjon er det en M! mulige plasseringer avhengig av rekkefølgen på elementene i denne kombinasjonen. Derfor, for å finne denne mengden, må du dele antall plasseringer av M elementer fra N med N!. Med andre ord, antall kombinasjoner av M elementer fra N er lik N!/(M!*(N - M)!).
En kombinasjon er et uordnet utvalg av elementer i et begrenset sett med et fast antall og uten gjentakelser av elementer. Ulike kombinasjoner må være forskjellige i minst ett element, og rekkefølgen på elementene spiller ingen rolle. For eksempel, fra settet med alle vokaler av latinske bokstaver (AEIOU), kan du lage 10 forskjellige kombinasjoner av 3 bokstaver, og danner følgende uordnede trillinger:
AEI, AEO, AEU, AIO, AIU, AOU, EIO, EIU, EOU, IOU.
Det er interessant å merke seg at fra de samme fem bokstavene kan du også få 10 forskjellige kombinasjoner hvis du kombinerer dem 2 bokstaver om gangen, slik at følgende uordnede par:
AE, AI, AO, AU, EI, EO, EU, IO, IU, OU.
Men hvis du kombinerer de samme latinske vokalbokstavene med 4, vil du bare få følgende 5 forskjellige kombinasjoner:
AEIO, AEIU, AIOU, EIOU, AEOU.
Generelt, for å betegne antall kombinasjoner av n forskjellige elementer av m elementer, brukes følgende funksjonelle, indeks- eller vektorsymbolikk (Appel):
Uavhengig av notasjonsformen, kan antall kombinasjoner av n elementer med m elementer bestemmes ved hjelp av følgende multiplikasjons- og faktorformler:
Det er lett å kontrollere at resultatet av beregninger ved bruk av disse formlene sammenfaller med resultatene av eksemplet diskutert ovenfor med kombinasjoner av vokaler i latinske bokstaver. Spesielt med n=5 og m=3 vil beregninger ved hjelp av disse formlene gi følgende resultat:
I det generelle tilfellet har formler for antall kombinasjoner en kombinatorisk betydning og er gyldige for alle heltallsverdier av n og m, slik at n > m > 0. Hvis m > n og m< 0, то число сочетаний равно 0, так как в этом случае основное множество из n элементов вообще не имеет подмножеств мощности m:
I tillegg er det nyttig å huske følgende begrensende antall kombinasjoner, som enkelt kan kontrolleres ved direkte substitusjon i multiplikasjons- og faktorformlene:
Det bør også bemerkes at multiplikasjonsformelen forblir gyldig selv når n er et reelt tall, så lenge m fortsatt er en heltallsverdi. Men da mister resultatet av beregningen ved å bruke det, mens det opprettholder formell gyldighet, sin kombinatoriske betydning.
IDENTITETER AV KOMBINASJONER
Den praktiske bruken av multiplikative og faktorielle formler for å bestemme antall kombinasjoner for vilkårlige verdier av n og m viser seg å være av liten produktivitet på grunn av den eksponentielle veksten av faktorproduktene til deres teller og nevner. Selv for relativt små verdier på n og m overskrider disse produktene ofte evnene til å representere heltall i moderne data- og programvaresystemer. Dessuten viser deres verdier seg å være betydelig større enn den resulterende verdien av antall kombinasjoner, som kan være relativt liten. For eksempel er antall kombinasjoner av n=10 med m=8 elementer bare 45. For å finne denne verdien ved å bruke faktorformelen, må du først beregne mye større verdier på 10! i telleren og 8! i nevneren:
For å eliminere tidkrevende operasjoner for behandling av store mengder, for å bestemme antall kombinasjoner, kan du bruke forskjellige gjentakelsesrelasjoner, som direkte følger av multiplikasjons- og faktorformlene. Spesielt følger følgende gjentakelsesforhold fra den multiplikative formelen, som lar oss ta forholdet mellom indeksene utover tegnet på antall kombinasjoner:
Til slutt, å holde abonnenten konstant gir følgende gjentakelsesrelasjon, som enkelt oppnås fra faktorformelen for antall kombinasjoner:
Etter elementære transformasjoner kan de tre resulterende gjentaksrelasjonene representeres i følgende former:
Hvis vi nå legger til venstre og høyre side av de to første formlene og reduserer resultatet med n, får vi en viktig gjentakelsesrelasjon, som kalles identiteten for å legge til kombinasjonstall:
Addisjonsidentiteten gir en grunnleggende gjentakelsesregel for effektivt å bestemme antall kombinasjoner for store verdier av n og m, siden den lar multiplikasjonsoperasjonene i faktorielle produkter erstattes av de enklere addisjonsoperasjonene, og for mindre antall kombinasjoner. Spesielt ved å bruke addisjonsidentiteten er det nå enkelt å bestemme antall kombinasjoner av n=10 med m=8 elementer, som ble diskutert ovenfor, ved å utføre følgende sekvens av tilbakevendende transformasjoner:
I tillegg, fra addisjonsidentiteten kan man utlede flere nyttige relasjoner for å beregne endelige summer, spesielt formelen for summering med nedskreven skrift, som har følgende form:
Denne relasjonen oppnås hvis vi i addisjonsidentiteten utvider gjentakelsen langs begrepet med det største hevet skriftet mens dets subskript er større enn 0. Følgende numeriske eksempel illustrerer denne prosessen med tilbakevendende transformasjoner:
Subscript summeringsformelen brukes ofte til å beregne summen av potenser av naturlige tall. Spesielt, forutsatt m=1, ved å bruke denne formelen er det lett å finne summen av de første n tallene i den naturlige rekken:
En annen nyttig versjon av summeringsformelen kan oppnås ved å utvide gjentakelsen av addisjonsidentiteten langs begrepet med det minste hevet opp. Følgende numeriske eksempel illustrerer denne versjonen av tilbakevendende transformasjoner:
I det generelle tilfellet, som et resultat av slike transformasjoner, oppnås summen av antall kombinasjoner, hvor begge indeksene avviker med en fra naboleddene, og forskjellen i indeksene forblir konstant (i det betraktede eksemplet er det også lik én). Dermed får vi følgende summeringsformel for begge indeksene for kombinasjonstall:
I tillegg til gjentaksrelasjonene og summeringsformlene diskutert ovenfor, har mange andre nyttige identiteter for kombinasjonstall blitt oppnådd i kombinatorisk analyse. Den viktigste blant dem er symmetri identitet, som ser slik ut:
Gyldigheten til symmetriidentiteten kan verifiseres i følgende eksempel ved å sammenligne antall kombinasjoner av 5 elementer med 2 og med (5 2) = 3:
Symmetriidentiteten har en åpenbar kombinatorisk betydning, siden den ved å bestemme antall alternativer for å velge m elementer fra n elementer, samtidig etablerer antall kombinasjoner fra de gjenværende (nm) uvalgte elementene. Den angitte symmetrien oppnås umiddelbart ved å erstatte m med (nm) i faktorformelen for antall kombinasjoner:
Tall og kombinasjonsidentiteter er mye brukt i ulike områder av moderne beregningsmatematikk. Imidlertid er deres mest populære applikasjoner relatert til Newtons binomiale og Pascals trekant.
BINOMIALTEOREM
For å utføre ulike matematiske transformasjoner og beregninger er det viktig å kunne representere enhver naturlig potens til et algebraisk binomial (binomial) i form av et polynom. For små potenser kan det ønskede polynomet enkelt oppnås ved å direkte multiplisere binomialer. Spesielt er følgende formler for kvadratet og terningen av summen av to ledd velkjent fra løpet av elementær matematikk:
I det generelle tilfellet, for en vilkårlig grad n av et binomial, er den nødvendige representasjonen i form av et polynom gitt av Newtons binomiale teorem, som erklærer følgende likhet for å være sann:
Denne likheten kalles vanligvis Newtons binomiale. Polynomet på høyre side er dannet av summen av produktene av n ledd X og Y av binomialet på venstre side, og koeffisientene foran dem kalles binomiale og er lik antall kombinasjoner med indekser, som er hentet fra deres krefter. Gitt den spesielle populariteten til Newtons binomiale formel i kombinatorisk analyse, anses begrepene binomial koeffisient og antall kombinasjoner generelt som synonyme.
Tydeligvis er kvadrat- og terningssumformlene spesielle tilfeller av binomialsetningen for henholdsvis n=2 og n=3. For å håndtere høyere grader (n>3), bør Newtons binomiale formel brukes. Dens anvendelse for en fjerdegrads binomial (n=4) demonstreres av følgende eksempel:
Det skal bemerkes at binomialformelen var kjent allerede før Newton for middelalderske matematikere i det arabiske Øst- og Vest-Europa. Derfor er det generelt aksepterte navnet ikke historisk korrekt. Newtons fortjeneste er at han generaliserte denne formelen til tilfellet med en vilkårlig reell eksponent r, som kan ta alle positive eller negative rasjonelle og irrasjonelle verdier. I det generelle tilfellet har en slik Newton binomial formel en uendelig sum på høyre side og er vanligvis skrevet som følger:
For eksempel, med en positiv brøkverdi av eksponenten r=1/2, tatt i betraktning verdiene til de binomiale koeffisientene, oppnås følgende utvidelse:
I det generelle tilfellet er Newtons binomiale formel for enhver eksponent en spesiell versjon av Maclaurins formel, som gir utvidelsen av en vilkårlig funksjon til en potensserie. Newton viste det for |z|< 1 этот ряд сходится, и сумма в правой части становится конечной. При любой натуральной степени r = n в правой части также получается конечная сумма из (n+1) первых слагаемых, так как все C(n, k>n) = 0 . Hvis vi nå setter Z=X/Y og multipliserer venstre og høyre side med Yn, får vi en versjon av Newton binomialformelen diskutert ovenfor.
Til tross for sin universalitet, beholder binomialsetningen sin kombinatoriske betydning bare for ikke-negative heltallskrefter til binomialet. I dette tilfellet kan det brukes til å bevise flere nyttige identiteter for binomiale koeffisienter. Spesielt formler for å summere antall kombinasjoner etter abonnent og etter begge indekser ble diskutert ovenfor. Den manglende hevet oppsummeringsidentiteten kan enkelt fås fra Newtons binomiale formel ved å sette X = Y = 1 eller Z = 1 i den:
En annen nyttig identitet etablerer likheten mellom summene av binomiale koeffisienter med partall og oddetall. Det er umiddelbart hentet fra Newtons binomiale formel hvis X = 1 og Y = 1 eller Z = 1:
Til slutt, fra begge betraktede identiteter får vi identiteten til summen av binomiale koeffisienter med bare partall eller bare oddetall:
Basert på de vurderte identitetene og den tilbakevendende regelen om å fjerne indekser fra under tegnet av antall kombinasjoner, kan en rekke interessante sammenhenger oppnås. For eksempel, hvis vi i den hevede summeringsformelen erstatter n overalt med (n1) og fjerner indeksene i hvert ledd, får vi følgende relasjon:
Ved å bruke en lignende teknikk i formelen for summen av binomiale koeffisienter med partall og oddetall, er det mulig å bevise gyldigheten av for eksempel følgende relasjon:
En annen nyttig identitet lar deg enkelt beregne summen av produktene av symmetrisk plasserte binomiale koeffisienter av to binomialer av vilkårlige grader n og k ved å bruke følgende Cauchy-formel:
Gyldigheten til denne formelen følger av den nødvendige likheten av koeffisienter for enhver grad m av variabelen Z på venstre og høyre side av følgende identiske forhold:
I det spesielle tilfellet når n=k=m, med tanke på symmetriidentiteten, oppnås en mer populær formel for summen av kvadrater av binomiale koeffisienter:
Mange andre nyttige identiteter for binomiale koeffisienter kan finnes i den omfattende litteraturen om kombinatorisk analyse. Imidlertid er deres mest kjente praktiske anvendelse relatert til Pascals trekant.
PASCALS TREKANT
Pascals aritmetiske trekant danner en uendelig numerisk tabell som består av binomiale koeffisienter. Linjene er ordnet etter potenser av binomialer fra topp til bunn. I hver linje er de binomiale koeffisientene ordnet i stigende rekkefølge av de hevete til de tilsvarende kombinasjonstallene fra venstre til høyre. Pascals trekant er vanligvis skrevet enten i likebenet eller rektangulær form.
Mer visuelt og vanlig er det likebenede formatet, der de binomiale koeffisientene, forskjøvet, danner en uendelig likebenet trekant. Det første fragmentet for binomialer opp til 4. grad (n=4) har følgende form:
Generelt gir Pascals likebente trekant en praktisk geometrisk regel for å bestemme binomiale koeffisienter, som er basert på addisjonsidentiteter og kombinasjonstallsymmetrier. Spesielt, i henhold til addisjonsidentiteten, er enhver binomial koeffisient summen av de to koeffisientene i den forrige raden nærmest den. I følge symmetriidentiteten er Pascals likebente trekant symmetrisk med hensyn til halveringslinjen. Dermed er hver av linjene et numerisk palindrom av binomiale koeffisienter. De angitte algebraiske og geometriske egenskapene gjør det mulig å enkelt utvide Pascals likebenede trekant og konsekvent finne verdiene til binomiale koeffisienter for vilkårlige potenser.
Men for å studere ulike egenskaper ved Pascals trekant, er det mer praktisk å bruke det formelt mer strenge rektangulære formatet. I dette formatet er det spesifisert av en lavere trekantet matrise av binomiale koeffisienter, hvor de danner en uendelig rettvinklet trekant. Det første fragmentet av Pascals rette trekant for binomialer opp til 9. grad (n=9) har følgende form:
Geometrisk oppnås en slik rektangulær tabell ved å deformere Pascals likebenede trekant horisontalt. Som et resultat blir tallserien parallelt med sidesidene av Pascals likebente trekant til vertikaler og diagonaler av Pascals rettvinklede trekant, og horisontalene til begge trekantene faller sammen. Samtidig forblir reglene for addisjon og symmetri for binomiale koeffisienter gyldige, selv om Pascals rettvinklede trekant mister den visuelle symmetrien som er karakteristisk for sin likebente motpart. For å kompensere for dette, blir det mer praktisk å formelt analysere de ulike numeriske egenskapene til de binomiale koeffisientene for horisontalene, vertikalene og diagonalene til Pascals rettvinklede trekant.
Ved å starte analysen av horisontalene til Pascals rettvinklede trekant, er det lett å legge merke til at summen av elementene i en hvilken som helst rad med nummer n er lik 2n i samsvar med formelen for å summere binomialer med hevet skrift. Det følger av dette at summen av elementene over noen av de horisontale linjene med nummer n er lik (2 n 1). Dette resultatet blir ganske åpenbart hvis verdien av summen av elementene i hver horisontal er skrevet i det binære tallsystemet. For eksempel, for n=4 kan dette tillegget skrives som følger:
Her er et par flere interessante egenskaper til horisontaler som også er relatert til potenser av to. Det viser seg at hvis det horisontale tallet er en potens av to (n=2 k), så er alle dets indre elementer (bortsett fra de ytre) partall. Tvert imot vil alle tall på en horisontal linje være oddetall hvis tallet er én mindre enn en potens av to (n=2 k 1). Gyldigheten av disse egenskapene kan verifiseres ved å kontrollere pariteten til de interne binomiale koeffisientene, for eksempel i horisontalene n=4 og n=3 eller n=8 og n=7.
La nå radnummeret til Pascals rettvinklede trekant være et primtall p. Da er alle dens interne binomiale koeffisienter delbare med p. Denne egenskapen er lett å sjekke for små verdier av prime konturtall. For eksempel er alle de interne binomiale koeffisientene til den femte horisontale (5, 10 og 5) åpenbart delbare med 5. For å bevise dette resultatet for et hvilket som helst horisontalt primtall p, må du skrive multiplikasjonsformelen for dens binomiale koeffisienter som følger:
Siden p er et primtall og derfor ikke er delelig med m!, må produktet av de gjenværende faktorene til telleren til denne formelen være delelig med m for å garantere en heltallsverdi av binomialkoeffisienten. Det følger at forholdet i firkantede parenteser er et naturlig tall N og det ønskede resultatet blir åpenbart:
Ved å bruke dette resultatet kan vi fastslå at tallene til alle horisontale linjer i Pascals trekant, hvis indre elementer er delbare med et gitt primtall p, er potenser av p, det vil si at de har formen n=p k. Spesielt hvis p=3, deler primtallet p ikke bare alle interne elementer i rad 3, som etablert ovenfor, men for eksempel den niende horisontale (9, 36, 84 og 126). På den annen side, i Pascals trekant er det umulig å finne en horisontal linje hvis indre elementer alle er delbare med et sammensatt tall. Ellers må tallet på en slik horisontal linje samtidig være en potens av primdelere av det sammensatte tallet som alle dens interne elementer er delt med, men dette er umulig av åpenbare grunner.
De vurderte betraktningene tillater oss å formulere følgende generelle kriterium for delbarheten til de horisontale elementene i Pascals trekant. Den største felles divisor (GCD) av alle interne elementer i en horisontal linje i Pascals trekant med nummer n er lik primtallet p hvis n=pk eller 1 i alle andre tilfeller:
GCD(Cmn) = ( ) for enhver 0< m < n .
Som konklusjon av analysen av horisontaler er det verdt å vurdere en mer interessant egenskap som rekken av binomiale koeffisienter som danner dem har. Hvis de binomiale koeffisientene til en horisontal linje med nummer n multipliseres med påfølgende potenser av tallet 10, og deretter alle disse produktene legges til, er resultatet 11 n. Den formelle begrunnelsen for dette resultatet er substitusjonen av verdiene X=10 og Y=1 (eller Z=1) i Newton-binomialformelen. Følgende numeriske eksempel illustrerer oppfyllelsen av denne egenskapen for n=5:
Analysen av egenskapene til vertikalene til Pascals rettvinklede trekant kan begynne med studiet av de individuelle egenskapene til deres bestanddeler. Formelt er hver vertikal m dannet av den følgende uendelige sekvensen av binomiale koeffisienter med en konstant hevet skrift (m) og en økning av underskriften:
Det er klart at når m=0 oppnås en sekvens av enere, og når m=1 dannes en serie naturlige tall. Når m=2 er vertikalen bygd opp av trekantetall. Hvert trekantet tall kan avbildes på et plan i form av en likesidet trekant, som er fylt med vilkårlige gjenstander (kjerner) arrangert i et sjakkbrettmønster. I dette tilfellet bestemmer verdien av hvert trekantet tall Tk antallet representerende kjerner, og indeksen viser hvor mange rader med kjerner som trengs for å representere det. For eksempel representerer 4 innledende trekantetall følgende konfigurasjoner av det tilsvarende antallet kjernefysiske "@"-symboler:
Det skal bemerkes at man på lignende måte kan introdusere kvadrattall S k , som oppnås ved å kvadrere naturlige tall og generelt mangekantet tall dannet ved regelmessig å fylle regulære polygoner. Spesielt kan de 4 første kvadrattallene representeres som følger:
For å gå tilbake til analysen av vertikalene i Pascals trekant, kan vi merke oss at den neste vertikalen ved m=3 er fylt med tetraedriske (pyramideformede) tall. Hvert slikt tall Pk spesifiserer antall kjerner som kan ordnes i form av et tetraeder, og indeksen bestemmer hvor mange horisontale trekantede lag med rader med kjerner som kreves for å skildre det i tredimensjonalt rom. I dette tilfellet må alle horisontale lag representeres som påfølgende trekanttall. Elementene i de følgende vertikalene i Pascals trekant for m>3 danner serier av hypertetraedale tall, som ikke har en visuell geometrisk tolkning på planet eller i tredimensjonalt rom, men formelt tilsvarer flerdimensjonale analoger av trekantede og tetraedale tall.
Selv om den vertikale tallserien til Pascals trekant har de betraktede individuelle formfunksjonene, er det for dem mulig å beregne delsummene av verdiene til de innledende elementene på samme måte, ved å bruke formelen for å summere antall kombinasjoner med subscript . I Pascals trekant har denne formelen følgende geometriske tolkning. Summen av verdiene til de n øvre binomiale koeffisientene til enhver vertikal er lik verdien av elementet til neste vertikal, som ligger en linje under. Dette resultatet stemmer også overens med den geometriske strukturen til trekantede, tetrahedale og hypertetrahedale tall, siden representasjonen av hvert slikt tall består av kjernelag som representerer tall av lavere orden. Spesielt kan det n-te trekanttallet T n oppnås ved å summere alle de naturlige tallene som representerer dets lineære lag:
På samme måte er det ikke vanskelig å finne det tetraedriske tallet Pn ved å beregne følgende sum av de første n trekanttallene som utgjør dets horisontale kjernelag:
I tillegg til horisontalene og vertikalene i Pascals rettvinklede trekant, kan man spore diagonale rader med elementer, som også er av interesse å studere egenskapene til. I dette tilfellet skilles det vanligvis mellom synkende og stigende diagonaler. De nedadgående diagonalene er parallelle med hypotenusen til Pascals rettvinklede trekant. De er dannet av serier av binomiale koeffisienter med en økning av begge indeksene. På grunn av identiteten til symmetri, faller de synkende diagonalene sammen i verdiene til elementene deres med de tilsvarende vertikale radene i Pascals trekant og gjentar derfor alle egenskapene deres diskutert ovenfor. Den angitte korrespondansen kan spores ved sammenfall av verdiene til elementene i den synkende diagonalen og den vertikale med et hvilket som helst tall n, hvis vertikale nuller ikke tas i betraktning:
Stigende diagonaler danner tallrekker geometrisk vinkelrett på hypotenusen til Pascals rettvinklede trekant. De er fylt med binomiale koeffisienter med en dekrement av den nedre og inkrement av hevet skrift. Spesielt danner de 7 øvre stigende diagonalene følgende numeriske sekvens uten å ta hensyn til de etterfølgende nullene:
Generelt inneholder det stigende diagonale tallet n følgende binomiale koeffisienter, summen av indeksene til hver av dem er lik (n1):
I kraft av addisjonsidentiteten for kombinasjonstall er hvert diagonalelement lik summen av to elementer som svarer i indekser fra de to foregående stigende diagonalene. Dette gjør at hver påfølgende stigende diagonal kan konstrueres ved parvis summering av tilstøtende horisontale elementer fra de to foregående diagonalene, og utvider Pascals trekant uendelig langs diagonalen. Følgende fragment av Pascals trekant illustrerer konstruksjonen av en stigende diagonal nummer 8 langs diagonaler nummerert 6 og 7:
Med denne konstruksjonsmetoden vil summen av elementene til enhver stigende diagonal, fra den tredje, være lik summen av elementene i de to foregående stigende diagonalene, og de to første diagonalene består av bare ett element, verdien hvorav er 1. Resultatene av de tilsvarende beregningene danner følgende numeriske serier, i henhold til hvilke du kan sjekke gyldigheten til den betraktede egenskapen til de stigende diagonalene til Pascals rettvinklede trekant:
Ved å analysere disse tallene kan du se at i henhold til en lignende lov dannes den velkjente sekvensen av Fibonacci-tall, der hvert neste tall er lik summen av de to foregående, og de to første tallene er lik 1:
Dermed kan vi trekke følgende viktige konklusjon: de diagonale summene av elementene i Pascals trekant utgjør Fibonacci-sekvensen. Denne egenskapen lar oss etablere et annet interessant trekk ved Pascals trekant. Ved å utvide Fibonacci-formelen rekursivt, er det lett å bevise at summen av de første n Fibonacci-tallene er lik (F n+2 1).
Derfor er summen av de binomiale koeffisientene som fyller de øvre n diagonalene også lik (F n+2 1). Det følger at summen av de første n diagonalene i Pascals trekant er 1 mindre enn summen av de binomiale koeffisientene som står på diagonalen med tall (n+2).
Avslutningsvis bør det bemerkes at de vurderte egenskapene til horisontalene, vertikalene og diagonalene til Pascals trekant ikke uttømmer det store utvalget av muligheter som forbinder ulike matematiske aspekter som ved første øyekast ikke har noe til felles. Slike uvanlige egenskaper tillater oss å betrakte Pascals trekant som et av de mest perfekte numeriske systemene, hvis evner ikke kan listes opp og er vanskelige å overvurdere.
Algoritmen for å beregne antall kombinasjoner ved å bruke Pascals trekant er presentert nedenfor:
Privat funksjon 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 Neste For i = 2 Til n For j = 1 Til i - 1 TT (i, j) = TT (i - 1, j - 1) + TT (i - 1, j) Neste Neste SochTT = TT (n, k) Sluttfunksjon
Hvis du trenger å beregne antall kombinasjoner mange ganger, kan det være mer praktisk å konstruere Pascals trekant én gang, og deretter motta data fra matrisen.
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 Som heltall ReDim Bevar TT (slutt, slutt) For i = start Til slutt TT (0, i) = 1 TT (i, i) = 1 Neste Hvis slutt< 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
Først må du ringe CreateTT-prosedyren. Du kan da finne antall kombinasjoner ved å bruke SochTT-funksjonen. Når du ikke lenger trenger trekanten, ring TerminateTT-prosedyren. I koden ovenfor, når du kaller SochTT-funksjonen, hvis trekanten ennå ikke er fullført til det nødvendige nivået, fullføres den ved å bruke BuildTT-prosedyren. Funksjonen henter deretter ønsket element i TT-matrisen og returnerer det.
Dim X () Som heltall Dim teller () Som heltall Dim K Som heltall Dim N Som heltall Public Sub Soch() Dim i Som heltall N = CInt(InndataBox("Skriv inn N")) K = CInt(Inntastingsboks("Skriv inn K ")) K = K + 1 ReDim X(N) For i = 1 Til N X(i) = i Neste txtOut.Text = "" ReDim Counter(K) Counter(0) = 1 SochGenerate 1 End Sub Private Sub SochGenerate( ByVal c Som heltall) Dim i Som heltall Dim j Som heltall Dim n1 Som heltall Dim ut() Som heltall Dim X1() Som heltall Hvis c = K Så Redim ut(K) X1 = X For i = 1 Til K - 1 n1 = 0 For j = 1 Til N Hvis X1(j)<>0 Da n1 = n1 + 1 Hvis n1 = Teller(i) Da Ut(i) = X1(j) X1(j) = 0 Avslutt For Slutt Hvis Neste txtOut.Text = txtOut.Text & CStr(Out(i)) Next txtOut.Text = txtOut.Text & vbCrLf Else For Counter(c) = Counter(c - 1) To N - c + 1 SochGenerate c + 1 Next End If End Sub
LISTER KOMBINASJONER AV NATURLIGE NUMMER
For å løse mange praktiske problemer, er det nødvendig å liste opp alle kombinasjoner av fast kardinalitet som kan oppnås fra elementene i et gitt begrenset sett, og ikke bare bestemme antallet. Med tanke på den alltid eksisterende muligheten for heltallsnummerering av elementene i et begrenset sett, er det i de fleste tilfeller tillatt å begrense oss til bruken av algoritmer for å telle kombinasjoner av naturlige tall. Den mest naturlige og enkle av dem er algoritmen for å liste kombinasjoner av naturlige tall i leksigrafisk rekkefølge.
For å formelt beskrive denne algoritmen, er det praktisk å anta at hovedsettet, alle kombinasjoner av m elementer som må være oppført, danner påfølgende naturlige tall fra 1 til n. Deretter enhver kombinasjon av m Som et resultat av bestilling viser verdien i hver posisjon av en slik vektor av kombinasjoner seg naturlig å være begrenset i verdi ovenfra og under som følger: Den leksigrafiske algoritmen genererer sekvensielt slike kombinasjonsvektorer, og starter med den leksigrafisk minste vektoren, der alle posisjoner inneholder følgende minimumsverdier av elementer som er lik deres indekser: Hver suksessiv kombinasjonsvektor dannes fra den gjeldende etter å ha skannet elementene fra venstre til høyre for å finne elementet lengst til høyre som ennå ikke har nådd grenseverdien: Verdien av et slikt element bør økes med 1. Hvert element til høyre for det bør tildeles den minste mulige verdien, som er 1 mer enn naboen til venstre. Etter disse endringene vil den neste vektoren av kombinasjoner ha følgende elementsammensetning: Dermed vil den neste kombinasjonsvektoren være leksigrafisk større enn den forrige, siden verdiene til deres initiale (j1) elementer er like i verdi, og verdien av elementet i posisjon j er 1 større enn den forrige. . Det spesifiserte forholdet til økende leksigrafisk rekkefølge er garantert tilfredsstilt ved alle iterasjoner av algoritmen. Resultatet er en økende leksigrafisk sekvens, som fullføres av den leksigrafisk største kombinasjonsvektoren, der elementene i alle posisjoner har følgende maksimumsverdier: Den betraktede leksigrafiske algoritmen er illustrert av følgende eksempel, der det er nødvendig å liste opp i økende leksigrafisk rekkefølge alle 15 kombinasjoner av n=6 første naturlige tall med m=4 tall, det vil si alle mulige 4-elements undersett av hovedgenereringen sett (1, 2, 3, 4, 5, 6) fra 6 elementer. Beregningsresultatene er presentert i følgende tabell: I dette eksemplet er de største tillatte verdiene av tall i posisjonene til kombinasjonsvektorene henholdsvis 3, 4, 5 og 6. For å lette tolkningen av resultatene, i hver kombinasjonsvektor, elementet lengst til høyre, som har ennå ikke nådd sin maksimale verdi, er understreket. Numeriske indekser av kombinasjonsvektorer bestemmer tallene deres i leksigrafisk rekkefølge. I det generelle tilfellet kan det leksigrafiske tallet N for en hvilken som helst kombinasjon av n elementer med m beregnes ved å bruke følgende formel, der, av kosmetiske årsaker, Appel-symbolikk brukes til å betegne antall kombinasjoner: Spesielt vil følgende beregninger som bruker denne formelen for kombinasjonstallet (1, 3, 4, 6) av n=6 elementer av m=4 i leksigrafisk rekkefølge gi resultatet N=8, som tilsvarer eksemplet diskutert ovenfor: I det generelle tilfellet, ved å bruke identiteten for summen av antall kombinasjoner for begge indeksene, er det mulig å vise at tallet på den leksigrafisk minste kombinasjonen (1, ... i, ... m) når det beregnes ved hjelp av denne formel vil alltid være lik 1: Det er også åpenbart at tallet på den leksigrafisk største kombinasjonen (m, … nm+i, … n) når det beregnes ved hjelp av denne formelen, vil være lik antall kombinasjoner av n elementer med m: Formelen for å beregne leksigrafiske kombinasjonstall kan brukes til å løse det omvendte problemet, der du må bestemme kombinasjonsvektoren etter tallet i leksigrafisk rekkefølge. For å løse et slikt omvendt problem, må det skrives i form av en ligning, der alle de ukjente verdiene til elementene i vektoren til ønsket kombinasjon (C 1, ... C i, ... C m ) er konsentrert i antall kombinasjoner på høyre side, og den kjente forskjellen L av antall kombinasjoner er skrevet på venstre side av n elementer hver m og nummeret på den nødvendige kombinasjonen N: Løsningen på denne ligningen er gitt av følgende "grådige" algoritme, i løpet av iterasjonene som verdiene til elementene i vektoren til ønsket kombinasjon velges sekvensielt. Ved den innledende iterasjonen velges den minste mulige (innenfor sine begrensninger) verdi av C 1, der det første leddet på høyre side vil ha en maksimal verdi som ikke overstiger L: Nå skal venstre side av L reduseres med det første antallet kombinasjoner på høyre side med den valgte verdien av C 1, og på samme måte bestemme verdien av C 2 ved den andre iterasjonen: På samme måte bør alle påfølgende iterasjoner utføres for å velge verdiene til alle andre elementer C i av ønsket kombinasjon, opp til det siste elementet C m: Av åpenbare grunner kan verdien av det siste elementet C m bestemmes basert på likheten mellom dets antall kombinasjoner og restverdien til venstre side av L: Det skal bemerkes at verdien av det siste elementet i kombinasjonen C m kan finnes enda enklere, uten å oppgi de mulige verdiene: Implementeringen av iterasjoner av den betraktede algoritmen er illustrert av følgende eksempel, der det er nødvendig å bestemme kombinasjoner med tallet N=8 i leksigrafisk rekkefølge, hvis n=6 og m=4: Den algoritmiske evnen til å bestemme en kombinasjon med et gitt tall i leksigrafisk rekkefølge kan brukes i ulike retninger. Spesielt når du oppgir kombinasjoner i leksigrafisk rekkefølge, er det nødvendig å sikre en retur til enhver kombinasjon som ble oppnådd tidligere, det er nok å bare vite nummeret. I tillegg blir det mulig å generere kombinasjoner i hvilken som helst rekkefølge, som er regulert av en vilkårlig gitt sekvens av deres leksigrafiske tall. Nå presenterer vi en algoritme for å generere kombinasjoner i leksikografisk rekkefølge: 2 for i:= 1 til k gjør A[i] := i; 5 begynn å skrive(A, …, A[k]); 6 hvis A[k] = n så p:= p 1 ellers p:= k; 8 for i:= k ned til p do A[i] := A[p] + i p + 1 KOMBINASJONER MED RETTENDE ELEMENTER I motsetning til en klassisk kombinasjon, der alle elementer er forskjellige, danner en kombinasjon med repetisjoner et uordnet utvalg av elementer i et begrenset sett, der ethvert element kan vises uendelig ofte og ikke nødvendigvis er til stede i en enkelt kopi. I dette tilfellet er antallet gjentakelser av elementer vanligvis bare begrenset av lengden på kombinasjonen, og kombinasjoner som er forskjellige i minst ett element anses som forskjellige. For eksempel, ved å velge 4 valgfritt forskjellige tall fra settet 1, 2 og 3, kan du lage følgende 15 kombinasjoner med repetisjoner: 1111 1112 1113 1122 1123 1133 1222 1223 1233 1333 2222 2223 2233 2333 3333.
Generelt kan kombinasjoner med repetisjoner dannes ved å velge n elementer av vilkårlige typer. Imidlertid kan de alltid assosieres med påfølgende naturlige tall fra 1 til n. Da kan enhver kombinasjon av m valgfritt forskjellige tall i dette området skrives i vektorform, og ordne dem i ikke-avtagende rekkefølge fra venstre til høyre: Naturligvis, med denne formen for notasjon, kan alle naboelementer være like på grunn av muligheten for ubegrensede repetisjoner. Imidlertid kan hver kombinasjonsvektor med repetisjoner av n elementer med m assosieres med en kombinasjonsvektor av (n+m−1) elementer med m, som er konstruert som følger: Det er klart at for alle verdier av elementene til vektor f, er elementene i vektor C garantert forskjellige og strengt ordnet i økende rekkefølge av verdiene fra området fra 1 til (n+m1): Tilstedeværelsen av en en-til-en korrespondanse mellom elementene i kombinasjonsvektorene f og C tillater oss å foreslå følgende enkle metode for systematisk å liste kombinasjoner med repetisjoner av n elementer med m. Det er bare nødvendig å liste, for eksempel, i leksigrafisk rekkefølge, alle C-kombinasjoner av (n+m1) elementer av m, sekvensielt transformere elementene til hver av dem til de tilsvarende elementene av kombinasjoner med repetisjoner f ved å bruke følgende formel: Som et resultat dannes en sekvens av vektorer av kombinasjoner med gjentakelser av elementer, som er ordnet i rekkefølgen generert ved å liste de tilsvarende kombinasjonene uten gjentakelser av elementer. Spesielt for å oppnå ovennevnte sekvens av kombinasjoner av 3 sifre 1, 2 og 3 med repetisjoner av 4 sifre, er det nødvendig å liste opp i leksigrafisk rekkefølge alle kombinasjoner uten repetisjoner av 6 sifre 1,2,3,4, 5 og 6 er 4 sifre hver, og konverterer dem som angitt. Følgende eksempel viser en slik konvertering av kombinasjonen (1,3,4,6) med det leksikografiske tallet 8: Den vurderte en-til-en-korrespondansen mellom kombinasjoner med og uten gjentakelser av elementer betyr at settene deres er like kraftige. Derfor, i det generelle tilfellet, er antall kombinasjoner med repetisjoner av n elementer med m lik antall kombinasjoner uten repetisjoner av (n+m1) elementer med m. Ved å bruke den samme symbolikken for å betegne antall kombinasjoner med repetisjoner f og uten repetisjoner C, kan denne likheten skrives som følger: Det er lett å sjekke at for eksemplet vurdert ovenfor, hvor n=3 og m=4, vil antall repetisjonskombinasjoner være lik 15, som sammenfaller med resultatet av deres direkte liste: Det skal bemerkes at, i motsetning til den klassiske versjonen, er verdiene til kombinasjonsparametrene med repetisjoner n og m ikke direkte relatert til hverandre, derfor f(n,m)>0 for enhver kombinasjon av deres positive verdier. De tilsvarende grensebetingelsene bestemmes fra likheten mellom verdiene av (n+m1) og (n1) eller (n+m1) og m: Det burde også være ganske åpenbart at hvis m er lik 1, så er ingen repetisjoner av elementer mulig, og derfor vil følgende likhet være sann for enhver positiv verdi på n>0: I tillegg, for antall kombinasjoner med repetisjoner for alle positive verdier av n og m, er følgende gjentakelsesrelasjon gyldig, som ligner addisjonsidentiteten for antall kombinasjoner uten gjentakelser av elementer: Faktisk blir den til den indikerte tilleggsidentiteten ved formell substitusjon av tilsvarende antall kombinasjoner uten repetisjoner til venstre og høyre side: Den betraktede gjentakelsesrelasjonen kan brukes til å effektivt bestemme antall kombinasjoner med repetisjoner, når det er viktig å eliminere de arbeidskrevende operasjonene med å beregne faktorielle produkter og erstatte dem med enklere addisjonsoperasjoner. I dette tilfellet, for å beregne verdien av f(n,m), trenger du bare å bruke denne gjentakelsesrelasjonen til du får summen av leddene på formen f(1,m) og f(i,1), der i tar verdier i området fra n til 1. Per definisjon av mengden er slike termer lik henholdsvis 1 og i. Følgende eksempel illustrerer bruken av denne transformasjonsteknikken for tilfellet med n=3 og m=4: LISTING AV BINÆRE KOMBINASJONER Ved implementering av kombinasjoner i maskinvare eller programmering i assemblerspråk er det viktig å kunne behandle kombinasjonsposter i binært format. I dette tilfellet bør enhver kombinasjon av n elementer av m spesifiseres i form av et n-bits binært tall (B n,...B j,...B 1), der m enhetssifre indikerer elementene i kombinasjon, og de resterende (nm) sifrene har nullverdier. Åpenbart, med denne formen for notasjon, må forskjellige kombinasjoner avvike i arrangementet av enernes sifre, og det er bare C(n,m) måter å arrangere m enere eller (nm) nuller i et n-bit binært sett. For eksempel viser følgende tabell alle 6 slike binære kombinasjoner, som gir 4-bits binære tall for alle kombinasjoner av 4 elementer i et vilkårlig sett (E 1 , E 2 , E 3 , E 4 ) med 2: I det generelle tilfellet kommer oppgaven med å telle opp slike binære kombinasjoner ned til et systematisk søk av alle n-bit binære sett med forskjellige arrangementer av m en og (nm) null biter. I den enkleste formen implementeres et slikt søk ved hjelp av forskjellige metoder for å transponere tilstøtende biter med et skift (transpositive-shift-algoritmer). Dette er iterative algoritmer, og navnene deres gjenspeiler arten av operasjonene som utføres på hvert trinn. Iterative prosedyrer for transpositive-shift-algoritmer danner sekvenser av binære kombinasjoner som begynner med et binært sett, der alle er konsentrert i sifrene med lav orden (til høyre), og slutter når alle 1-ene er i sifrene av høy orden ( til venstre): Mens de samsvarer i innledende og endelige kombinasjoner, er disse sekvensene forskjellige i rekkefølgen som mellomliggende binære sett er oppført. I alle tilfeller dannes imidlertid hver påfølgende binær kombinasjon fra den forrige som et resultat av å utføre de tilsvarende transposisjons- og skiftoperasjonene. Samtidig er forskjellige transpositive-shift-algoritmer forskjellige i måten de velger et par biter for transponering og en gruppe biter for å skifte. Denne spesifisiteten er diskutert nedenfor for transposisjonsalgoritmer med venstre og høyre skift. I transposisjonsalgoritmen med et venstreskift, oppnås ved hvert trinn den neste binære kombinasjonen fra den gjeldende ved å erstatte det sifferparet 01 lengst til venstre med 10 (transponering) og flytte gruppen av ledende enhetssiffer, hvis noen, nær par 10 oppnådd etter transposisjonen (skift). Hvis det i dette tilfellet ikke er noen enheter i de ledende sifrene i den gjeldende binære kombinasjonen, utføres ikke skiftet, selv når den ledende enheten er oppnådd etter transponering i dette trinnet. Skiftet utføres heller ikke når det ikke er nuller i de mest signifikante bitene før paret 10 oppnådd etter transposisjonen. De betraktede handlingene er illustrert av følgende eksempel på å utføre to suksessive iterasjoner av denne algoritmen, hvor ved en iterasjon (15) bare transposisjon (T") utføres, og ved den andre iterasjonen (16) blir transposisjonen supplert med et skifte ( T"+S"): I høyreskift-transponeringsalgoritmen utføres konseptuelt lignende trinn ved hvert trinn. Bare transponering sikrer at bitene lengst til høyre av 01 erstattes med 10 (i stedet for de lengst til venstre), og så blir alle bitene til høyre for den forskjøvet til de minst signifikante bitene. Som tidligere utføres skiftet kun hvis det er enheter som kan forskyves til høyre. De betraktede handlingene er illustrert av følgende eksempel på å utføre to påfølgende iterasjoner av denne algoritmen, hvor ved en iterasjon (3) bare transposisjon (T") utføres, og ved den andre iterasjonen (4) blir transposisjonen supplert med et skifte ( T"+S"): Det skal bemerkes at iterasjonene til begge algoritmene kan skrives i additiv form hvis binære kombinasjoner tolkes som heltall i base 2-tallsystemet. Spesielt for transposisjonsalgoritmen med høyre skift, hver neste binære kombinasjon (B" n ,...B" j , ...B" 1), kan alltid hentes fra den gjeldende kombinasjonen (B n,...B j,...B 1) ved å utføre operasjonene med å legge til heltall ved å bruke følgende additive formel: I denne additive formelen betegner eksponentene for potenser av toer f og t henholdsvis antall lavordens nullsiffer i den gjeldende binære kombinasjonen og antall enere på rad til venstre for dem. For eksempel, for den fjerde binære kombinasjonen (001110) av n=6 sifre f =1 og t =3. Derfor vil beregning av neste binære kombinasjon ved å bruke additivformelen ved iterasjon 5 gi følgende resultat, tilsvarende å utføre transposisjons- og skiftoperasjoner: For en komparativ analyse av de betraktede transposisjonsalgoritmene med venstre og høyre skift, er det tilrådelig å sammenligne sekvensene av binære kombinasjoner som de genererer i sine iterasjoner. Følgende tabell viser to slike sekvenser av binære kombinasjoner av 4 elementer av 2, som oppnås av henholdsvis venstre (TSL) og høyre (TSR) skiftalgoritme: Ved å sammenligne disse to sekvensene kan du se at de er omvendt speil. Dette betyr at to binære kombinasjoner som er plassert i dem i samme avstand fra de innbyrdes motsatte ender av sekvensene deres, er et speilbilde av hverandre, det vil si at de faller sammen når indekseringen av bitene i noen av dem reverseres. For eksempel er det andre binære mønsteret fra begynnelsen av TSL-sekvensen (0101) et speilbilde av det binære mønsteret (1010) som er andre fra slutten av TSR-sekvensen. Generelt er enhver binær kombinasjon med nummer i i en sekvens et speilbilde av en binær kombinasjon med nummer (ni+1) i en annen sekvens. Dette forholdet mellom disse sekvensene er en konsekvens av den symmetriske karakteren til transposisjons- og skiftoperasjonene i de to betraktede algoritmene for oppregning av binære kombinasjoner. Det skal bemerkes at det binære formatet også kan brukes til å registrere kombinasjoner med gjentakelser av elementer. For å gjøre dette er det nødvendig å etablere en en-til-en-korrespondanse mellom kombinasjoner med repetisjoner og binære kombinasjoner, som er konstruert som følger. La det være en vilkårlig kombinasjon med repetisjoner, som oppnås ved å velge m valgfritt forskjellige elementer fra de n elementene i generatorsettet. For å etablere ønsket match, må du først legge til alle elementene i formingssettet (katten) til kombinasjonen, og deretter sortere den resulterende sammenkoblingen (sortere) slik at alle identiske elementer er side ved side. Resultatet er en sekvens av (n+m) elementer, der det er n grupper av identiske elementer. Det vil være totalt (n+m1) gap mellom elementer, blant disse vil det være (n1) gap mellom grupper av identiske elementer og m gap mellom elementer innenfor grupper. For klarhetens skyld kan du plassere symbolene "|" i de angitte mellomrommene. og "", henholdsvis. Hvis vi nå matcher 1 med mellomrommene mellom gruppene (|) og 0 til alle andre mellomrom (), får vi en binær kombinasjon. Den er dannet av et binært sett med (n+m1) biter, der (n1) er enere og m nullbiter, hvis plassering unikt tilsvarer den opprinnelige kombinasjonen med repetisjoner av elementene n til m. Den betraktede transformasjonsteknikken er illustrert av følgende eksempel på å konstruere en binær kombinasjon (1001101) ved å bruke en kombinasjon med repetisjoner (BBD), hvis elementer er valgt fra generasjonssettet med de fem første latinske bokstavene: Generelt sett bestemmer antallet slike binære sett antall måter å ordne (n1) enere (eller m nuller) i (n+m1) binære sifre. Denne verdien er åpenbart lik antall kombinasjoner fra (n+m1) med (n1) eller med m, det vil si C(n+m1,n1) eller C(n+m1,m), som er lik antall kombinasjoner med repetisjoner f( n,m) av n elementer, m hver. Å ha en en-til-en korrespondanse mellom kombinasjoner med repetisjoner og binære kombinasjoner, er det legitimt å redusere opptellingen av kombinasjoner med repetisjoner til oppregning av binære kombinasjoner, for eksempel ved å bruke transposisjonsalgoritmer med venstre- eller høyreforskyvning. Etter dette trenger du bare å gjenopprette de nødvendige kombinasjonene med repetisjoner ved å bruke de resulterende binære kombinasjonene. Dette kan alltid gjøres ved å bruke følgende gjenopprettingsteknikk. La hovedsettet, fra elementene hvor kombinasjoner med repetisjoner av m ikke nødvendigvis forskjellige elementer dannes, ordnes på en vilkårlig måte slik at hvert av elementene har et visst serienummer fra 1 til n. La oss også implementere opptellingen av binære kombinasjoner av (n+m1) binære sifre, der (n1) enere og m null sifre. Hver resulterende binær kombinasjon kan suppleres til venstre med et fiktivt enhetssiffer, og alle enhetssiffer kan nummereres fra venstre til høyre med heltall fra 1 til n. Da vil antallet nuller på rad etter hver i-te enhet av den binære kombinasjonen være lik antall forekomster av det i-te elementet i hovedsettet i den tilsvarende kombinasjonen med repetisjoner. Den betraktede teknikken er illustrert av følgende eksempel, der ved å bruke en binær kombinasjon (1001101) gjenopprettes en kombinasjon med repetisjoner av BBD, hvis elementer er valgt fra generasjonssettet av de fem første latinske bokstavene, skrevet i alfabetisk rekkefølge , og overlinjen indikerer elementer som er fraværende i denne kombinasjonen: Ved å utføre lignende handlinger under betingelsene i dette eksemplet, kan du liste opp alle de 35 binære kombinasjonene som danner 7-bits binære sett, der det er 4 enere og 3 nuller, og gjenopprette de tilsvarende kombinasjonene med repetisjoner av 5 elementer av 3. Eksempel // Kombinasjoner av 3 av 52 for (int i1 = 0; i1< 50; ++i1)
for (int i2 = i1+1; i2 < 51; ++i2)
for (int i3 = i2+1; i3 < 52; ++i3)
// ...
Her skal vi se på et mer komplekst problem, hvis løsning jeg ikke har funnet i RuNet (men jeg vil gi en lenke, men den formelen er tydeligvis feil) - basert på selve kombinasjonen (i dette tilfellet et sett med tre tall) finn indeksen. La oss anta, for nøyaktighetens skyld, etter å ha bestilt i1 = 3, i2 = 7, i3 = 12. En typisk generasjonsalgoritme er at vi genererer kombinasjoner av 2 av 52, og for hver slik kombinasjon i en nestet sløyfe genererer vi kombinasjoner av 3 av 50, og sjekker at indeksene (i3, i4, i5) i den nestede kombinasjonen gjør ikke sammenfaller med indeksene (i1, i2) i ekstern kombinasjon: C++ kode // EKSTERN KOMBINASJON for (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++ kode if (i3 >= i1) --i3; if (i3 >= i2) --i2; // lignende for i4, i5 Eksempelkode for delt indeks med 2, 3, 47 int get_split_2_3_47_index(int i1, int i2, int i3, int i4, int i5) ( // Indeks for kombinasjonen av 2 av 52, multiplisert med C(3, 50) int offset = ((52*51 - (51-i1) *(52-i1)) / 2 + (i2 - i1 - 1)) * 19600; // "Reindekser" den interne gruppen slik at nummereringen er 0...49 if (i3 >= i1 ) --i3; (i3 >= i2) --i3; if (i4 >= i2) --i5 // Legg til kombinasjonsindeksen med 3 // 0 // SUM for n = 0 x i3-1 KOMBINASJONER (2, 49-n) // = SUM for m = 50-i3 x 49 (m * (m-1) / 2) offset += (19600 - (( (49-i3)*(50-i3)*(99-2*i3)) / 6 - ((49-i3)*(50-i3 )) / 2) / 2 // 1: // SUM for n = i3+1 til i4-1 KOMBINASJONER (1, 49-n) offset += (((48-i3)*(49-i3) - (49-i4)*(50-i4)) / 2) ; // 2: // SUM for n = i4+1 med i5-1 (1) offset += (i5 - i4 - 1 ) Generelt sett vil jeg dele kombinatoriske algoritmer inn i følgende klasser: Antall kombinasjoner Kombinasjon fra n Ved k kalt et sett k elementer valgt fra data n elementer. Sett som bare avviker i rekkefølgen på elementene (men ikke i sammensetning) anses som identiske, dette er grunnen til at kombinasjoner er forskjellige fra plasseringer. Antall kombinasjoner av n Ved k
lik binomial koeffisient For en fast verdi n generere funksjon av antall kombinasjoner med repetisjoner fra n Ved k er: Den todimensjonale genereringsfunksjonen til antall kombinasjoner med repetisjoner er: Wikimedia Foundation. Se hva "Antall kombinasjoner" er i andre ordbøker: 70 sytti 67 68 69 70 71 72 73 40 50 60 70 80 90 100 Faktorisering: 2×5×7 romersk notasjon: LXX Binær: 100 0110 ... Wikipedia Lett tall, et betinget tall som unikt uttrykker det ytre forhold under fotografering (vanligvis lysstyrken til motivet og fotosensitiviteten til det fotografiske materialet som brukes). Enhver verdi av E. h kan velges flere ganger. kombinasjoner blenderåpning nummer ... ... Big Encyclopedic Polytechnic Dictionary En tallform som skiller to objekter både i forhold til et enkelt objekt og i forhold til mange objekter. Denne formen eksisterer ikke i moderne russisk, men det gjenstår rester av dens innflytelse. Så kombinasjoner av to tabeller (jf. flertall... ... Ordbok over språklige termer Kombinatorisk matematikk, kombinatorikk, en gren av matematikk viet til å løse problemer med å velge og arrangere elementer av et visst, vanligvis begrenset, sett i samsvar med gitte regler. Hver slik regel bestemmer konstruksjonsmetoden ... ... Matematisk leksikon I kombinatorikk er en kombinasjon av by et sett med elementer valgt fra et gitt sett som inneholder forskjellige elementer. Sett som bare avviker i rekkefølgen på elementene (men ikke i sammensetning) anses som identiske, disse kombinasjonene ... ... Wikipedia Engasjert i studiet av hendelser hvis forekomst ikke er kjent med sikkerhet. Det lar oss bedømme rimeligheten av å forvente forekomsten av noen hendelser sammenlignet med andre, selv om det ofte er unødvendig å tildele numeriske verdier til sannsynlighetene for hendelser... ... Colliers leksikon 1) det samme som matematisk kombinatorisk analyse. 2) En del av elementær matematikk assosiert med studiet av antall kombinasjoner, underlagt visse betingelser, som kan komponeres fra et gitt begrenset sett med objekter ... ... - (greske paradokser uventet, merkelig) i vid forstand: et utsagn som avviker skarpt fra allment akseptert, etablert oppfatning, en fornektelse av det som virker «ubetinget riktig»; i en snevrere forstand, to motstridende utsagn, for... ... Filosofisk leksikon - (eller prinsippet om inkluderinger og ekskluderinger) en kombinatorisk formel som lar deg bestemme kardinaliteten til foreningen av et begrenset antall endelige sett, som i det generelle tilfellet kan krysse hverandre ... Wikipedia En matematisk teori opptatt av å bestemme antall forskjellige måter å distribuere gitte objekter i en kjent rekkefølge; er spesielt viktig i likningsteori og sannsynlighetsteori. De enkleste oppgavene av denne typen er... ... Encyclopedic Dictionary F.A. Brockhaus og I.A. Ephron Kombinatorikk er en gren av matematikken som studerer spørsmål om hvor mange forskjellige kombinasjoner, under visse betingelser, kan lages av gitte objekter. Det grunnleggende om kombinatorikk er svært viktig for å estimere sannsynlighetene for tilfeldige hendelser, fordi Det er de som lar oss beregne det grunnleggende mulige antallet forskjellige scenarier for utvikling av hendelser. La det være k grupper av elementer, og den i-te gruppen består av n i elementer. La oss velge ett element fra hver gruppe. Da er det totale antallet N måter et slikt valg kan gjøres på, bestemt av forholdet N=n 1 *n 2 *n 3 *...*n k . Eksempel 1. La oss forklare denne regelen med et enkelt eksempel. La det være to grupper av elementer, og den første gruppen består av n 1 elementer, og den andre - av n 2 elementer. Hvor mange forskjellige elementpar kan lages fra disse to gruppene, slik at paret inneholder ett element fra hver gruppe? La oss si at vi tok det første elementet fra den første gruppen og, uten å endre det, gikk gjennom alle mulige par, og endret bare elementene fra den andre gruppen. Det kan være n 2 slike par for dette elementet. Så tar vi det andre elementet fra den første gruppen og lager også alle mulige par for det. Det vil også være n 2 slike par. Hvor mange tresifrede partall kan lages fra sifrene 0, 1, 2, 3, 4, 5, 6, hvis sifrene kan gjentas? I tilfellet når alle grupper består av like mange elementer, dvs. n 1 =n 2 =...n k =n vi kan anta at hvert utvalg er gjort fra samme gruppe, og elementet etter seleksjon returneres til gruppen. Da er antallet på alle utvalgsmetodene n k . Denne metoden for seleksjon i kombinatorikk kalles prøver med retur. Eksempel 3. Hvor mange firesifrede tall kan lages av sifrene 1, 5, 6, 7, 8? Tenk på et sett som består av n elementer. I kombinatorikk kalles dette settet generell befolkning. Definisjon 1. Overnatting fra n elementer av m i kombinatorikk evt bestilt sett fra m ulike elementer valgt fra befolkningen i n elementer. Eksempel 4. Ulike arrangementer av tre elementer (1, 2, 3) med to vil være settene (1, 2), (2, 1), (1, 3), (3, 1), (2, 3), (3) , 2). Plasseringer kan avvike fra hverandre både i elementer og rekkefølge. Antall plasseringer i kombinatorikk er angitt med A n m og beregnes med formelen: Kommentar: n!=1*2*3*...*n (les: «en factorial»), i tillegg antas det at 0!=1. Eksempel 5. Hvor mange tosifrede tall er det der titallet og enhetssifferet er distinkte og oddetall? Definisjon 2. Kombinasjon fra n elementer av m i kombinatorikk evt uordnet sett fra m ulike elementer valgt fra befolkningen i n elementer. Eksempel 6. For settet (1, 2, 3) er kombinasjonene (1, 2), (1, 3), (2, 3). Antall kombinasjoner er angitt med C n m og beregnes med formelen: Eksempel 7. På hvor mange måter kan en leser velge to bøker av seks tilgjengelige? Løsning: Antall metoder er lik antall kombinasjoner av seks bøker av to, dvs. tilsvarer: Definisjon 3. Permutasjon fra n elementer kalles noen bestilt sett disse elementene. Eksempel 7a. Alle mulige permutasjoner av et sett som består av tre elementer (1, 2, 3) er: (1, 2, 3), (1, 3, 2), (2, 3, 1), (2, 1, 3) , (3, 2, 1), (3, 1, 2). Antall forskjellige permutasjoner av n elementer er betegnet med P n og beregnes med formelen P n =n!. Eksempel 8. På hvor mange måter kan syv bøker av ulike forfattere ordnes på én rad på en hylle? Løsning: Dette problemet handler om antall permutasjoner av syv forskjellige bøker. Det er P 7 =7!=1*2*3*4*5*6*7=5040 måter å ordne bøkene på. Diskusjon. Vi ser at antall mulige kombinasjoner kan beregnes i henhold til forskjellige regler (permutasjoner, kombinasjoner, plasseringer) og resultatet vil bli annerledes, fordi Beregningsprinsippet og selve formlene er forskjellige. Ser du nøye på definisjonene, vil du legge merke til at resultatet avhenger av flere faktorer samtidig. For det første, fra hvor mange elementer vi kan kombinere settene deres (hvor stor er totalen av elementer). For det andre avhenger resultatet av størrelsen på settene med elementer vi trenger. Til slutt er det viktig å vite om rekkefølgen av elementene i settet er viktig for oss. La oss forklare den siste faktoren ved å bruke følgende eksempel. Eksempel 9. Det er 20 personer tilstede på foreldremøtet. Hvor mange ulike alternativer er det for sammensetningen av foreldreutvalget dersom det skal omfatte 5 personer? Ting vil være annerledes hvis hvert komitémedlem i utgangspunktet er ansvarlig for et spesifikt arbeidsområde. Da er det med samme listesammensetning av komiteen muligens 5 inni den! alternativer permutasjoner den saken. Antall forskjellige (både i sammensetning og ansvarsområde) alternativer bestemmes i dette tilfellet av antallet plasseringer med 20 elementer 5 hver. Selvtestoppgaver 2. Hvor mange femsifrede tall er det som leses likt fra venstre til høyre og fra høyre til venstre? 3. Det er ti fag i klassen og fem leksjoner om dagen. På hvor mange måter kan du lage en tidsplan for én dag? 4. På hvor mange måter kan 4 delegater velges ut til en konferanse hvis det er 20 personer i gruppen? 5. På hvor mange måter kan åtte forskjellige bokstaver legges i åtte forskjellige konvolutter, hvis bare én bokstav legges i hver konvolutt? 6. En kommisjon bestående av to matematikere og seks økonomer bør være sammensatt av tre matematikere og ti økonomer. På hvor mange måter kan dette gjøres?Kombinasjonsindeks
Hver kombinasjon, permutasjon, plassering og andre kombinatoriske objekter kan assosieres med en indeks - dette er tallet det vises i når du itererer gjennom denne algoritmen.
Det er en mulighet for å søke "head-on". Vi slår på kombinasjonstelleren, tar algoritmen ovenfor og prøver alt til vi kommer til ønsket alternativ. Dette alternativet har en svært høy tidskompleksitet, så vi forkaster dette alternativet.
La oss anta at inngangen inneholder tallene i1, i2, i3. Først av alt må vi ordne dem i stigende rekkefølge (merk at selve generasjonsalgoritmen, gitt ovenfor, alltid produserer dem i ordnet form, selv om selve konseptet "kombinasjon" innebærer en vilkårlig rekkefølge).
Dette betyr at vi "gikk gjennom" alle kombinasjoner der i1 var lik 0, 1 og 2.
For i1 = 0 har vi gått gjennom C(2, 51) kombinasjoner, siden indeksene i1, i2 går gjennom alle kombinasjoner av 2 av de 51 tallene.
For i1 = 1 gikk vi gjennom C(2, 50) kombinasjoner.
For i1 = 2 gikk vi gjennom C(2, 49) kombinasjoner.
Totalt gikk vi gjennom SUM (fra n = 0 til n = i1-1) C(2, 51-n).
For i1 = 3, la oss vurdere de kombinasjonene vi gikk gjennom mens vi kjørte gjennom indeks i2 (og for oss starter det med i2 = i1+1 = 4).
Når i2 = 4, C(1, 47) kombinasjoner bestått, når i2 = 5, C(1, 46) kombinasjoner bestått, når i2 = 6, C(1, 45) kombinasjoner bestått.
Ved fullstendig analogi, med i2 = 7, vurderer vi kombinasjonene som indeksen i3 gikk gjennom.
Vi får den generelle formelen:
Den nødvendige kombinasjonsindeksen = SUM (fra n = 0 til i1-1) C(2, 51-n) + SUM (fra n = i1+1 til i2-1) C(1, 51-n) + SUM (fra n = i2+1 til i3-1) C (0, 51-n).Delsettindeks
I kombinatorikk er det et mer komplekst objekt - partisjonering i delsett. For eksempel å dele opp et sett med 52 elementer i tre delsett av henholdsvis 2, 3 og 47 elementer, der rekkefølgen på elementene innenfor hvert delsett er uviktig. (Forresten, en kombinasjon av 2 av 52 er ganske enkelt et spesialtilfelle av å dele opp i to delsett med henholdsvis 2 og 50 elementer).
Igjen, hver slik partisjon har sin egen indeks.
Det viser seg at algoritmen vår for å finne kombinasjonsindeksen kan endres for å finne partisjonsindeksen.
Det skal bemerkes at vi må ordne indeksene i den "eksterne kombinasjonen" i1, i2 seg imellom, og indeksene i3, i4, i5 seg imellom, men uavhengig av de to første.
Det bør også tas i betraktning at i en "nestet kombinasjon" jobber vi i hovedsak med et sett med 50 elementer, men indeksene i3, i4, i5 må "skiftes" på en bestemt måte slik at de ikke endres fra 0 til 51, men fra 0 til 49:
(så å si, vi kutter ut indeksene i1, i2 fra vårt 52-elementsett og forskyver deretter det gjenværende settet for å lukke hullene, mens indeksene i3-i5 forskyves).
Det bør tas i betraktning at inne i hver "ekstern" kombinasjon har vi nøyaktig C(3, 50) "nestede" kombinasjoner.
Da vil algoritmen reduseres til følgende:
KOMBINASJONSINDEKS (i1, i2 av 52) * KOMBINASJONSNUMMER BY_3_OF_50 + KOMBINASJONSINDEKS (i3, i4, i5 av 50 etter indeksskift). Bringe algoritmer til konstant kompleksitet
Jeg bør umiddelbart merke meg at det oppstår en "feil" i formelen hvis for eksempel i1 = 0 (vi teller summen for n = fra 0 til -1) eller i2 = 1 (vi teller summen fra 1 til 0). Faktisk, i slike tilfeller bør den tilsvarende summen tas lik null, og resultatet vil være korrekt.
Jeg bør også være oppmerksom på tidskompleksiteten til algoritmene våre: de har lineær kompleksitet, forutsatt at du anser C som konstant tid. Dette er allerede mye bedre enn brute force.
Men egentlig (i vårt tilfelle 52) er det ingenting som hindrer oss i å redusere algoritmen til konstant kompleksitet. For å gjøre dette vil vi bruke kunnskap om matematikk og analytisk beregne alle beløpene.
For eksempel antall kombinasjoner C(2, K), hvis du "utvider" det i form av en formel K! / ((K-2)! * 2!), reduserer til et polynom av 2. grad. Og siden vi har det under sumtegnet, kan vi bruke formlene for summen av N-te potenser av tall i den naturlige rekken (se Wikipedia) og få et enkelt polynom av 3. grad. Som åpenbart har konstant tidskompleksitet. (Dessuten manifesterer ikke "feilen" som jeg siterte i begynnelsen av undertittelen seg på noen måte; formelen forblir korrekt).
Jeg gjentar, dette for en fast dimensjon på basesettet. Imidlertid er jeg sikker på at du ved hjelp av metaprogrammering kan "lære" kompilatoren slik at den gjør dette arbeidet for deg. Etterord
I min pokersimulator (Texas Hold'em) ønsket jeg å beregne og lagre vinnersannsynlighetene på forhånd for alle mulige kombinasjoner av mine håndkort (2 stykker) og alle floppkort (3 kort på bordet). 52-settet med 2, 3, 47 delsett.
Beregnet og lagret.
Men da det var på tide å lese data fra en fil for en bestemt kombinasjon, ønsket jeg virkelig ikke å beregne noe på lenge eller søke i en gigabyte-fil. Nå bestemmer jeg bare offset i filen og leser direkte hva jeg trenger.
Det ville vært interessant å ha en oppslagsbok om kombinatoriske algoritmer for alle kombinatoriske objekter, inkludert permutasjoner, kombinasjoner, plasseringer, delmengder, kombinasjoner med repetisjoner, plasseringer med repetisjoner. Eksplisitte formler
Linker
2010.
Bøker
Grunnformel for kombinatorikk
Løsning: n 1 =6 (fordi du kan ta et hvilket som helst tall fra 1, 2, 3, 4, 5, 6 som det første sifferet), n 2 =7 (fordi du kan ta et hvilket som helst tall fra 0 som det andre sifferet , 1, 2 , 3, 4, 5, 6), n 3 =4 (siden et hvilket som helst tall fra 0, 2, 4, 6 kan tas som det tredje sifferet).
Så, N=n 1 *n 2 *n 3 =6*7*4=168.
Løsning. For hvert siffer i et firesifret tall er det fem muligheter, som betyr N=5*5*5*5=5 4 =625.Antall plasseringer av n elementer med m
Løsning: fordi Hvis det er fem oddetall, nemlig 1, 3, 5, 7, 9, så kommer denne oppgaven ned på å velge og plassere to av de fem forskjellige sifrene i to forskjellige posisjoner, dvs. de angitte tallene vil være:
Antall kombinasjoner av n elementer, m hver
Permutasjoner av n elementer
Løsning: I dette eksemplet er vi ikke interessert i rekkefølgen av navn på komitélisten. Hvis de samme menneskene som et resultat viser seg å være en del av det, så er dette det samme alternativet for oss. Derfor kan vi bruke formelen til å beregne tallet kombinasjoner med 20 elementer 5 hver.
1. Hvor mange tresifrede partall kan lages fra sifrene 0, 1, 2, 3, 4, 5, 6, hvis sifrene kan gjentas?
Forholdet mellom menneske og natur Forholdet mellom menneske og natur
Sammensatte ord med en forbindelsesvokal
Urinsyre i blodet: normer og avvik, hvorfor det øker, kosthold for å redusere det Sluttproduktet av nitrogenmetabolismen er